编译原理课后习题答案

最新编译原理课后习题答案最新编译原理课后习题答案最新编译原理课后习题答案优选文档第一章1．典型的编译程序在逻辑功能上由哪几部分组成？答：编译程序主要由以下几个部分组成：词法解析、语法解析、语义解析、中间代码生成、中间代码优化、目标代码生成、错误办理、表格管理。实现编译程序的主要方法有哪些？答：主要有：变换法、移植法、自展法、自动生成法。将用户使用高级语言编写的程序翻译为可直接履行的机器语言程序有哪几种主要的方式？答：编译法、解说法。编译方式和解说方式的根本差别是什么？答：编译方式：是将源程序经编译获取可履行文件后，即可走开源程序和编译程序独自履行，所以编译方式的效率高，履行速度快；解说方式：在履行时，必然源程序和解说程序同时参加才能运行，其不产生可履行程序言件，效率低，履行速度慢。优选文档优选文档第二章乔姆斯基文法系统中将文法分为哪几类？文法的分类同程序设计语言的设计与实现关系怎样？答：1）0型文法、1型文法、2型文法、3型文法。2）2.写一个文法，使其语言是偶整数的会合，每个偶整数不以0为前导。答：ZSME|B1|2|3|4|5|6|7|8|9M|D|MDD0|SB2|4|6|8E0|B设文法G为：ND|NDD0|1|2|3|4|5|6|7|8|9请给出句子123、301和75431的最右推导和最左推导。答：NNDN3ND3N23D23123NNDNDDDDD1DD12D123NNDN1ND1N01D01301NNDNDDDDD3DD30D301NNDN1ND1N31ND31N431ND431N5431D543175431NNDNDDNDDDNDDDDDDDDD7DDDD75DDD754DD7543D75431证明文法SiSeS|iS|i是二义性文法。答：关于句型iiSeS存在两个不同样的最左推导：SiSeSiiSesSiSiiSeS所以该文法是二义性文法。给出描绘下面语言的上下文没关文法。1）L1={anbnci|n>=1,i>=0}2）L2={aibj|j>=i>=1}3）L3={anbmcmdn|m,n>=0}答：1）SABaAb|abcB|2）SASb|ab优选文档优选文档Aa|（3）SaSd|A|AbAc|6.设计一个最简的DFAM,使其能够鉴识全部的被3整除的无符号十进制整数。答：2|5|80|3|6|90|3|6|901|4|711|4|722|5|82|5|80|3|6|91|4|7设计一个DFA,使其能够接受被4整除的二进制数。答：001101001231写出表达以下各项的正则表达式。1）二进制数且为5的倍数。2）Σ={a,b,c},第一个a位于第一个b以前的字符串。3）Σ={a,b,c},包括偶数个a的字符串。（4）Σ={0，1},不包括11子串的字符串。答：1）能够先画出相应的有限自动机:100A10C1B

10DE10增加新的开始状态S和停止状态T:优选文档优选文档1001SA10C1D0BE10T依据以上自动机，列出以下方程：S=AA=0A+1B+TB=0C+1DC=0E+1AD=0B+1CE=0D+1E解以上方程组：E=1*0DA=0*1B+0*T⑥代入④C=01*0D+1A⑤代入④C=01*00B+01*01C+1AC=xB+yA其中x=(01*01)*01*00y=(01*01)*1⑤代入③B=0C+10B+11CB=(0|11)C+10BB=(10)*(0|11)C将C=xB+yA代入上式B=uB+vAB=u*vA其中u=(10)*(0|11)xv=(10)*(0|11)y将B=u*vA代入②A=0*1u*vA+0*TA=(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|)优选文档优选文档词法解析器的功能是什么？答：读源程序的字符序列，逐个拼出单词，并结构相应的内部表示TOKEN；同时检查源程序中的词法错误。试解析分开符（空格、跳格及回车等）对词法解析的影响。答：空格、跳格、回车均分开符号对词法解析不起作用，能够删除。可是回车符号能够用于错误定位，所以在删除回车符号前需要统计回车的个数。给出鉴识C语言全部实型常数的自动机。答：(+|-|)([1-9][0-9]*|0)(.[0-9][0-9]*|)(E(+|-|)[0-9][0-9]*)写出鉴识C语言中全部单词的LEX程序。L=[A-Z]|[a-z]D=[0-9]D1=[1-9]%%(L|_)(L|D|_)*{return(1);}D1D*{return(2);}+{return(3);}优选文档优选文档第四章设有以下文法G[S]:SaABbcd|AASd|BSAh|eC|CSf|Cg|求每个产生式的Predict集。该文法能否为LL(1)文法？为什么？答：(1)Predict(SaABbcd)={a}Predict(S)={#,d,f,a,h}Predict(AASd)={a,d}Predict(A)={h,a,d,b,e}Predict(BSAh)={a,d,h}Predict(BeC)={e}Predict(B)={b}Predict(CSf)={a,f}Predict(CCg)={a,f,g}Predict(C)={g,b}(2)由于Predict(AASd)Predict(A)，所以该文法不是LL(1)文法。2.以下描绘括号般配的文法中，哪些是LL(1)文法？(1)S(SS’|S’)|(2)S(S)S|(3)SS(S)S|(4)S(S|S’S’(S’)|答：(1)不是，(2)是，(3)不是，(4)不是已知文法G[E]:EE+T|TTT*F|FFi|(E)请按递归下降法结构该文法的语法解析程序。答：求产生式的predict会合：predict(EE+T)={i,(}predict(ET)={i,(}predict(TT*F)={i,(}predict(TF)={i,(}优选文档优选文档由于文法中非终极符号E和T对应的产生式的predict会合的交集都不为空，所以该文法不知足自顶向下解析的条件，现对文法进行等价变换获取以下文法：ETE’E’+TE’|TFT’T’*FT’|iF(E)求新文法的predict会合：Predict(ETE’)={(,i}Predict(E’+TE’)={+}Predict(E’)={#,)}Predict(TFT’)={i,(}Predict(T’*FT’)={*}Predict(T’)={+,),#}Predict(Fi)={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();}结构一个LL(1)文法G，它能鉴识语言L:L={|为字母表上不包括两个相邻的1的非空串}，其中={0，1}。并证明你所结构的文法是LL(1)文法。优选文档优选文档答：A0E|1F0E|1F0EB|C|Predict(A0E)={0}Predict(A1F)={1}Predict(B0E)={0}Predict(B1F)={1}Predict(EB)={0,1}Predict(E)={#}Predict(FC)={0}Predict(F)={#}对随意非终极符号对应的产生式的predict会合的交集都为空，所以该文法是LL(1)文法。已知文法G[A]为：AaABe|aBBb|d(1)试给出与G[A]等价的LL(1)文法G’[A]。(2)结构G’[A]的LL(1)解析表并给出输入串aade#的解析过程。答：(1)所求G’[A]为：AaA’(1)A’ABe(2)A’(3)BdB’(4)B’bB’(5)B’(6)Predict(AaA’)={a}Predict(A’ABe)={a}Predict(A’)={#,d}Predict(BdB’)={d}Predict(B’bB’)={b}Predict(B’)={e}对随意非终极符号对应的产生式的predict会合的交集都为空，所以该文法是LL(1)文法。解析表以下：abde#A(1)A’(2)(3)(3)优选文档优选文档B(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#般配##成功优选文档优选文档第五章（这章答案是错的）设有以下文法：SaAAAbAbSaSSbSaSSSScSASSbASAAaScASccBBccBBbAcAAa结构上述文法的LR(0)归约活前缀状态机，并给出LR(0)解析表。答：(1)Ch05-1-(1)0Z→.SS→.aAA→.AbA→.b3A→b.(2)

有移入、规约矛盾1SZ→S.a2S→a.AA45A→.AbS→aA.bA→Ab.A→.bA→A.bb优选文档优选文档Ch05-1-(2)1Z→S.S0aZ→.S2346S→.aSSbS→a.SSbaS→aS.SbS→aSS.bbS→aSSb.S→.aSSSS→a.SSSS→aS.SSS→aSS.SS→.caS→.cSS→.cSS→.c7S→.aSSbS→.aSSbS→.aSSbSS→aSSS.c5S→.aSSSS→.aSSSS→.aSSScaS→c.ccactiongotoabc#SS0s2s51Z→.S(1)S1AccS→.aSSb(2)S2s2s53S→.aSSS(3)S3s2s54S→.c(4)S4s2s6s57S5R4R4R4R4S6R2R2R2R2S7R3R3R3R3(3)优选文档优选文档Ch05-1-(3)1Z→S.A→S.AA→.SA0A→.aSZ→.SaS→.AS4S→.baA→a.A→.SA5A→.abAS→b.b6S→A.S7S→.bSS→AS.(4)

有移入、规约矛盾28A→SA.A→SA.AS→A.SS→.AS3S→.bSA→S.AAA→.aA→.SAaS→.ASS→.bbSb

9SS→AS.S10S→.ASS→A.SS→.bAbCh05-1-(4)11B→ccB.B810B→c.cBcB→cc.B46A→c.AB→.ccBS→cA.S→ccB.A→.cAcB→.bABA→.aA→c.A015cAA→.cAS→c.AS→cc.BA→.aZ→.SccB→.ccB7AS→.cAS→c.cBAA→.cAB→.bA→cA.aS→.ccBA→.aA→c.A9bSaaA→.cAbaB→b.A→.a23Z→S.A→a.优选文档优选文档Z→S(1)actiongotoabc#ABSS→cA(2)S0s12S→ccB(3)S1s3s54B→ccB(4)B→b(5)S2AccA→cA(6)S3R7R7R7R7A→a(7)S4R6R6R6R6S5s3s9s876S6R3R3R3R3S7R2R2R2R2S8s3s107S9R5R5R5R5S10s3s9s8711S11R4R4R4R4设有以下文法：SSaS|b(2)SbSb|cSc|b|cSbSb|bSc|dSaSb|bSa|abSSab|bRRS|aSSAB|BABbAaA|BSAaAb|BbBaBAAaABe|BaBdB|说明上述文法能否为SLR(1)文法。假如，请结构SLR(1)解析表；若不是，请说明原由。答：(1)Ch05-2-(1)不是SLR（1）Follow(S)={#,a}023S4Z→.SSZ→S.S→Sa.SS→SaS.S→.SaSaS→.SaSS→.bS→S.aSS→.baS→S.aSbb1S→b.优选文档优选文档(2)Ch05-2-(2)不是SLR（1）Follow(S)={#,b,c}01bS→b.SbZ→.SS→b.S→.bSbS→.bSbS→.cScS→.cScS→.bS→.bS→.cS→.c(3)Ch05-2-(3)是SLR（1）0Z→.SS→.bSbS→.bScS→.dS1Z→S.

35dS→d.S→bSb.db24bS→b.SbS→b.ScSS→bS.bS→bS.cS→.bSbcbS→.bScS→.d6S→bSc.actiongotobcd#SZ→.S(1)S0s2s31S1AccS→.bSb(2)S2s2s3Ch05-2-74S→.bSc(3)S→.d(4)S3R4R4R4S4s5s6S5R2R2R2S6R3R3R3(4)优选文档优选文档Ch05-2-(4)不是SLR（1）Follow(S)={#,a,b}0Z→.SS→.aSbS→.bSaS→.abS1Z→S.

234S→a.SbSS→aS.bbS→aSb.S→a.b5S→.aSbbS→ab.aS→.bSaS→b.SaS→.abS→.aSb4S→.bSaS→.abS→b.SaS→.aSbS→.bSaS→.ab(5)Ch05-2-(5)不是SLR（1）Follow(R)={#,a}1Z→S.a2b3S→S.abS→Sa.bS→Sab.S045Z→.SS→b.RRS→bR.R→.SS→.Sabb4R→.aS→.bRSS→.SabR→S.S→.bRS→S.ab(6)Ch05-2-(6)0Z→.SS→.SABS→.BAB→.bS1Z→S.S→S.ABA→.aAA→.BB→.b9S→SAB.

是SLR（1）2bB→b.b4B3AS→BA.S→B.AB5A→.aAA→B.A→.BBB→.ba6baA→a.A2A→.aAB5BA→.BB→.bA8BS→SA.Bb2B→.b

b7AA→aA.a优选文档优选文档actiongotoab#ABSZ→S(1)S0s231S1s6s2Acc85S→SAB(2)S2R6R6R6Ch05-2-7S→BA(3)S3s6s245A→aA(4)S4R3R3R3A→B(5)S5R5R5R5B→b(6)S6s6s275S7R4R4R4S8s29S9R2R2R2(7)Ch05-2-(7)不是SLR（1）Follow(A)={a,b}Follow(B)={a,b}0S1Z→.SZ→S.S→.AaAb2468S→.BbBaAS→Aa.AbS→A.aAbabA→.A→.AS→AaA.bS→AaAb.B3B→.b5S→B.bBaS→Bb.Ba79BB→.S→BbB.aaS→BbBa.(8)Ch05-2-(8)

不是SLR（1）Follow(B)={a,e}1Z→A.A0Z→.A→.aABeA→.BaB→.dB

3A→a.ABeA→.aABeA→.BaB→.dBaB→.B4BA→B.a

6A→aA.BeB→.dBB→.9aA→Ba.

7BA→aAB.ee8A→aABe.dB→.

d

5

d→d.BB→.dBB→.d

10BB→dB.设有以下文法：aAd|bBd|aBe|bAeAgBg说明该文法是LR(1)文法，但不是LALR(1)文法。答：优选文档优选文档Ch05-3是LR(1)文法0→.SS→.aAdS→.bBdS→.aBeS→.bAeS1Z→S.

2A4#d7##S→aA.dS→aAd.S→a.Ad58S→a.Be#BeS→aB.e#S→aBe.#A→.gda6#B→.gegdA→g.#B→g.e##912#b3A#e##S→bA.eS→bAe.S→b.Bd1013S→b.Ae#B#d##A→.geS→bB.dS→bBd.11B→.gdgeA→g.B→g.dCh05-3不是LALR(1)文法2A4#d7##S→aA.dS→aAd.S→a.Ad58S→a.Be#BeS→aB.e#S→aBe.#0A→.gda#B→.geZ→.SgS→.aAd#6S→.bBd#d,eA→g.S→.aBe#bB→g.e,dS→.bAe#3gSS→b.Bd#A9e121S→b.Ae#S→bA.e#S→bAe.#Z→S.#A→.ge1013B→.gdB#d#S→bB.dS→bBd.设有以下文法：EE+T|TTTF|T(E)|F*|a|bSAa|bAc|dc|bdad说明上述文法能否为SLR(1)文法？能否为LALR(1)文法？并结构相应的解析表。答：(1)优选文档优选文档Ch05-4-(1)不是SLR(1)文法Follow(T)={#,(,a,b,+,)}34FT→TF.E→E+T.F→F.*T→T.F6T→T.a2F→a.TF→.(E)71E→E+.TbF→.F*F→b.Z→E.+T→.TFF→.a0EE→E.+TT→.TF→.b11Z→.E+(E→T.E→.E+T8T→T.FE→.T109F→(.E)(T→T.T→.TFE→.E+TF→(E).)F→(E.)EF→.(E)T→.TE→.TE→E.+TF→.F*T→.TFTF→.aT→.TF→.b

5*F→F*.4a6b7Ch05-4-(1)不是LALR(1)文法21E→E+.T#+(ab*)T→.TF#+(abZ→E.#E→E.+T#++T→.T#+(abE+Z→.E09#F→(E.)#+(ab*)E→.E+T#+E→E.+T#+(ab*)E→.T#+(T→.TF#+(ab10T→.T#+(abF→(E).#+(ab*)

5F→F*.#+(ab**34E→E+T.#+FT→TF.#+(abT→T.F#+(abF→F.*#+(ab*T→T.#+(aba6F→.(E)#+(ab*F→a.#+(ab*TF→.F*#+(ab*b7F→.a#+(ab*F→b.#+(ab*F→.b#+(ab*(118F→(.E)#+(ab*)(E→T.#+(ab*)EE→.E+T#+(ab*)T→T.F#+(ab*)E→.T#+(ab*)T→T.#+(ab*)T→.TF#+(ab*)F→.(E)#+(ab*)TF→.F*#+(ab*)T→.T#+(ab*)F→.a#+(ab*)F→.b#+(ab*)(2)Ch05-4-(2)不是SLR(1)文法Follow(A)={a,c}0A2a3Z→.SS→A.aS→Aa.S→.Aa45S→.bAcdcS→d.cS→dc.S→.dcA→d.S→.bda6A7c8A→.dbSS→b.AcS→bA.cS→bAc.S→b.dad9c101A→.dS→bd.aS→bda.Z→S.A→d.优选文档优选文档Ch05-4-(2)是LALR(1)文法15Z→S.#S→Aa.#Sa0A4Z→.SS→A.a##69S→.Aa#S→.bAc#bS→b.Ac#AS→bA.c#S→.dc#S→b.da#cA→.dcS→.bda#10dA→.da7S→bAc.#d#2S→bd.aA→d.cS→d.c#A→d.aac83S→bda.#S→dc.#actiongotoabcd#ASZ→.S(1)S0s6s241S1AccS→.Aa(2)S2R6s3S→.bAc(3)S→.dc(4)S3R4S→.bda(5)S4s5A→.d(6)S5R2S6s79S7s8R6S8R5S9s10S10R3设有以下文法：LMLb|aM说明上述文法能否为LR(1)文法，若不是，请说明原由。答：Ch05-5是LR(1)文法5L→a.ba0#MZ→.LL→.MLb#L→.a#M→.aL1Z→L.#

237L→M.LbLL→ML.b#bL→MLb.##L→.MLbb489L→.abMLL→ML.bbbL→MLb.bM→.aL→M.LbbL→.MLbb10aL→.abM→.aML→a.b优选文档优选文档第六章1.试写出以下种类的内部表示：egerb.ARRAY[1..5]ofRECORDi:integer;b:booleanENDc.ARRAY[1..5]ofRECORDa:ARRAY[1..10];r:RECORDi,j:integerENDENDd.RECORDr:RECORDx,y:realEND;a:ARRAY[1..10]ofintegerEND设目前层数为l，可用区距为101，且有以下程序段：CONSTmm=333；nn=444；TYPEatype=ARRAY[1..10]OFreal;rtype=RECORDi,j:integerEND;VARa,b:atype;x,y:real试写出各表记符的内部表示。设目前层数和区距分别为l和off，且有函数说明首部：FUNCTIONf（A：atype；VARB：atype；VARX：real）：integer其中atype的定义见题5，试写出f的内部表示。要求在下面括号中写上相应?（层数）和区距（off）。（）（）PROCEDURE（gA：atype；（）（）VARB：atype；（）（）VARX：real（）（））（）（）.给出下面C程序扫描到语句c=a+b+x时相应的全局符号表(采用次序表结构)。main（）{inta=0;floatc=1.0;{floata=3.0;{floatx=1.3;floatb=0.3;}{intb=10;c=a+b+x;}}}6.给出题1中程序扫描到语句c=a+b+x时相应的全局符号表(采用外拉链的散列表结构)。优选文档优选文档7.依据表记符的作用域规则，分别给出图6.5的程序中，过程P、Q、R、S中有效的表记符。优选文档优选文档第七章将算术表达式(a+b)*(c+d)-(a+b+c)翻译成四元式序列。将以下语句翻译成四元式序列：a.IFx>0THENx:=0ELSEx:=1b.WHILEx>0DOx:=x-1c.IFx>0THENx:=x+1ELSEIFx<0THENx:=x+1ELSEx:=x+1d.WHILEx>0DOWHILEy>0DOBEGINy:=y-x;x:=x-1END3.给出以下程序段的四元式序列。(四元式的操作符可用自己代替)。其中A：Arrayof[1..10]ofinteger。a:=1;whilea<=10dobeginifa<>bthenA[a]:=A[b]+2;elsea:=a+1;b:=b+1;end试将FOR语句翻译成四元式序列。试将UNTIL语句翻译成四元式序列。试将CASE语句翻译成四元式序列。试给出4、5、6题中翻译过程的语法制导程序。优选文档优选文档第八章将下面的程序段区分为基本块并画出其程序流图。read(A);read(B);F:=1;C:=A*A;D:=B*B;ifC<DgotoL1;E:=A*A;F:=F+1;E:=E+F;write(E);gotoL3;L1:E:=B*B;F:=F+2;write(E);ifE>100gotoL2;gotoL3;L2:F:=F-1;gotoL1;L3:write(E);假定有以下语句序列，写出常表达式优化前和优化后的四元式中间代码。(1)i:=1;(2)a:=20;j:=i*(i+1);b:=a*(a+10);k:=2*(i+j);c:=a*b;假定有以下语句序列或表达式，写出公共表达式优化前和优化后的四元式中间代码。x:=x*y+z;y:=x*y+z;z:=x*y+z;(a*b+c)/(a*b-c)+(c*b+a-d)/(a*b+c)写出以下循环语句不变式外提后的四元式中间代码。whilei<=100dobeginu:=A*B;m:=u*u;S:=S+m*m;i:=i+1;end5.写出下面循环语句不变式外提后的四元式中间代码，其中数组各下标的种类为1..10。whilei<=100dobeginj:=1;whilej<=100do优选文档优选文档begink:=1;whilek<=100doA[i][j][k]:=0;endend优选文档优选文档第九章1.过程活动记录包括哪些信息？各信息的作用？何时填写它们？2.下面是一个调用递归函数的Pascal程序prog