各章练习题(编译原理).pdf

第三章复习重点：1.文法与语言的对应关系语言L(G)=L(G’)文法G文法G’{bn|n>0}B→bB|bB→Bb|b{bn|n≥0}P→bP|εP→Pb|εS→DBS→aB{abn|n>0}D→a→B→bB|bBBb|bT→PDT→Pa{bna|n≥0}D→aP→bP|εP→Pb|εU→EU|EU→Uab|ab{(ab)n|n>0}E→abV→ABV→aV|aB{ambn|m>0,n>0}A→aA|aB→bB|bB→bB|b→WABW→aW|B{ambn|m≥0,n>0}A→aA|εB→bB|bB→bB|b{anbn|n>0}X→aXb|abX→DXH|DHD→Acd{(akcd)nbn|k,n>0}A→aA|aH→bY→KYH|a{a2n+1bn|n>=0}Y→aaYb|aK→aaH→b思路要点：注意结构拆分技巧：如何将表示语言的通用字符串形式作适当的“切割”？例：已知语言：L1={axb2xcy|x,y>=0}，给出此语言的文法，并证明此语言是上下文无关语言。提示：该题实际上要求为相应语言设计上下文无关文法。一个文法设计好后，严格来说应当证明此文法是否对应于该语言。解：G[S]：S→ABA→|aAbbB→|cB推导过程：SAB+axAb2xB/*使用A→aAbbx次*/axb2xB/*使用A→一次*/axb2xcxB/*使用B→cBx次*/axb2xcx/*使用B→一次*/举一反三：已知语言L2={axb2ycy|x,y>=0}，给出此语言的文法，并证明此语言是上下文无关语言。解：G[S]：S→ABA→|aAB→|bBcc练习：14：写出下列语言对应的文法(1).{anbnambm|n,m≥0}2.{1n0m0m0n|n,m≥0}3.{1n0m0m0n|n≥0,m>0}4.{anbmck|n,m,k≥0}G1:S—>AAG2:S—>ABA—>aAb|εA—>aAb|εB—>aBb|εG:S—>1S0S—>AA—>0A1A—>εG:S1S0|AS1S0|0A1A0A1|01A0A1|ε2.给出文法，证明文法符号串是否为文法的句型，若是句型，找出这个句型的所有短语、直接短语、句柄。1.令文法G［E］为：Z→bMbM→a|(LL→Ma）①符号串b(Ma)b是否为该文法的一个句型，并证明。②若此符号串是句型，指出这个句型的所有短语、直接短语、句柄。1）（5分）证明：S=>bMb=>b(Lb=>b(Ma)b所以，符号串b(Ma)b是该文法的一个句型。（2）（5分）短语:Ma)，(Ma)，b(Ma)b直接短语:Ma)句柄:Ma)练习：（10分）已知文法G[T]：T→T*F|F；F→F↑P|P；P→(T)|i（1）用最右推导法证明β：T*P↑(T*F)是G[T]的一个句型；（2）画出β的语法树；（3）写出β的全部短语、直接短语和句柄。(1)T=>T*F=>T*F↑P=>T*F↑(T)=>T*F↑(T*F)=>T*P↑(T*F)证毕。(2)如图TT*FF↑PP(T)T*F第3题语法树（3）短语：T*P↑(T*F)；P↑(T*F)；(T*F)；T*F；P直接短语：T*F；P句柄：P3.证明一个文法是二义性文法。证明下述文法G［S］是二义的。（5分）S->iSeS|iS|i解：SSiSeSiSiSiSeS可见，句型iises有两种不同的语法树，所以G[S]是二义的。练习：证明下述文法G：SaSbS|aS|d是二义性文法。解：一个文法，如果存在某个句子有不只一棵语法分析树与之对应，那么称这个文法是二义性文法。句子aadbd有两棵语法树。如下图：SSaSaSbSaSbSaSddd(1)d(2)由此可知，SaSbS|aS|d定义的文法是二义性文法。第四章:重点：1.NFADFA的确定化及DFA的最小化。2.试写出描述语言L的正规式，构造能识别该语言L等价的NFA，再确定化将下图所示的NFA确定化，再最小化。(2010年出过)3aaX12Y4ba用子集法确定化如下表:编号IIIabAA{X,1,2,4}B{1,2,3,4}C{1,2,4,Y}BB{1,2,3,4}B{1,2,3,4}C{1,2,4,Y}CC{1,2,4,Y}B{1,2,3,4}C{1,2,4,Y}由于对于非终态的状态A和B来说，它们输入a、b的下一个状态都是一样的，故状态A和B可以合并，将合并后的状态重命名为A，而终态则重命名为B，则合并后的状态转换矩阵为：SabAABBAB由此可以得到最小化的DFA，如下图所示：aABb练习1：给出接受字母表={a，b}，语言为以b开头，以aa结尾的字符串集合的正规表达式，并构造与之等价状态的DFA。（2010年出过）答：依题意，以b开头，以aa结尾的字符串集合的正规表达式可写为：b(a|b)*aa画