编译原理课后习题答案(陈火旺+第三版)2129

编译原理课后习题答案(陈火旺+第三版)第二章P36-6(1)L(G)是0~9组成的数字串1(2)最左推导:NNDNDDNDDDDDDD0DDD01DD012D0127NNDDD3D34NNDNDDDDD5DD56D568最右推导:NNDN7ND7N27ND27N127D1270127NNDN4D434NNDN8ND8N68D68568P36-7G(S)O1|3|5|7|9N2|4|6|8|OD0|NSO|AOAAD|NP36-8文法：ET|ET|ETTF|T*F|T/FF(E)|i最左推导:EETTTFTiTiT*FiF*Fii*Fii*iETT*FF*Fi*Fi*(E)i*(ET)i*(TT)i*(FT)i*(iT)i*(iF)i*(ii)

最右推导:EETET*FET*iEF*iEi*iTi*iFi*iii*iETF*TF*FF*(E)F*(ET)F*(EF)F*(Ei)F*(Ti)F*(Fi)F*(ii)i*(ii)语法树：/********************************EEEE+TE-TE+TE+TFE-TFT*FTFiTFiFiTFiFiFiiiii+i+ii-i-ii+i*i*****************/P36-9句子iiiei有两个语法树：SiSeSiSeiiiSeiiiieiSiSiiSeSiiSeiiiieiP36-10/**************STS|TT(S)|()***************/11011确定化：01{X}φφφ{1,2,3}φ{1,2,3}{2,3}{2,3,4}{2,3}{2,3}{2,3,5}{2,3,4}{2,3,4}{2,3,4}{2,3,5}{2,3}{2,3,4,Y}{2,3,4,Y}{2,3,5}{2,3,4,}010023001101045610111最小化：{0,1,2,3,4,5},{6}{0,1,2,3,4,5}{,13,5}{0,1,2,3,4,5}{,12,4,6}01{0,1,2,3,4},{}5,{6}{0,1,2,3,4}{,13,5}{0,1,2,3},{4},{}5,{6}{0,1,2,3}{,13}{0,1,2,3}{1,2,4}{0,1},{2,3}{4},{5},{6}{0,1}{1}{0,1}{1,2}{2,3}{3}{2,3}{4}{0},{1},{2,3},{4},{5},{6}0010101010200110100345111P64–8(1)(1|0)*01(2)(1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*(0|5)|(0|5)(3)0*1(0|10*1)*|1*0(0|10*1)*P64–12(a)aa,b01a确定化：ab{0}{0,1}{1}{0,1}{0,1}{1}{1}φ{0}φφφ给状态编号：a1103b22330123aa01ab23bbba最小化：{0,1},{2,3}{0,1}{}1{0,1}{2}{2,3}a{0,3}{2,b3}{}3{0,1},{a2},{3}baab120bab(b)bb023aabaabb145aaa已经确定化了,进行最小化最小化：{{0,1},{2,3,4,5}}{0,1}{1}{0,1}{2,4}ab{2,3,4,5}{1,3,0,5}{2,3,4,5}{2,3,4,5}ab{2,4}{1,0}{2,4}{3,5}ab{3,5}{3,5}{3,5}{2,4}a{{0,1},{2,4},{3,5}}b{0,1}{1}{0,1}{2,4}ab{2,4}{1,0}{2,4}{3,5}ab{3,5}{3,5}{3,5}{2,4}abb12b0aabaP64–14(1)01001(2):XY(0|10)*2011YX0确定化：01{X,1,Y}{1,Y}{2}{1,Y}{1,Y}{2}{2}{1,Y}φφφφ给状态编号：01113122330123001010123110最小化：{0,1},{2,3}{0,1}{1}{0,1}{2}01{2,3}{1,3}{2,3}{3}0{0,1},{2},{3}1011013100第四章P81–1(1)按照T,S的顺序消除左递归G(S)Sa|^|(T)TSTT,ST|递归子程序：procedureS;beginifsym='a'orsym='^'thenabvanceelseifsym='('thenbeginadvance;T;ifsym=')'thenadvance;elseerror;endelseerrorend;procedureT;beginS;Tend;procedure;Tbeginifsym=','thenbeginadvance;S;Tendend;其中:sym:是输入串指针IP所指的符号advance:是把IP调至下一个输入符号error:是出错诊察程序

(2)FIRST(S)={a,^,(}FIRST(T)={a,^,(}FIRST()={,,}TFOLLOW(S)={),,,#}FOLLOW(T)={)}FOLLOW()={)}T预测分析表a^(),#SSaS^S(T)TTSTTSTTSTTTT,ST是LL(1)文法P81–2文法：ETEEE|TFTTT|FPFF*F|P(E)|a|b|^(1)FIRST(E)={(,a,b,^}FIRST(E')={+,ε}FIRST(T)={(,a,b,^}FIRST(T')={(,a,b,^,ε}FIRST(F)={(,a,b,^}FIRST(F')={*,ε}FIRST(P)={(,a,b,^}FOLLOW(E)={#,)}FOLLOW(E')={#,)}FOLLOW(T)={+,),#}FOLLOW(T')={+,),#}FOLLOW(F)={(,a,b,^,+,),#}FOLLOW(F')={(,a,b,^,+,),#}FOLLOW(P)={*,(,a,b,^,+,),#}(2)考虑下列产生式:EE|TT|F*F|P(E)|^|a|bFIRST(+E)∩FIRST(ε)={+}∩{ε}=φFIRST(+E)∩FOLLOW(E')={+}∩{#,)}=φFIRST(T)∩FIRST(ε)={(,a,b,^}∩{ε}=φFIRST(T)∩FOLLOW(T')={(,a,b,^}∩{+,),#}=φ

FIRST(*F')∩FIRST(ε)={*}∩{ε}=φFIRST(*F')∩FOLLOW(F')={*}∩{(,a,b,^,+,),#}=φFIRST((E))∩FIRST(a)∩FIRST(b)∩FIRST(^)=φ所以,该文法式LL(1)文法.(3)+*()ab^#EETE'ETE'ETE'ETE'E'TEEEETFTTFTTFTTFTT'FTTTTTTTTTTTFPFFPFFPFFPFF'PFF*FFFFFFFP(E)PaPbP^(4)procedureE;beginifsym='('orsym='a'orsym='b'orsym='^'thenbeginT;E'endelseerrorendprocedureE';beginifsym='+'thenbeginadvance;Eendelseifsym<>')'andsym<>'#'thenerrorendprocedureT;beginifsym='('orsym='a'orsym='b'orsym='^'thenbeginF;T'endelseerrorendprocedureT';beginifsym='('orsym='a'orsym='b'orsym='^'thenTelseifsym='*'thenerrorend

procedureF;beginifsym='('orsym='a'orsym='b'orsym='^'thenbeginP;F'endelseerrorendprocedureF';beginifsym='*'thenbeginadvance;F'endendprocedureP;beginifsym='a'orsym='b'orsym='^'thenadvanceelseifsym='('thenbeginadvance;E;ifsym=')'thenadvanceelseerrorend

elseerrorend;P81–3/***************(1)是，满足三个条件。(2)不是，对于A不满足条件3。(3)不是，A、B均不满足条件3。(4)是，满足三个条件。***************/第五章P133–1EETET*F短语:E+T*F,T*F,直接短语:T*F句柄:T*FP133–2文法：Sa|^|(T)TT,S|S(1)最左推导:S(T)(T,S)(S,S)(a,S)(a,(T))(a,(T,S))(a,(S,S))(a,(a,S))(a,(a,a))S(T,S)(S,S)((T),S)((T,S),S)((T,S,S),S)((S,S,S),S)(((T),S,S),S)(((T,S),S,S)),S)(((S,S),S,S),S)(((a,S),S,S),S)(((a,a),S,S),S)(((a,a),^,S),S)(((a,a),^,(T)),S)(((a,a),^,(S)),S)(((a,a),^,(a)),S)(((a,a),^,(a)),a)

最右推导:S(T)(T,S)(T,(T))(T,(T,S))(T,(T,a))(T,(S,a))(T,(a,a))(S,(a,a))(a,(a,a))S(T,S)(T,a)(S,a)((T),a)((T,S),a)((T,(T)),a)((T,(S)),a)((T,(a)),a)((T,S,(a)),a)((T,^,(a)),a)((S,^,(a)),a)(((T),^,(a)),a)(((T,S),^,(a)),a)(((T,a),^,(a)),a)(((S,a),^,(a)),a)(((a,a),^,(a)),a)(2)(((a,a),^,(a)),a)(((S,a),^,(a)),a)(((T,a),^,(a)),a)(((T,S),^,(a)),a)(((T),^,(a)),a)((S,^,(a)),a)((T,^,(a)),a)((T,S,(a)),a)((T,(a)),a)((T,(S)),a)((T,(T)),a)((T,S),a)((T),a)(S,a)(T,S)(T)S“移进-归约”过程：步骤栈输入串动作0#(((a,a),^,(a)),a)#预备1#(((a,a),^,(a)),a)#进2#(((a,a),^,(a)),a)#进3#(((a,a),^,(a)),a)#进4#(((a,a),^,(a)),a)#进5#(((S,a),^,(a)),a)#归6#(((T,a),^,(a)),a)#归7#(((T,a),^,(a)),a)#进8#(((T,a),^,(a)),a)#进9#(((T,S),^,(a)),a)#归10#(((T),^,(a)),a)#归11#(((T),^,(a)),a)#进12#((S,^,(a)),a)#归13#((T,^,(a)),a)#归14#((T,^,(a)),a)#进15#((T,^,(a)),a)#进16#((T,S,(a)),a)#归17#((T,(a)),a)#归18#((T,(a)),a)#进19#((T,(a)),a)#进20#((T,(a)),a)#进21#((T,(S)),a)#归22#((T,(T)),a)#归23#((T,(T)),a)#进24#((T,S),a)#归25#((T),a)#归26#((T),a)#进27#(S,a)#归28#(T,a)#归29#(T,a)#进30#(T,a)#进31#(T,S)#归32#(T)#归33#(T)#进34#S#归P133–3(1)FIRSTVT(S)={a,^,(}FIRSTVT(T)={,,a,^,(}LASTVT(S)={a,^,)}LASTVT(T)={,,a,^,)}(2)

a^(),>>a^>>(<<<=<)>>,<<<>>是算符文法，并且是算符优先文法G6(3)优先函数a^(),f44244g55523ffff)a^(f,gag^g(g)g,（4）栈输入字符串动作#（a,(a,a)）#预备#(a,(a,a))#,(a,a))#进#(a进#(t,(a,a))#归进#（t,(a,a)）##（t,（a,a））#进#（t,（a#（t,（t#（t,（t,#（t,（t,a#（t,（t,s#（t,（t,a））#进,a））#归a））#进））#））#））#进归归进#（t,（t））##（t,s#（t）#）#归归#（t）#进#s#归successP134–5(1)0.1.SS2.3.SASSSSAS4.SAS5.Sb6.7.ASASb

8.ASA9.ASA10.Aa11.Aa(2)1S789AaS110A2534Sd6确定化：SAab{0,2,5,{1,2,5,{2,3,5,{11}{6}7,10}7,8,10}7,10}{1,2,5,{2,5,7,{2,3,5,{11}{6}7,8,10}8,10}7,9,10}{2,3,5,{2,4,5,{2,3,5,{11}{6}7,10}7,8,10}7,10}{2,5,7,{2,5,7,{2,3,5,{11}{6}8,10}8,10}7,9,10}{2,3,5,{2,4,5,{2,3,5,{11}{6}7,9,10}7,8,10}7,10}{2,4,5,{2,5,7,{2,3,5,{11}{6}7,8,10}8,10}7,9,10}{11}φφφφφφφ{6}φASA3:5:6:ASASASSASSbASASASSbSSSASAASAAaASAaASAbSaASbSAbaA0:4:7:SSSASSbSASSASSbSASASASASSbAASAASASbaabba1:2:DFA构造LR(0)项目集规范族也可以用GO函数来计算得到。所得到的项目集规范族与上图中的项目集一样:={，，，，}GIO(S，aS)={SASS}=}=abASAAa0AGO(I，b)={I0012GO(I，S)={SS，bI，，，，SI}=ASAASAAaSASSb0IGO(，A)={，，，，}=3SAAaGO(GO(GO(GO(IIIII，a)={，b)={，S)={}=ASSbA}=aISASS03334AI1，bI，，，}=S2SASSbASbSAAaASA5I，，A)={ASA，，，，ASASASSAS}=Aa3IGO(，a)={}=6A}=aGO(III，b)={I41GO(，S)={，bI，，，，SASASSbASAS4A2SAS}=4AaGO(，A)={，，，，}=I7SAAaGO(GO(GO(GO(IIIII，a)={，b)={，S)={}=ASSbA}=aSASSI4555}=54AI1，bI，，，}=S2SASSbASbSAAa，A)={ASA，，，，，IASASASSASASA5AaGO(，Ia)={}=，b6aGO(，b)={}=IIA612GO(，S)={I，，，，IS6ASAASASAS}=SASSbIa6GO(，AI)={，，，，Aa}=A7SASSASSbASA}=}=IIGO(，a)={I64GO(GO(GO(IIII，b)={Aa7771，，，，}=I2SASSbASAAaI，S)={，A)={，，，，，ASA5ASASASSASSbASASb}=7AaI6

项目集规范族为C={，，，，，，}IIIIIII1234675(3)不是SLR文法状态3，6，7有移进归约冲突状态3：FOLLOW(S’)={#}不包含a,b状态6：FOLLOW(S)={#,a,b}包含a,b,；移进归约冲突无法消解状态7：FOLLOW(A)={a,b}包含a,b；移进归约冲突消解所以不是SLR文法。(4)构造例如LR(1)项目集规范族见下图：对于状态5，因为包含项目[AASa/b]，所以遇到搜索符号a或b时，应该用AAS归约。又因为状态5包含项目[Aaa/b]，所以遇到搜索符号a时，应该移进。因此存在“移进-归约”矛盾，所以这个文法不是LR(1)文法。

bbb1：5：8：SS#ASAa/bSASa/bASAa/bASAa/bSASa/bSASa/bSASa/bSbASAa/bAaa/bAAAaSASa/bSba/bSba/bASAa/ba/bAAaa/ba/bSaaS3：SaaS0：3：aSS#SAS#/a/bSb#/a/bASAa/bAaa/bAAa9：6：ASAa/bASAa/bSASa/bASAa/bASAa/b4：Aaa/bSASa/bSAaa/bSASa/bSbSb#/a/bSba/bba/bSaASbabb2：7：SAS#/a/bASAa/bASAa/bSAS#/a/bSAS#/a/bSbASAa/bAa#/a/bAaSASa/bSba/b10：a/bSa/bSba/bbAA5：第六章/********************第六章会有点难P164–5(1)EE1＋T{if(E1.type=int)and(T.type=int)thenE.type:=intelseE.type:=real}ET{E.type:=T.type}Tnum.num{T.type:=real}Tnum{T.type:=int}(2)P164–7SL1|L2{S.val:=L1.val+(L2.val/2)}L2.lengthSL{S.val:=L.val}LL1B{L.val:=2*L1.val+B.val;L.length:=L1.length+1}LB{L.val:=B.c;L.length:=1}B0{B.c:=0}B1{B.c:=1}

***********************/第七章P217–1a*(-b+c)ab@c+*a+b*(c+d/e)-a+b*(-c+d)A(CD)abcde/+*+a@bc@d+*+ACD(AB)(CD)ABC@D(AB)(CDE)ABCD@Eif(x+y)*z=0then(a+b)↑celsea↑b↑cxy+z*0=ab+c↑abc↑↑￥或xy+z*0=P1jezab+c↑P2jumpabc↑↑P1P2P217–3-(a+b)*(c+d)-(a+b+c)的三元式序列:(1)+,a,b(2)@,(1),-(3)+,c,d(4)*,(2),(3)(5)+,a,b(6)+,(5),c(7)-,(4),(6)间接三元式序列:三元式表：(1)+,a,b(2)@,(1),-(3)+,c,d(4)*,(2),(3)(5)+,(1),c(6)-,(4),(5)间接码表：(1)(2)(3)(4)(1)(5)(6)

四元式序列:(1)+,a,b,(2)@,,-,T1T(3)+,c,d,T12(4)*,,,T3T(5)+,a,b,TT234T(6)+,,c,5(7)-,,,T6TT5TT467P218–4自下而上分析过程中把赋值句翻译成四元式的步骤:A:=B*(-C+D)步骤输入串栈PLACE四元式(1)A:=B*(-C+D)(2):=B*(-C+D)iA(3)B*(-C+D)i:=A-(4)*(-C+D)i:=iA-B(5)*(-C+D)i:=EA-B(6)*(-C+D)i:=EA-B(7)(-C+D)i:=E*A-B-(8)-C+D)i:=E*(A-B--(9)C+D)i:=E*(-A-B---(10)+D)i:=E*(-iA-B---C(11)+D)i:=E*(-EA-B---C(@,C,-,)(12)+D)i:=E*(EA-B--T1(13)D)i:=E*(E+A-B---T1(14))i:=E*(E+iA-B---DT1(15))i:=E*(E+EA-B---D(+,,D,)T1(16))i:=E(EA-B--TT1T21(17)i:=E*(E)A-B--T2-T2

(18)(19)(20)i:=E+EA-B-(*,B,,)i:=EA-(:=,,-,A)T2TT23ATT33产生的四元式：(@,C,-,)(+,,D,T)1T(*,B,,)T123A)(:=,T2,-,TT3P218–5/****************设A：10*20，B、C、D：20，宽度为w＝4则T1:=i*20T1:=T1+jT2:=A–84T3:=4*T1Tn:=T2[T3]//这一步是多余的T4:=i+jT5:=B–4T6:=4*T4T7:=T5[T6]T8:=i*20T8:=T8+jT9:=A–84T10:=4*T8T11:=T9[T10]T12:=i+j

T13:=D–4T14:=4*T12T15:=T13[T14]T16:=T11+T15T17:=C–4T18:=4*T16T19:=T17[T18]T20:=T7+T19Tn:=T20******************/P218–6100.(jnz,A,-,0)101.(j,-,-,102)102.(jnz,B,-,104)103.(j,-,-,0)104.(jnz,C,-,103)105.(j,-,-,106)106.(jnz,D,-,104)--假链链首107.(j,-,-,100)--真链链首假链：{106,104，103}真链：{107,100}

P218–7100.(j<,A,C,102)101.(j,-,-,0)102.(j<,B,D,104)103.(j,-,-,101)104.(j=,A,‘1’,106)105.(j,-,-,109)106.(+,C,‘1’,T1)107.(:=,T1,-,C)108.(j,-,-,100)109.(j≤,A,D,111)110.(j,-,-,100)111.(+,A,‘2’,T2)112.(:=,T2,-,A)113.(j,-,-,109)114.(j,-,-100)P219–12/********************(1)MAXINT–5MAXINT–4MAXINT–3

MAXINT–2MAXINT–1MAXINT(2)翻译模式方法1：forE1:=E2toE3doSSFdoMS1FForI:EtoE12IidMSFdoMS1{backpatch(S1.nextlist,nextquad);backpatch(F.truelist,M.quad);emit(F.place‘:=’F.place‘+’1);emit(‘j,’F.place‘,’F.end‘,’M.quad);S.nextlist:=F.falselist;}{F.falselist:=FForI:EtoE12makelist(nextquad);emit(‘j>,’E1.place‘,’E2.place‘,0’);

emit(I.Place‘:=’E1.place);F.truelist:=makelist(nextquad);emit(‘j,-,-,-’);F.place:=I.place;F.end:=E2.place;}{p:=lookup();ifp<>nilthenIidI.place:=pelseerror}{M.quad:=nextquad}M****************/方法2：S→forid:=E1toE2doS1S→FS1F→forid:=E1toE2doFforid:E1toE2do{INITIAL=NEWTEMP;emit(‘:=，’E1.PLACE’，-，’INITIAL);FINAL=NEWTEMP;

emit(‘j,’INITIAL‘,’FINAL’,’emit(‘j,’F.place‘,’F.final’,’p);S.nextlist:=merge(F.nextlist,makelist(nextquad));emit(‘j,－,－,－’);emit(‘succ，’F.place’，