編譯原理第三版課后習(xí)題解答

1、P36-6(1)L(G1)是09組成的數(shù)字串(2)最左推導(dǎo):NDNDDNDDDNDDD3D34NDNDDDDD最右推導(dǎo):NDN7ND7NDN4D4NDN8ND8P36-7G(S)1|3|5|7|92|4|6|8|O0|NO|AOAD|NP36-8文法：T|EF|T*(E)|iT|EF|T/F最左推導(dǎo):EETTETT*Fi*(iT)*(iF)最右推導(dǎo):EETETEF*TT*FF*FF*(Ti)F*(Fi)第二章習(xí)題解答DDDD0DDD01DD012D01275DD56D568N27ND27N127D127012734N68D68568TiTiT*FF*i*ii*Fi*(iT*(E)i*(T)i*

2、(TT)*(FT)*(E)F*(iEF*F*(EiT)i*iF*(Ti*iF)FF*(Ei*ii)i*i語(yǔ)法樹：/*i)i*(ii)ETFiEFFiETFiii+i+ii-i-iii+i*i*/P36-9句子iiiei有兩個(gè)語(yǔ)法樹：SiSeSiSeiiiSeiiiieiSiSiiSeSiiSeiiiieiP36-10/*STS|TT(S)|()*/P36-11/*L1:SACAaAb|abCcC|L2:SABAaA|BbBc|bcL3:SABAaAb|BaBb|L4:SA|BA0A1|B1B0|A*/第三章習(xí)題參考答案P64-71(01) 101Ly；0確定化:01X1,2,31,2,32,3

3、2,3,42,32,32,3,42,3,42,3,52,3,42,3,52,32,3,4,Y2,3,4,Y2,3,52,3,4,最小化:0,1,2,3,4,5,60,123,4,501,3,50,1,2,3,431,2,4向0,1,2,3,4,5,60,1,2,3,401,3,50,1,2,3,4,5,60,1,2,3。1,30,1,2,311,2,40,1,234,5,60,1010,111,22,3032,3140,1,2,3,4,5,6P64-8*(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)0*1(0|10*

4、1)*|1*0(0|10*1)*P64-12(a)a確定化:ab00,110,10,1110給狀態(tài)編號(hào):ab012112203333最小化：0,1,2,30,1a10,1b2a2,30,32,3b3ab0,1,2,3aa已經(jīng)確定化了，進(jìn)行最小化最小化:0,1,2,3,4,50,1a10,1b2,42,3,4,5a1,3,0,52,3,4,5b2,3,4,52,4a1,02,4b3,53,5a3,53,5b2,40,1,2,4,3,50,1a10,1b2,42,4a1,02,4b3,53,5a3,53,5b2,4P64-14確定化:01X,1,Y1,Y21，Y1，Y221，Y給狀態(tài)編號(hào):0101

5、2112213333最小化：0,1,2,30,1010,1122,3o1,32,3i30，1，2,3第四章P81-1(1)按照T,S的順序消除左遞歸G(S)Sa1Al(T)TSTT,ST|遞歸子程序：procedureS;beginifsym='a'orsym='A'thenabvanceelseifsym='('thenbeginadvance;T;ifsym=')'thenadvance;elseerror;endelseerrorend;procedureT;beginS;Tend;procedureT;beginifsym

6、=','thenbeginadvance;S;Tendend;其中：sym:是輸入串指針I(yè)P所指的符號(hào)advance:是把IP調(diào)至下一個(gè)輸入符號(hào)error:是出錯(cuò)診察程序(2)FIRST(S尸叱,(FIRST(T尸aF,(FIRST(T)=,FOLLOW(S)=),#FOLLOW(T)=)FOLLOWT)=)預(yù)測(cè)分析表aA(),#SSaSaS(T)TrTSTrTSTTSTTTT,ST是LL(1)文法P812文法:ETEEE|TFTTTIFPFF*F|P(E)|a|brFIRST(E尸(,ah>FIRST(E'尸+,£FIRST(T尸(.ah>FIR

7、ST(T')=(,a,b,A,£FIRST(F)=(,a,b,AFIRST(F尸*,£FIRST(P)=(,a,b,AFOLLOW(E尸#,)FOLLOW(E'尸#,)FOLLOW(T尸+,),#FOLLOW(T'尸+,),#FOLLOW(F)=(,a,b,A,+.),#FOLLOW(F')=(,a,b,A,+.),#FOLLOW(P)=*,(,a,b,A,+.),#(2)考慮下列產(chǎn)生式：EE|TTIF*F|P(E)|A|a|bFIRST(+E)AFIRST(£)=+A&=()FIRST(+E)AFOLLOW(E')

8、=+n#,)=()FIRST(T)nFIRST(£)=(,a,b,A&=()FIRST(T)nFOLLOW(T')=(,a,b,An+,),#=()FIRST(*F')AFIRST(£)=*&=()FIRST(*F')nFOLLOW(F')=*n(,a,b,A,+,),#=()FIRST(E)nFIRST(a)nFIRST(b)nFIRST(A)=(j)所以，該文法式LL(1)文法.+*()abA#EETE'ETE'ETE'ETE'E'EEEETTFTTFTTFTTFTT'TTT

9、TTTTTTTTFFPFFPFFPFFPFF'FF*FfFFFFFPP(E)PaPbPA(4)procedureE;beginifsym='('orsym='a'orsym='b'orsym='A'thenbeginT;E'endelseerrorendprocedureE'beginifsym='+'thenbeginadvance;Eendelseifsym<>')'andsym<>'#'thenerrorendprocedureT

10、;beginifsym='('orsym='a'orsym='b'orsym='A'thenbeginF;T'endelseerrorendprocedureT'beginifsym='('orsym='a'orsym='b'orsym='A'thenTelseifsym='*'thenerrorendprocedureF;beginifsym='('orsym='a'orsym='b'o

11、rsym='A'thenbeginP;F'endelseerrorendprocedureF'beginifsym='*'thenbeginadvance;F'endendprocedureP;beginifsym='a'orsym='b'orsym='A'thenadvanceelseifsym='('thenbeginadvance;E;ifsym=')'thenadvanceelseerrorendelseerrorend;P813/*(2)(4)是，滿

12、足三個(gè)條件。不是，對(duì)于A不滿足條件3。不是，A、B均不滿足條件3。是，滿足三個(gè)條件。*/第五章P133- 1E E T E 短語(yǔ)：E+T*F, T*F, 直接短語(yǔ)：T*F 句柄：T*FT* FP133- 2文法：S a|A|(T)T T,S|S最左推導(dǎo)：S (T)(T,S)S (T,S)(S,S)(T,S),S,S), S) (a,a),A ,S),S) (a,a),A ,(a), a)最右推導(dǎo)：(S,S)(a,S)(a,(T)(a,(T,S)(T),S)(T,S),S)(T,S,S),S)(S,S),S,S),S)(a,S),S,S),S)(a,a),A ,(T), S) ( a,a),A

13、,(S),S)(a,(S,S)(a,(a,S)(a,(a,a)(S,S,S),S)(T),S,S),S)(a,a),S,S),S)(a,a),A ,(a),S)S (T)(T,S)(T,(T)(T,(T,S)(T,(T,a)(T,(S,a)(T,(a,a)(S,(a,a)S (T,S) (T,(a), a)(a,(a,a)(T,a)(S,a)(T),a)(T,S),a)(T,(T), a)(T,S,(a), a)(T,A,(a),a)(SJ ,(a), a)(T,(S), a)(T),"(a),a)(T,S/，(a),a)(T,a),A,(a),a)(S,a/，(a),a)(a,a/

14、，(a),a)(2)(a,a)F,(a),a)(S,a)F,(a),a)(T,a/,(a),a)(TS,(a),a)(T)，A，(a)，a)(S，A,(a),a)(T,A,(a),a)(TS，(a)，a)(T,(a),a)(T,(S),a)(T,(T),a)(TS),a)(IL，a)(S,a)(IS)(1)S“移進(jìn)-歸約”過(guò)程:步驟棧輸入串動(dòng)作0#(a,a),A,(a),a)#預(yù)備1#(a,a),A,(a),a)#進(jìn)2#(a,a),A,(a),a)#進(jìn)3#(a,a),A,(a),a)#進(jìn)4#(a,a),A,(a),a)#進(jìn)5#(S,a),A,(a),a)#歸6#(I,a),A,(a),a)#歸

15、7#(I,a)F,(a),a)#進(jìn)8#(I,a),A,(a),a)#進(jìn)9#(I,S),A,(a),a)#歸10#(I),A,(a),a)#歸11#(I),A,(a),a)#進(jìn)12#(S,A,(a),a)#歸13#(I,A,(a),a)#歸14#(I,A,(a),a)#進(jìn)15#(I,a,(a),a)#進(jìn)16#(I)S,(a),a)#歸17#(I,(a),a)#歸18#(I,(a),a)#進(jìn)19#(I,(a),a)#進(jìn)20#(I,(a),a)#進(jìn)21#(I,(S),a)#歸22#(I,(I),a)#歸23#(I,(I),a)#進(jìn)24#(I)S),a)#歸25#(I),a)#歸26#(T),a)#進(jìn)

16、27 #(S,a)#歸28 #(T,a)#歸29 #(T,a)#進(jìn)30 #(T,a)#進(jìn)31 #(T,S)#歸32 #(T)#歸33 #(T)#進(jìn)34 #S#歸P133-3FIRSTVT(S尸a,A,(FIRSTVT(T尸,a,A,(LASTVT(S尸a/,)LASTVT(T尸“a。)(2)aA(),a>>A>>(<<<=<)>>,<<<>>G6是算符文法，并且是算符優(yōu)先文法優(yōu)先函數(shù)aA(),f44244g55523(4)預(yù)備棧輸入字符串動(dòng)作# (a,(a,a)# (a,(a,a)#進(jìn)# (a,(a,a)

17、#進(jìn)# (t,(a,a)#歸#(t,(a,a)#進(jìn)#(t,(a,a)#進(jìn)#(t,(a,a)#進(jìn)#(t,(t,a)#歸#(t,(t,a)#進(jìn)#(t,(t,a)#進(jìn)#(t,(t,s)#歸#(t,(t)#歸#(t,(t)#進(jìn)#(t,s)#歸#(t)#歸#(t)#進(jìn)#s#歸success0. S4. S8. AP1345AS 3. S A S7. A SA11. A aS1.SS2.SAS5.Sb6.sbSA9.ASA10.Aa確定化:SAab0,2,5,7,101,2,5,7,8,102,3,5,7,101161,2,5,7,8,102,5,7,8,102,3,5,7,9,101162,3,5,7,

18、102,4,5,7,8,102,3,5,7,101162,5,7,8,102,5,7,8,102,3,5,7,9,101162,3,5,7,9,102,4,5,7,8,102,3,5,7,101162,4,5,7,8,102,5,7,8,102,3,5,7,9,10116116Io=S S, SGO(10, a)= A GO(I o , b)= S GO(I。，S)= SDFA構(gòu)造LR(0)項(xiàng)目集規(guī)范族也可以用GO函數(shù)來(lái)計(jì)算得到。所得到的項(xiàng)目集規(guī)范族與上圖中的項(xiàng)目集一樣：AS,Sb,ASA,Aaa=11b=I2AS, Sb= I3S,ASA,ASA,Aa,SGO(I0，A)=SAS，SAS，S

19、b，ASA，Aa=I4GO(I3，a)=Aa=I1GO(I3，b)=Sb=I2GO(I3，S)=ASA，SAS，Sb，ASA，Aa=I5GO(I3，A)=ASA，SAS，SAS，Sb，ASA，Aa=I6GO(I4，a)=Aa=I1GO(I4，b)=Sb=I2GO(I4，S)=SAS，ASA，SAS，Sb，ASA，Aa=I7GO(I4，A)=SAS，SAS，Sb，ASA，Aa=I4GO(I5，a)=Aa=I1GO(I5，b)=Sb=I2GO(I5，S)=ASA，SAS，Sb，ASA，Aa=I5GO(I5，A)=ASA，SAS，SAS，Sb，ASA，Aa=I6GO(I6，a)=Aa=I1GO(I6

20、，b)=Sb=I2GO(I6，S)=SAS，ASA，SAS，Sb，ASA，Aa=I7GO(I6，A)=SAS，SAS，Sb，ASA，Aa=I4GO(I7，a)=Aa=I1GO(I7，b)=Sb=I2GO(I7，S)=ASA，SAS，Sb，ASA，Aa=I5GO(I7，A)=ASA，SAS，SAS，Sb，ASA，Aa=I6項(xiàng)目集規(guī)范族為C=I1，I2，I3，I4，I5，I6，I7不是SLR文法狀態(tài)3，6，7有移進(jìn)歸約沖突狀態(tài)3：FOLLOW(S)=#不包含a,b狀態(tài)6：FOLLOW(S)=#,a,b包含a,b,；移進(jìn)歸約沖突無(wú)法消解狀態(tài)7：FOLLOW(A尸a,b包含a,b;移進(jìn)歸約沖突消解所以

21、不是SLR文法。(4)構(gòu)造例如LR(1)項(xiàng)目集規(guī)范族見(jiàn)下圖：對(duì)于態(tài)5,因?yàn)榘?xiàng)目AASa/b,所以遇到搜索符號(hào)a或b時(shí)，應(yīng)該用AAS歸約。又因?yàn)闋顟B(tài)5包含項(xiàng)目Aaa/b，所以遇到搜索符號(hào)a時(shí)，應(yīng)該移進(jìn)。因此存在“移進(jìn)-歸約”矛盾，所以這個(gè)文法不是LR(1)文法。bZ5:SAa/b8:a/bSa/ba/bASa/bSAa/bASa/ba/bASAS#/a/b#/a/bSAba/baa/b2：ASSAa/ba/ba/ba/bSAa/bA3:AaAa/b#/a/b#/a/b#/a/ba/ba/bSAa/ba/ba/b3：6:ASAa/bASAa/bAaa/bSASa/bSba/b.4:Sb#/a/

22、b9：ASSAASa/ba/ba/ba/ba/ba/baA7:SAS#/a/bASAa/bASAa/bAaa/bSASa/bSba/bbA10：Sba/b5:/*第六章會(huì)有點(diǎn)難第六章P1645EE1+Tif(El.type=int)and(T.type=int)thenE.type:=intelseE.type:=realETE.type:=T.typeTnum.numT.type:=realTnumT.type:=int(2)P164-7SL1|L2S.val:=L1.val+(L2.val/2L2.length)SLS.val:=L.valLL1BL.val:=2*L1.val+B.val

23、;L.length:=L1.length+1LBL.val:=B.c;L.length:=1B0B.c:=0B1B.c:=1*/第七章P2171a*(-b+c) a+b*(c+d/e) -a+b*(-c+d)A CDabc+*abcde/+*+abcd+*+A(CD)(AB)(CD)ABCD(AB)(CDE)ABCDET b T c xy+z*0= ab+c T abc T TT P2 jump abc T Tif(x+y)*z=0then(a+b)Tcelsea或xy+z*0=P1jezab+cP1P2P217-3-(a+b)*(c+d)-(a+b+c)的三元式序列:(1) +,a,b(2)

24、 ,(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,T1(2) ,T1,-,T2(3) +,c,d,T3(4) *,T2,T3,T4(5) +,a,b,T5(6) +,T5,c,T6(7) -,T4,T6,T7P2184自下而上分析過(guò)程中把賦值句翻譯成四元式的步驟:A:=B*(-C+D)

25、步驟輸入串棧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(12)+D)i:=E*(EA-B-T1A-B-T-1A-B-T-D1(13)D)i:=E*(E+(14)i:=E*(E+i(15)i:=E*(E+EA-B-T-D1A-B-T2A-B-T-A

26、-B-T22A-T3(20)A(16) )(17)(18)(19)產(chǎn)生的四元式：(,C,-,T)(+,T1,D,T2)(*,B,T,T)(:=,T3,-,A)P218-5/*i:=E(Ei:=E*(E)i:=E+Ei:=E設(shè)A：10*20，B、C、D：20，寬度為寬度為w=4則(,C,-,T1)(+,T1,D,T2)(*,B,T,T)(:=,T,-,A)T1:=i*20T1:=T1+jT2:=A-84T3:=4*T1Tn:=T2T3/這一步是多余的T4:=i+jT5:=B-4T6:=4*T4T7:=T5T6T8:=i*20T8:=T8+jT9:=A-84T10:=4*T8T11:=T9T10T

27、12:=i+jT13:=D4T14:=4*T12T15:=T13T14T16:=T11+T15T17:=CWT18:=4*T16T19:=T17T18T20:=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)假鏈鏈?zhǔn)渍骀滄準(zhǔn)?06. (jnz,D,-,104)-107. (j,-,-,100)-假鏈：106,104，103真鏈：107,100P218-7100. (j<,A,C,102)101. (j

28、,-,-,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-3MAXINT-2MAXINT-1MAXINT(2)翻譯模式方法1：forE1:=E2t

29、oE3doSSFdoMS1FForI:E1toE2IidMSFdoMS1backpatch(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;FForI:E1toE2F.falselist:=makelist(nextquad);emit('j>,'E1.place&#

30、39;,'E2.place',0');emit(I.Place':='E1.place);F.truelist:=makelist(nextquad);emit('j,-,-,-');F.place:=I.place;F.end:=E2.place;Iidp:=lookup();ifp<>nilthenI.place:=pelseerrorMM.quad:=nextquad*/方法2:Sfforid:=E1toE2doS1SfFS1Ffforid:=E1toE2doFforid:E1toE2doINITIAL=N

31、EWTEMP;emit(':=,'E1.PLACE，-,'INITIAL);FINAL=NEWTEMP;emit(':=,'E2.PLACE，-,'FINAL);p:=nextquad+2;emit('j,'INITIAL','FINAL','p);F.nextlist:=makelist(nextquad);emit('j,一,一,');F.place:=lookup();ifF.placenilthenemit(F.place'k'INITIAL)F

32、.quad:=nextquad;F.final:=FINAL;SFS1backpatch(S1.nextlist,nextquad)p:=nextquad+2;emit('j,'F.place','F.final','p);S.nextlist:=merge(F.nextlist,makelist(nextquad);emit('j,一,一,');emit('succ,'F.place-,'F.place);emit('j,一,一,'F.quad);第九章P270-9傳名即當(dāng)過(guò)程調(diào)用時(shí)，其作用相當(dāng)于把被調(diào)用段的過(guò)程體抄到調(diào)用出現(xiàn)處，但必須將其中出現(xiàn)的任一形式參數(shù)都代之以相應(yīng)的實(shí)在參數(shù)。A:=2;B:=3;A:=A+1;A:=A+(A+B);printA;.A