第三四章习题课编译原理ppt课件.ppt

《第三四章习题课编译原理ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三、四章习题P64：7,8,9,12,14,15,20,补充题P81：1,2,3,4,51词法分析正规式自动机正规文法①②③④⑤⑥正规式正规文法NFADFA状态最小DFA词法分析器分裂法转换规则子集法分划法2正规式与正规文法的转化②:令VT=∑对任意正规式R选择一个非终结符Z生成规则ZR，并令S＝Z；若a和b都是正规式，对形如Aab的规则转换成AaB和Bb；在已转换的文法中，将形如Aa*b的规则进一步转换成AaA

2、b；不断利用上上面后两条规则进行转换，直到每条规则最多含有一个终结符为止。①:将每个非终结符表示成关于它的正规式方程，获得一个联立方程组。依照求解规则：若x=x

3、

4、(或x=x+)，则解为x=*若x=x

5、(或x=x+)，则解为x=*以及正规式的分配率、交换率和结合率求关于文法开始符号的正规式方程组的解。3正规式转化为NFA(1/2)(1)引进初始结点X和终止结点Y，把R表示成拓广转换图。如图XYR(2)分析R的语法结构，用如下规则对R中的每个基本符号构造NFA。R＝，构造NFA如图：R＝，构造NFA如图：XYXYR＝a(a)，构造NFA如图：XYa4正规式转化为NFA(2/2)若R是复合正规式，则按下图的转换规则对R进行分裂和加进新结，直至每个边上只留下一个符号（或）为止。ABr1r2ABr1Cr2代换为ABr1

6、r2AB

7、r1r2代换为ABr1*ABC代换为r1整个分裂过程中，所有新结点均采用不同的名字，保留X，Y为全图唯一初态结点和终态结点5NFA确定化为DFA首先将从初态S出发经过任意条弧所能到达的状态所组成的集合作为M的初态S’，然后从S’出发，经过对输入符号a的状态转移所能到达的状态(包括读输入符号之前或之后所有可能的转移所能到达的状态)所组成的集合作为M的新状态，如此重复，直到不再有新的状态出现为止。从NFAN=(Q,,F,S,Z)构造等价的DFAM=(Q’,,F’,S’,Z’)的方法6DFA的化简将DFAM的状态集Q分成两个子集：终态集F和非终态集F，形成初始分划。对建立新的分

8、划new。对的每个状态子集G进行如下变换：把G分划成新的子集，使得G的两个状态s和t属于同一子集，当且仅当对任何输入符号a，状态s和t转换到的状态都属于的同一子集。用G分划出的所有新子集替换G，形成新的分划new。如果new＝，则执行第（4）步；否则令＝new，重复第（2）步。分划结束，对分划中的每个状态子集，选出一个状态作代表，而删去其它一切等价的状态，并把射向其余状态的箭弧都改为射向作为“代表”的状态。7增加新初态X，与所有原初态用ε相连，增加新终态Y，与所有原终态用ε相连，从而构成一个新的FAM’，它只有一个初态X和一个终态Y。在X与Y之间进行弧合并：ACBr1r2A

9、Br1r2r2ACBr1r3ABr1r2ABr1

10、r2ABr1r2*r3在X和Y之间的表达式即为所求的正规式R。代之以代之以代之以自动机转化为正规式8正规文法转化为自动机(1/2)设给定一个右线性正规文法G=(VN,VT,P,S)，则相应的有穷自动机M=(Q,,f,q0,Z)（1）将VN中的每一个非终结符视作M中的一个状态，并增加一个新终态D，且DVN，令Q=VN{D},Z={D},=VT,q0=S（2）对AaB（A,BVN,aVT{}），令f(A,a)=B。构造弧（3）对Aa（AVN,aVT{}），令f(A,a)=D。构造弧ABaADa9正规文法转化为自动机

11、(2/2)设给定一个左线性正规文法G=(VN,VT,P,S)，则相应的有穷自动机M=(Q,,f,q0,Z)（1）将VN中的每一个非终结符视作M中的一个状态，并增加一个初始状态q0，且q0VN，令Q=VN{q0},Z={S},=VT(将文法G的开始符号S看成终态)（2）对ABa（A,BVN,aVT{}）令f(B,a)=A。构造弧（3）对Aa（AVN,aVT{}），令f(q0,a)=A。构造弧BAaq0Aa10自动机转化为正规文法(1/2)设给定有穷自动机M=(Q,,f,q0,Z)，按照下述方法可以从M构造出相应的右线性正规文法G=(VN,VT,P,S)，使得L

12、(M)=L(G)(1)令VN=Q,VT=,S=q0(2)若f(A,a)=B且BZ时，则将规则AaB加到P中。(3)若f(A,a)=B且BZ时，则将规则AaBa或AaB,Bε加到P中。(4)若文法的开始符号S是一个终态，则将规则Sε加到P中。ABa注意:若终态无出弧，则去掉该非终结符起点开始，考虑出弧！11自动机转化为正规文法(1/2)设给定有穷自动机M=(Q,,f,q0,Z