编译原理—词法分析、构建DFA、上下文无关文法、LL(1)分析、提取正规式

系列文章戳这里👇

1. 什么是上下文无关文法、最左推导和最右推导
2. 如何判断二义文法及消除文法二义性
3. 何时需要消除左递归
4. 什么是句柄、什么是自上而下、自下而上分析
5. 什么是LL(1)、LR(0)、LR(1)文法、LR分析表
6. LR(0)、SLR(1)、LR(1)、LALR(1)文法之间的关系
7. 编译原理第三章习题
8. 词法分析、构建DFA、上下文无关文法、LL(1)分析、提取正规式
   

   编译原理—构建DFA/上下文无关文法/提取正规式

   • 系列文章戳这里👇
   • 构建DFA
   • 上下文无关文法
   • 词法分析
   • $LL(1)$分析
   • 提取正规式

构建DFA

表示被$5$整除的二进制串的$DFA$
一个数$mod5$ 结果为 $0,1,2,3,4$以此为 $5$ 种状态。由于要求是能被 $5$ 整除的数，$0mod5=0$满足，故状态 $0$ 为初始$\&$最终状态，状态表如下:

注意这里$+0、+1$是对二进制串末尾而言，分别代表二进制串对应的十进制数乘$2$以及乘$2$再$+1$，例如$1000=8_D+0=10000=16_D$，原本$mod5$余$3$，变成了余$1$。

根据状态表构建$DFAM$

上下文无关文法

给出对应的上下文无关文法
令
$$0:S、1:A、2:B、3:C、4:D$$
则根据$DFA$给出上下文无关文法：
$$\begin{gathered} S\to 1A|0S|ϵ \\ A\to 0B|1C \\ B\to 0D|1S \\ C\to 0A|1B \\ D\to 0C|1D \end{gathered}$$

因为S是终态也是初态，所以有S→ε

词法分析

给出$First$集与$Follow$集
F i r s t ( S ) = { 0 , 1 , ϵ } F i r s t ( A ) = F i r s t ( B ) = F i r s t ( C ) = F i r s t ( D ) = { 0 , 1 } F o l l o w ( S ) = F o l l o w ( A 、 B 、 C 、 D ) = { ＄ } First(S)=\{0,1,\epsilon\}\\ First(A)=First(B)=First(C)=First(D)=\{0,1\}\\ Follow(S)=Follow(A、B、C、D)=\{＄\} First(S)={0,1,ϵ}First(A)=First(B)=First(C)=First(D)={0,1}Follow(S)=Follow(A、B、C、D)={＄}

$LL(1)$分析

给出$LL(1)$分析表

提取正规式

给出正规式$R$，使得$L(R)=L(M)$
由于状态转换图中到达终态$S0$的状态转换为$S0\to S0,S2\to S0$
因此依次消去$S4、S3、S1、S2$

S0和S2是新的初态和终态，S1是原来的S0

最终得到正规式

$(0|1(10{)}^{\ast }(0|11)(01^{\ast }01|01^{\ast }00(10{)}^{\ast }(0|11){)}^{\ast }1{)}^{\ast }$