编译原理课后习题答案杨明.doc

编译原理习题答案习题1 1.1翻译程序：把用某种程序设计语言（源语言）编写的程序（源程序）翻译成与之等价的另一种语言（目标语言）的程序（目标程序）。 编译程序：一种翻译程序，将高级语言编写的源程序翻译成等价的机器语言或汇编语言的目标程序。 1.2词法分析、语法分析、语义分析和中间代码生成、代码优化、目标代码生成1.3词法分析：根据语言的词法规则对构成源程序的符号进行扫描和分解，识别出一个个的单词。 语法分析：根据语言的语法规则，把单词符号串分解成各类语法单位。 语义分析及中间代码生成：对语法分析识别出的语法单位分析其含义，并进 行初步翻译。 代码优化：对中间代码进行加工变换，以产生更高效的目标代码。 目标代码生成：将中间代码变换成特定机器上的绝对指令代码、可重定位的指令代码或会变指令代码。 以上5个阶段依次执行。习题2 2.1 （1）有穷非空的符号集合（2）利用产生是规则A-v将A替换为v时与A的上下文无关。 （3）略 （4）推导是把句型中的非终结符用一个产生是规则的右部开替代的过程； 直接推导是将非终结符的替代结果只用了一次产生式规则。（5）略（6）一个句型的最左直接短语（7）如果一个文法存在某个句子对应两棵不同的语法树或有两个不同的最左（右）推导，则称这个文法是二义的。2.2（1）VN =Z,A,B VT =a,b,c,d,e （2）abbcde,abbbcde是，acde不是。2.3 （1）LG=d|n1,m0 （2）2.4 （1） A=B=c=fAg=fBg=fCg=feg （2）A=AaB=AaC=Aae=Bae=BcCae=Bceae=Cceae=eceae（3）A=B=BcC=BcfAg=BcfAaBg=BcfAaCg=BcfAaeg=BcfBaeg=BcfCaeg=Bcfeaeg=Ccfeaeg=ecfeaeg（3）中题目有错应为CfCg|e2.5 LG=abc|aab,n22.6 (1)ZAB AAa| BBb| (2)ZaZb|ab (3)ZaAb AaAb|b (4)ZAB AaAb|ab BcB| (5)ZaaAb|ab ZaaBb|bb AaaAb|ab BaaBb|bb2.7 一位数：Z2|4|6|8 两位数：ZAB A1|2|3|4|5|6|7|8|9 B0|2|4|6|8 三位以上：ZACB A1|2|3|4|5|6|7|8|9 B0|2|4|6|8 CCD D0|1|2|3|4|5|6|7|8|92.8证明：E=E+T=E+T*F 短语：T*F E+T*F 直接短语：T*F 句柄：T*F2.9 语法树： E 短语：E*T , (E*T) , F(E*T) ，F ,E* F(E*T) E * F 直接短语：E*T , F T F 句柄：F F ( E ) E * T 2.10（1）语法树 （2） 直接短语：a , Z Z 句柄：Z ( L ) L , Z Z ( L ) Z a2.11最左推导：Z=ZaB=BaB=B+AaB=A+AaB=(+)Z*aB=(+)ZaB*aB =(+)+aB*aB=(+)+aA*aB=(+)+a(*aB=(+)+a(*aA =(+)+a(*a( 直接短语：（，+ 句柄：(2.12(1) S=iSeS=iiSeS=iiIeS=iiIeI S=iS=iiSeS=iiIeS=iiIeI (2) S=SaS=cSaS=cfaS=cfaf S=cS=cSaS=cfaS=cfaf (3) E=EOE=EOEOE=iOEOE=i+EOE=i+iOE=i+i-E=i+i-i E=EOE=iOE=i+E=i+EOE=i+iOE=i+i-E=i+i-i2.13 ZaABZ|cCACd AbAB|aZA|cCC BbAB|Czb CcZ|c习题3 3.1(1)确定的有限自动机 (2)不确定的有限自动机 (3)正规集是一类特殊的单词集合，正规式是正规集的描述工具3.2 (1) (1|2|3|4|5|6|7|8|9|0)*(1|3|5|7|9) (2) 11(0|1)*00 3.3 证明：b*(a|b)+=a,b,ab,ba,aa,bb (a|b)+=a,b,ab,ba,aa,bbcbaDSSSssS0DSSSssADSSSssBDSSSssCDSSSssZ3.4 (1) DSSSssS0DSSSssZaDSSSssAabb(2) bbDSSSssFbDSSSssEabDSSSssDDSSSssCDSSSssBDSSSssS0aDSSSssZbDSSSssAabaDSSSss Ga(3) (4)aDSSSssBaDSSSssZDSSSssS0DSSSssAbabbaDSSSssS0 DSSSssZDSSSssX010DSSSssU1baDSSSssYDSSSssAaDSSSssZb3.5(1) (2)(3) 3.6(1) (01|10) *(01|10) (2) (0(1|00)*)|00 3.7(1) Z1AB (2)ZAB A(0|1)A A0A| A0|1 B(0|1)B| B0B B 3.8 r=a(a|b)*bb 3.9 Z1B B0Z|0 Z0Z|baDSSSss3DSSSss0baDSSSss1DSSSss4bbaaDSSSssADSSSssBaDSSSssCaDSSSssDbb 3.10 3.11b 习题44.1 (1)若文法GZ满足文法不含左递归 (2)4.2(1) First(S)=a,d First(B)=a,d,c,First(A)=a,d,e,c First(D)=a,d,Follow(S)=#,a,b,d,e Follow(B)=a,dFollow(A)=b Follow(D)=e,a,d,b(2) 不是4.3 (1) 证明： First(Z)=a,b,c Follow(S)=#,a,b,c,d First(A)=a,b,c,d Follow(A)= #,a,b,c,d First(B)=a,d,c Follow(B)= a,b,c,d 是LL(1)文法。 (2) 输入非终结符abcd#ZZBAZBAZBAAABZABZABZAdBBaABbZBc (3)略4.4 (1) ZNZ1 Z1E| EZE1 E1 *E| Ni (2) First(Z)=i Follow(Z)=#,*, First(Z1)=, Follow(Z1)= #,*,First(E)=i Follow(E)= First(E1 )=*, Follow(E1 )= First(N)=i Follow(N )=#,* (3) 输入非终结符*i#ZZNZ1Z1Z1EZ1Z1EEZE1E1E1 E1 *EN Ni4.5 (1) First(A)=a, Follow(A)= #,a 不是LL(1)文法 (2) void A() If(sym=a) getsymbol(); A();If(sym=a) getsymbol();Else error();4.6 AB BXBBAB|XaX|bX X aX|bX| void A() if(sym=) getsymbol(); B();void B() X(); if(sym=) getsymbol(); B();void B() if(sym=) A(); getsymbol(); B();void X() if(sym=a) getsymbol(); X();else if(sym=b) getsymbol(); X();else error();4.7(1) Z(L)|aZ|b LZL L,ZL| BdB BbB| (2) First(Z)=(,a,b Follow(Z)=,),# First(L)= (,a,b Follow(L)=),First(L)=, Follow(L)= )First(B )=d Follow(B )=# First(B)=b, Follow(B )=# (3) 4.8(1) ZaPZ|*aPZ Z*aPZ| P+aP PP| (2) First(Z)=a,* Follow(Z)= # First(Z)= *, Follow(Z)=# First(P)=+ Follow(P)= #,*First(P )=+, Follow(P )=#,* (3) 输入非终结符a*+#ZZaPZZ*aPZZ1Z*aPZZPP+aPPP PPP习题5 5.1 分析：先求出FirstVT,LastVT集STFirstVTa b (, a b (LastVTa b ), a b ) (1)算符优先关系表如下：ab(),ab(), (2)因为关系表中无多重定义项，顾是算符优先文法 (3)一种优先函数如下ab(),f22022g44400 5.2 (1)FirstVT,LastVT集如下 STFirstVTa c d a c d ,LastVTb c db c d ,(2)算符优先关系表abcD,abcd,(3)是算符优先文法(4)优先函数abcd,f03332g40331 (5)题目有误aASbbAabAI6:ASA. SA.SS.ASS.bA. SAA.aSI6:SAS. AS.AA.SAA.aS.ASS.bASbbI3: Sb. aI0: S.SS.ASS.bA.SAA.aA.I1: SS. accAS.AA. SAA.aS.ASS.bSSI5: AS.AA. SAA.aS.ASS.bI2:Aa. I4:SA.SS.ASS.bA.SAA.aASaAb5.3 (1)文法要拓广 SS SAS Sb ASA Aa (2) LR(0)分析表状态ACTIONGOTO ab#SA0S2S3141S2S3acc562r5r5r53r3r3r34S2S3745S2S3566S2/r4S3/r4r4747S2/r2S3/r2r256(3)不是LR(0)文法。5.4(1)文法要拓广 SS SASaaaAI2: AAA. SA.SAA.AS.ASS.bA.AAA.aA. SAI2: SA.SAA.AS.ASS.bA.AAA.aA. SI0: S.SS.ASS.bA.AAA.aA. SI1: SS. accI5: SAS. AI4: Aa. I3: Sb. bbb Sb AAA Aa A(2) SLR(1)分析表 先求Follow(S)=# Follow(A)=a,b状态ACTIONGOTO ab#SA0S4/r6S3/r6121acc2S4/r6S3/r6563r34r5r55r26S4/r6/r4S3/r6/r456(3)不是SLR(1)文法。(4)LR(1)项目集族 aaaAI2: AAA . b/a SA . S, #AA . A, b/aS . AS , #S. b , #A . AA , b/a A. a, b/aA . SAI2: SA . S , #AA . A, b/aS. AS , #S. b, #A. AA , b/a A. a , b/aA. , b/a SI0: S. S，#S. AS，#S. b，#A. AA，b/aA. a, b/aA. , b/a SI1: SS.,# accI5: SAS . ,# AI4:Aa. ,b/a I3: Sb . , # bbb(5) LR(1)分析表 状态ACTIONGOTO ab#SA0S4/r6S3/r6121acc2S4/r6S3/r6563r34r5r55r26S4/r6/r4S3/r6/r456(6)不是LR(1)文法。5.5 (1)拓广文法 SA AaAd AaAb A I0: S.AA.aAdA.aAbA. I2: Aa.AdAa.AbA.aAdA.aAbA. I3: AaA.dAaA.bI1: SA . accI5: AaAb. I4:AaAd. AAadba 是SLR(1)文法，其SLR(1)表如下： 状态ACTIONGOTO abd#A0S2r4r4r411acc2S2r4r4r433S5S44r2r2r25r3r3r3 #ab#分析过程：2a0#3A2a0#S2r4 A归约S5S2r3 AaAb归约acc成功 0# 5b3A2a0#3A2a0#2a0#5.6LR(0)项目集族：cI8:B aAc. I9: BaAb. AAb.I2: Ab.Ba B.aAc B.a B.aAbbBabaAI0: S.AA.AbA.bBaI1: SA. accAA.bAbI3: AAb. I4: AbB.a I5: AbBa. I6: Ba.Ac Ba. Ba.Ab A.AbA.bBa I7: BaA.c BaA.b AA.bb 从上述项目集族中，状态集I9是归约-归约冲突。因而不是LR(0)文法。 状态集I6时归约-移进冲突。但在SLR(1)中，Follow(A)=#,b,c Follow(B)=a因而在SLR(1)中，I9与I6的冲突就消失了，因而是SLR(1)文法。5.7 (1)文法拓广： SS SAaAb SBbBa A B SLR(1)项目集族： Follow(A)=a,b Follow(B)=a,bI0:S.S S.AaAb S.BbBa A. B. 在I0种有归约-归约冲突。因而不是SLR(1)文法。 I4:SAa.Ab ,#A.，b aABbabI1:S.S，# accI2:SA.aAb ,#I3:SB.bBa ,#I0:S.S，#S.AaAb，#S.BbBa，#A.，a B. , b SABI5:SBb.Ba ,#B. , a I6:SAaA.b ,#I7:SAaAb. ,# I8:SBbB.a ,#I:SBbBa. ,# (2)LR(1)项目集族：从项目集族中可发现，不存在冲突项。因而是LR(1)文法。 习题66.1 6.2 改造文法。新文法GS如下: SL.R SL LLB LB RBR RB B0 B1 文法GS的S属性文法如下：规则语义规则SL.RS.val=L.val+R.valSLS.val=L.valLL1BL.val= L1.val*2+B.valLBL.val=B.valRBR1R.val=(B.val+ R1.val)*0.5RBR.val=B.val*0.5B0B.val=0B1B.val=16.3 题目有误。加上Tnum规则。 即文法为 GE:ETR R+TR/-TR/ Tnum 只用综合属性翻译方案如下： ETR R+TMR1 R -TMR1 R M print(+) N print(-) T num print(num.lexval)6.4 (1)文法改造如下: GS: S S S (L) S a L L,S L S 给S与L配上继承属性S.level L.level 翻译方案如下：（输出每一个a的嵌套深度） S S.level=0 S S (L.level=S.level+1L) S aprint(S.level) L L1.level=L.levelL1,S.level=L.levelS L S.level=L.level S(2) 打印出每个a在句子中是第几个字符的翻译方案。 指派属性如下： S.pos是继承属性，表示S所代表的字符串的第一个字符的位置 S.len是综合属性，表示S所代表的字符串的长度 L.pos与L.len含义同S 翻译方案如下： S S.pos=1S S (L.pos=S.pos+1L)S.len=L.len+2 S aprint(S.pos)S.len=1 L L1.pos=L.posL1,S.pos=L1+L.len+1SL.len=L1.len+1+S.len L S.pos=L.posSL.len=S.len6.5 语法分析树方法主要步骤：(1) 输入串进行语法分析，构造语法分析树(2) 遍历语法树，确定依赖图(3) 根据依赖图，确定一种语义计算次序(4) 属性计算习题77.1 答：进行语法分析时，当发生归约（或推导）时，自动调用该规则所配置的语义规则，自动进行语义的处理。语义处理的时机，调用何种语义规则，由当时所进行的语法分析所决定。7.2 分析：指派属性E.left表示表达式E是否是左值表达式。若E.left为true，表示是左值。否则是右值表达式。 翻译方案如下： 行号产生式规则语义动作1EE1+E2E.left=false2E(E1)E.left=E1.left3EE1+if(E1.left)E.left=false;elseprint(“Invalid Value in increment”);4EidE.left=true5EnumE.left=false7.3 (1)ab-c+* (2)ab+-cd+*ab+c+- 7.4(1)行号产生式规则语义动作及含义1 EE1?E2:E3E1.true=newlabel;E1.false=newlabel;E1.goto=newlabel;E.place=newTemp;E.code=E1.code|gencode(E1.true,:)|E2.code|gencode(E.place,:=,E2.place)|gencode(goto,E1.goto)|gencode(E1.false,:)|E3.code|gencode(E1.place,:=,E3.place)|gencode(E1.goto,:)(2) a:=x0? x+1:x+2; 翻译如下：（三地址代码） if x0 goto L1 goto L2 L1: T1:=x+1 a := T1 goto L3 L2: T2:=x+2 a := T2 L3: 7.5 (1) Sfor(i=E1;MiE2;Ni+)WS, M N W(2)行号产生式规则语义动作与含义1Sfor(i=E1;MiE2;Ni+)WS,M.label=newlabel;N.label=newlabel;W.label=newlabel;S.code=E1.code|gencode(i,:=,E1.place)|gencode(M.label,:)|E2.code|gencode(if,iE