资源描述:
《第三四章习题课编译原理ppt课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、第三、四章习题P64:7,8,9,12,14,15,20,补充题P81:1,2,3,4,51词法分析正规式自动机正规文法①②③④⑤⑥正规式正规文法NFADFA状态最小DFA词法分析器分裂法转换规则子集法分划法2正规式与正规文法的转化②:令VT=∑对任意正规式R选择一个非终结符Z生成规则ZR,并令S=Z;若a和b都是正规式,对形如Aab的规则转换成AaB和Bb;在已转换的文法中,将形如Aa*b的规则进一步转换成AaA
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如图:XYXYR=a(a),构造NFA如图:XYa4正规式转化为NFA(2/2)若R是复合正规式,则按下图的转换规则对R进行分裂和加进新结,直至每个边上只留下一个符号(或)为止。ABr1r2ABr1Cr2代换为ABr1
6、r2AB
7、r1r2代换为ABr1*ABC代换为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,且DVN,令Q=VN{D},Z={D},=VT,q0=S(2)对AaB(A,BVN,aVT{}),令f(A,a)=B。构造弧(3)对Aa(AVN,aVT{}),令f(A,a)=D。构造弧ABaADa9正规文法转化为自动机
11、(2/2)设给定一个左线性正规文法G=(VN,VT,P,S),则相应的有穷自动机M=(Q,,f,q0,Z)(1)将VN中的每一个非终结符视作M中的一个状态,并增加一个初始状态q0,且q0VN,令Q=VN{q0},Z={S},=VT(将文法G的开始符号S看成终态)(2)对ABa(A,BVN,aVT{})令f(B,a)=A。构造弧(3)对Aa(AVN,aVT{}),令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且BZ时,则将规则AaB加到P中。(3)若f(A,a)=B且BZ时,则将规则AaBa或AaB,Bε加到P中。(4)若文法的开始符号S是一个终态,则将规则Sε加到P中。ABa注意:若终态无出弧,则去掉该非终结符起点开始,考虑出弧!11自动机转化为正规文法(1/2)设给定有穷自动机M=(Q,,f,q0,Z