编译原理课后习题答案

1第一章1．典型的编译程序在逻辑功能上由哪几部分组成？答：编译程序主要由以下几个部分组成：词法分析、语法分析、语义分析、中间代码生成、中间代码优化、目标代码生成、错误处理、表格管理。2.实现编译程序的主要方法有哪些？答：主要有：转换法、移植法、自展法、自动生成法。3.将用户使用高级语言编写的程序翻译为可直接执行的机器语言程序有哪几种主要的方式？答：编译法、解释法。4.编译方式和解释方式的根本区别是什么？答：编译方式：是将源程序经编译得到可执行文件后，就可脱离源程序和编译程序单独执行，所以编译方式的效率高，执行速度快；解释方式：在执行时，必须源程序和解释程序同时参与才能运行，其不产生可执行程序文件，效率低，执行速度慢。2第二章1.乔姆斯基文法体系中将文法分为哪几类？文法的分类同程序设计语言的设计与实现关系如何？答：1）0型文法、1型文法、2型文法、3型文法。2）2.写一个文法，使其语言是偶整数的集合，每个偶整数不以0为前导。答：ZSME|BS1|2|3|4|5|6|7|8|9M|D|MDD0|SB2|4|6|8E0|B3.设文法G为：ND|NDD0|1|2|3|4|5|6|7|8|9请给出句子123、301和75431的最右推导和最左推导。答：NNDN3ND3N23D23123NNDNDDDDD1DD12D123NNDN1ND1N01D01301NNDNDDDDD3DD30D301NNDN1ND1N31ND31N431ND431N5431D543175431NNDNDDNDDDNDDDDDDDDD7DDDD75DDD754DD7543D754314.证明文法SiSeS|iS|i是二义性文法。答：对于句型iiSeS存在两个不同的最左推导：SiSeSiiSesSiSiiSeS所以该文法是二义性文法。5.给出描述下面语言的上下文无关文法。（1）L1={anbnci|n=1,i=0}（2）L2={aibj|j=i=1}（3）L3={anbmcmdn|m,n=0}答：（1）SABAaAb|abBcB|（2）SASb|ab3Aa|（3）SaSd|A|AbAc|6.设计一个最简的DFAM,使其能够识别所有的被3整除的无符号十进制整数。答：1200|3|6|91|4|72|5|80|3|6|91|4|72|5|80|3|6|92|5|81|4|77.设计一个DFA,使其能够接受被4整除的二进制数。答：1230010101018.写出表达下列各项的正则表达式。（1）二进制数且为5的倍数。（2）Σ={a,b,c},第一个a位于第一个b之前的字符串。（3）Σ={a,b,c},包含偶数个a的字符串。（4）Σ={0，1},不包含11子串的字符串。答：（1）可以先画出相应的有限自动机:ABCDE0101100101添加新的开始状态S和终止状态T:4ABCDE0101100101ST根据以上自动机，列出以下方程：①S=A②A=0A+1B+T③B=0C+1D④C=0E+1A⑤D=0B+1C⑥E=0D+1E解以上方程组：⑥E=1*0D②A=0*1B+0*T⑥代入④C=01*0D+1A⑤代入④C=01*00B+01*01C+1AC=xB+yA其中x=(01*01)*01*00y=(01*01)*1⑤代入③B=0C+10B+11CB=(0|11)C+10BB=(10)*(0|11)C将C=xB+yA代入上式B=uB+vAB=u*vA其中u=(10)*(0|11)xv=(10)*(0|11)y将B=u*vA代入②A=0*1u*vA+0*TA=(0*1u*v)*0*T将A代入①S=(0*1u*v)*0*T串(0*1u*v)*0*即为所求。（2）该题目理解为：至少有一个a和一个b，且a出现在b的前面（可以有间隔），则答案为：c*a(a|c)*b(a|b|c)*（3）((b|c)*a(b|c)*a)*(b|c)*(a(b|c)*a|b|c)*（4）(0|10)*(1|)5第三章1.词法分析器的功能是什么？答：读源程序的字符序列，逐个拼出单词，并构造相应的内部表示TOKEN；同时检查源程序中的词法错误。2.试分析分隔符（空格、跳格及回车等）对词法分析的影响。答：空格、跳格、回车等分隔符号对词法分析不起作用，可以删除。但是回车符号可以用于错误定位，所以在删除回车符号前需要统计回车的个数。3.给出识别C语言全部实型常数的自动机。答：(+|-|)([1-9][0-9]*|0)(.[0-9][0-9]*|)(E(+|-|)[0-9][0-9]*)4.写出识别C语言中所有单词的LEX程序。答：L=[A-Z]|[a-z]D=[0-9]D1=[1-9]%%(L|_)(L|D|_)*{return(1);}D1D*{return(2);}+{return(3);}……6第四章1.设有如下文法G[S]:SaABbcd|AASd|BSAh|eC|CSf|Cg|(1)求每个产生式的Predict集。(2)该文法是否为LL(1)文法？为什么？答：(1)Predict(SaABbcd)={a}Predict(S)={#,d,f,a,h}Predict(AASd)={a,d}Predict(A)={h,a,d,b,e}Predict(BSAh)={a,d,h}Predict(BeC)={e}Predict(B)={b}Predict(CSf)={a,f}Predict(CCg)={a,f,g}Predict(C)={g,b}(2)由于Predict(AASd)Predict(A)，所以该文法不是LL(1)文法。2.下列描述括号匹配的文法中，哪些是LL(1)文法？(1)S(SS’|S’)|(2)S(S)S|(3)SS(S)S|(4)S(S|S’S’(S’)|答：(1)不是，(2)是，(3)不是，(4)不是3.已知文法G[E]:EE+T|TTT*F|FFi|(E)请按递归下降法构造该文法的语法分析程序。答：求产生式的predict集合：predict(EE+T)={i,(}predict(ET)={i,(}predict(TT*F)={i,(}predict(TF)={i,(}7由于文法中非终极符号E和T对应的产生式的predict集合的交集都不为空，所以该文法不满足自顶向下分析的条件，现对文法进行等价变换得到如下文法：ETE’E’+TE’|TFT’T’*FT’|FiF(E)求新文法的predict集合：Predict(ETE’)={(,i}Predict(E’+TE’)={+}Predict(E’)={#,)}Predict(TFT’)={i,(}Predict(T’*FT’)={*}Predict(T’)={+,),#}Predict(Fi)={i}Predict(F(E))={(}由于以上文法中任意非终极符号对应的产生式的predict集合的交集都为空，所以满足自顶向下分析的条件，所以可以写出如下的递归下降语法分析伪代码：VoidE(){if(token{(,i}){T();E’();}elseError();}voidE’(){if(token{+}){Match(‘+’);T();E’();}elseif(token{#,)}){;}elseError();}voidT(){if(token{i,(}){F();T’();}elseError();}voidT’(){if(token{*}){Match(‘*’);F();T’();}elseif(token{+,),#}){;}elseError();}voidF(){if(token{i}){Match(‘i’);}elseif(token{(}){Match(‘(‘);E();Match(‘)’);}elseError();}4.构造一个LL(1)文法G，它能识别语言L:L={|为字母表上不包括两个相邻的1的非空串}，其中={0，1}。并证明你所构造的文法是LL(1)文法。8答：A0E|1FB0E|1FC0EEB|FC|Predict(A0E)={0}Predict(A1F)={1}Predict(B0E)={0}Predict(B1F)={1}Predict(EB)={0,1}Predict(E)={#}Predict(FC)={0}Predict(F)={#}对任意非终极符号对应的产生式的predict集合的交集都为空，所以该文法是LL(1)文法。5.已知文法G[A]为：AaABe|aBBb|d(1)试给出与G[A]等价的LL(1)文法G’[A]。(2)构造G’[A]的LL(1)分析表并给出输入串aade#的分析过程。答：(1)所求G’[A]为：AaA’(1)A’ABe(2)A’(3)BdB’(4)B’bB’(5)B’(6)Predict(AaA’)={a}Predict(A’ABe)={a}Predict(A’)={#,d}Predict(BdB’)={d}Predict(B’bB’)={b}Predict(B’)={e}对任意非终极符号对应的产生式的predict集合的交集都为空，所以该文法是LL(1)文法。(3)分析表如下：abde#A(1)A’(2)(3)(3)9B(4)B’(5)(6)aade#的分析过程如下分析栈输入流动作A#aade#替换(1)aA’#aade#匹配A’#ade#替换(2)ABe#ade#替换(1)aA’Be#ade#匹配A’Be#de#替换(3)Be#de#替换(4)dB’e#de#匹配B’e#e#替换e#e#匹配##成功10第五章（这章答案是错的）1.设有下列文法：(1)SaAAAbAb(2)SaSSbSaSSSSc(3)SASSbASAAa(4)ScASccBBccBBbAcAAa构造上述文法的LR(0)归约活前缀状态机，并给出LR(0)分析表。答：(1)Z→.SS→.aAA→.AbA→.bSZ→S.01S→a.AA→.AbA→.ba2A→b.3bAS→aA.A→A.b4bA→Ab.5Ch05-1-(1)有移入、规约冲突(2)11Ch05-1-(2)Z→.SS→.aSSbS→.aSSSS→.caS→a.SSbS→a.SSSS→.cS→.aSSbS→.aSSSS→c.SZ→S.caS→aS.SbS→aS.SSS→.cS→.aSSbS→.aSSSScS→aSS.bS→aSS.SS→.cS→.aSSbS→.aSSSScabS→aSSb.SS→aSSS.01234567acZ→.S(1)S→.aSSb(2)S→.aSSS(3)S→.c(4)S0S1S2S3S4S5S6S7s2s2s2s2R4R2R3s6R4R2R3s5s5s5s5R4R2R3AccR4R2R31347abc#Sactiongoto(3)12Z→.SS→.ASS→.bA→.SAA→.a0SZ→S.A→S.AA→.SAA→.a1S→A.SS→.b6SS→AS.7AA→SA.2SA→S.AA→.aA→.SAS→.ASS→.b3aA→a.4AbS→b.5ababA→SA.S→A.SS→.ASS→.b8ASSS→AS.9bAS→.ASS→A.SS→.b10bSACh05-1-(3)有移入、规约冲突(4)Z→.SS→.cAS→.ccB0cS→c.AS→c.cBA→.cAA→.a1SZ→S.2aA→a.3AS→cA.4cS→cc.BB→.ccBB→.bA→c.AA→.cAA→.a5BS→ccB.6aB→b.9cB→c.cBA→c.AA→.cAA→.a8A→cA.7AAbcB→cc.BB→.ccBB→.bA→c