各章练习题(编译原理)

第三章复习重点：1.文法与语言的对应关系思路要点：注意结构拆分技巧：如何将表示语言的通用字符串形式作适当的“切割”？例：已知语言：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}语言L(G)=L(G’)文法G文法G’{bn|n0}B→bB|bB→Bb|b{bn|n≥0}P→bP|εP→Pb|ε{abn|n0}S→DBD→aB→bB|bS→aBB→Bb|b{bna|n≥0}T→PDD→aP→bP|εT→PaP→Pb|ε{(ab)n|n0}U→EU|EE→abU→Uab|ab{ambn|m0,n0}V→ABA→aA|aB→bB|bV→aV|aBB→bB|b{ambn|m≥0,n0}W→ABA→aA|εB→bB|bW→aW|BB→bB|b{anbn|n0}X→aXb|ab{(akcd)nbn|k,n0}X→DXH|DHD→AcdA→aA|aH→b{a2n+1bn|n=0}Y→aaYb|aY→KYH|aK→aaH→b2.{1n0m0m0n|n,m≥0}3.{1n0m0m0n|n≥0,m0}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↑PPT*TF()第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有两棵语法树。如下图：(1)(2)由此可知，SaSbS|aS|d定义的文法是二义性文法。第四章:重点：1.NFADFA的确定化及DFA的最小化。2.试写出描述语言L的正规式，构造能识别该语言L等价的NFA，再确定化将下图所示的NFA确定化，再最小化。(2010年出过)用子集法确定化如下表:编号IIaIbAA{X,1,2,4}B{1,2,3,4}C{1,2,4,Y}X431baaa2YdSSabSSadSaSSabSddBB{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，如下图所示：练习1：给出接受字母表={a，b}，语言为以b开头，以aa结尾的字符串集合的正规表达式，并构造与之等价状态的DFA。（2010年出过）答：依题意，以b开头，以aa结尾的字符串集合的正规表达式可写为：b(a|b)*aa画NFA，如下图所示用子集法确定化如下表IIaIb{X}A{1}B{1,2}C{1,2,Y}D-{1,2}C{1,2,Y}D{1,2,Y}D.{1}B{1}B{1}B{1}B（10分）将下图的NFA确定化为DFA。（2011年重修卷A出过）X12baYa0baABCbaDababbABab答：用子集法确定化如下表用子集法对所给图的确定化IIaIb状态{X,1,2}{1,2}..{1,2,3}{1,2,Y}{1,2}..{1,2}..{1,2,Y}{1,2}..{1,2,3}{1,2,3}{1,2,3}{1,2,3}X123确定化后如下图第五章重点：1.LL(1)的判别要点：（1）计算First\Follow\Select集，然后判断是否是LL(1)文法。（2）如果是LL(1)文法，则构造预测分析表。（消除左递归和左公共因子也要了解）例：（10分）已给文法G[S]：S→PS'S'→aPS'|fS'|P→qP'P'→bP|（1）该文法是否是LL（1）文法，并说明理由。（2）给出该文法的预测分析表。答：（10分）（1）Select（S→PS'）=first(P)={q}Select(S’→aPS')={a}Select(S’→fS')={f}Select(S'→)=follow(S’)=follow(S)={#}Select(P→qP')={q}Select(P'→bP)={b}Select（P'→）=follow(P’)=follow(P)={first(S’)-{}}follow(S)={a,f}{#}={a,f,#}Select(S’→aPS')Select(S’→fS')Select(S'→)=Select(P'→bP)Select（P'→）=所以文法是LL（1）文法。（7分）（2）预测分析表：（3分）abfq#SPS’S’aPS’fS’PqP’P’bP(15分)写出下列文法中各候选式的FIRST集和各非终结符的FOLLOW集,构造该文法的LL（1）分析表，并说明它是否为LL（1）文法。（2011年重修卷A出过）S→aA|BAA→cB|B→bB|各候选式的FIRST集(4分)FIRST（aA）={a}FIRST（BA）={b，c，}FIRST（cB）={c}FIRST（）={}FIRST（bB）={b}FIRST（）={}各非终结符的FOLLOW集(4分)FOLLOW(S)={#}FOLLOW(A)={#}FOLLOW(B)={c，#}LL（1）分析表(5分)abc#SS→aAS→BAS→BAS→BAAA→cBA→BB→bBB→B→说明它是否为LL（1）文法(2分)判断1分，理由1分因为LL（1）分析表无冲突，所以该文法是LL（1）文法。2.设文法G(S):S→^|a|(T)T→T,S|S⑴消除左递归；⑵构造相应的FIRST和FOLLOW集合；⑶构造预测分析表解：(1)消除左递，文法变为G’[S]：S→^|a|(T)'T→ST’|ST’→,ST’|ε此文法无左公共左因子。(2)构造相应的FIRST和FOLLOW集合：FIRST(S)={a,^,(}，FOLLOW(S)={#,,,)}FIRST(T)={a,^,(}，FOLLOW(T)={}}FIRST(T’)={,,ε}，FOLLOW(F)={)}(3)构造预测分析表：a^(),#SS→aS→^S→(T)'TT→ST’T→ST’T→ST’T’T’→εT’→,ST’第七章重点：1.识别活前缀的有限自动机的构造，判断某个文法是否是LR(0)文法，或SLR（1）文法或LR（1）文法，若不是，请说明理由，若是，构造相应的LR分析表。2.查LR分析表，进行句子的识别。典型例题：文法G[S]及其LR分析表如下，请给出串baba#的LR分析过程。(1)S→DbB(2)D→d(3)D→ε(4)B→a(5)B→Bba(6)B→εLR分析表状态ACTIONGOTObDa#SBD0r3s3121acc2S43r24r6S5r665r4r46S7r17S88r5r5(注：答案格式为步骤状态栈符号栈输入串ACTIONGOTO)答案：步骤状态符号输入串ACTIONGOTO00#baba#r32102#Dbaba#S42024#Dbaba#S530245#Dbaba#r4640246#DbBba#S7502467#DbBba#S86024678#DbBba#r5670246#DbB#r11801#S#acc2.（8分）已知拓广文法G[S’]：S’→SS→AS∣εA→aA∣b（1）试构造以LR（1）项目集为状态的识别活前缀的有穷自动机；（2）试判断文法是否是LR(1)文法，并说明理由。(1)I0:I2:I6:（2）有穷自动机所有的状态都不含有“移进－归约”、“归约－归约”冲突，因而该文法是LR(1)文法。练习：.(20分)给定文法G[S]：S→SaA|aA→AbS|b⑴(8分)请构造该文法的以LR(0)项目集为状态的识别规范句型活前缀的DFA。⑵(4分)请构造该文法的LR(0)分析表。⑶(4分)什么是LR(0)文法？该文法是LR(0)文法吗？为什么？⑷(4分)什么是SLR(1)文法？该文法是SLR(1)文法吗？为什么？答：⑴拓广文法1分G[S′]:S′→S⑴S→SaA⑵S→a⑶A→AbS⑷A→b⑸[S→A．S，#][S→．AS，#][S→．，#][A→．aA，a/b/#][A→．b，a/b/#][S'→．S，#][S→．AS，#][S→．，#][A→．aA，a/b/#][A→．b，a/b/#][A→aA．，a/b/#]ASabbI2I1I5[S→AS．，#]I4[A→b．，a/b/#]I3[A→a．A，a/b/#][A→．aA，a/b/#][A→．b，a/b/#]I6I0SAabAa[S'→S．，#]该文法的以LR(0)项目集为状态的识别规范句型活前缀的DFA：⑵该文法的LR(0)分析表：状态ACTIONGOTOab#SA0S211S3acc2r3r3r33S544r2r2/S6r25r5r5r56S277r4/S3r4r4⑶LR(0)文法：该文法的以LR(0)项目集为状态的识别规范句型活前缀的DFA中没有冲突状态。该文法不是LR(0)文法因为存在冲突状态：I4和I7⑷SLR(1)文法：该文法的以LR(0)项目集为状态的识别规范句型活前缀的DFA中有冲突状态，冲突可用FOLLOW集解决。该文法不是SLR(1)文法。因为FOLLOW(S)={a,b,#}，所以无法解决冲突。其它练习可以直接做书本上我们布置的作业！第八章：1.给出代码，写成代码对应的四元式(三地址码形式！)重点：（1）.赋值语句（2）.For语句（3）.if…then语句（4）数组赋值（5）.while语句例：写出下面语句经语法制导翻译后所生成的四元式代码序列。（共10分）ifxythenwhileecdoc:=c+1elsex:=x+5（依次翻译，再考虑回填！）解：假设初始为100，则四元式代码序列为100ifxygoto102101goto107102ifecgoto104103goto109104M:=C+1105C:=M106goto1021