編譯原理第三版課后答案

1、編譯 原理課后題答案第二章P36-6L（G）是o9組成的數(shù)字串最左推導(dǎo)：NNDNDDNDDDDDDD0DDD01DD012D0127NNDDD3D 34NNDNDDDDD5DD56D568最右推導(dǎo):NNDN7ND 7N27ND 27N127D1270127NNDN4D4 34NNDN8ND 8N68D68568P36-7G(S)O 1|3|5|7|9N 2|4|6|8|0D 0|NS 0|A0A AD |NP36-8文法：ET E T|E TTF T* F|T/ FF (E)|i最左推導(dǎo):EET TT FT iT i T* F i F* F ii*F i i*iETT* F F * F i *

2、 Fi*( E) i *(E T) i *( T T) i *( F T)i*( i T) i *( i F) i *( i i)最右推導(dǎo):E T F*T F * F F*(E)F*( E T)F*( E F) F*( E i)F*( T i) F*( F i) F*( i i) i *( i i)語(yǔ)法樹(shù):ii+i+iii+i*i*P36-9句子iiiei有兩個(gè)語(yǔ)法樹(shù):2 siseis s e s ssee sP36-10/*S TS |TT (S)|()*/P36-11/*L1:S ACA aAb | abC cC |L2:S ABA aA|B bBc|bcL3:S ABA aAb|B aB

3、b|L4:S A| BA 0A1|B 1B0| A*/第三章習(xí)題參考答案P64 71(01)*1010確定化:01X01,2,30001,2,32,32,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,V1 1最小化：010,1,2,3,4,5,60,123,4,5。1,3,5。，侔件1,2,40,1,2,3,4, 5,60,123,4。1,3,50,1,23,4, 5,60,1,23。1,30,1,2,311,2,40,1,2,04, $,60,1 0 1 0,11 1,22,30 B 門(mén)匡40,1,2,3, 4,

4、5, 6P64 - 8(1)(1|0)*01 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*1)* |1*0(0|10*1)P64 - 12aa0bbb2a確定化:ab00,110,10,111r00000ab012112203333給狀態(tài)編號(hào):a最小化：0,1, 2,30,1 a 1 0,1b 2 2,3a 0,32,3b 30,1, 2, 3(b)已經(jīng)確定化了，進(jìn)行最小化 最小化：0,1, 2,3,4,50,1a 10,1b 2,42,3,4,52,3,4,5a 1,3,0,52,3,4,5b2,4a 1,02,4b

5、3,53,5a3,53,5b 2,40,1, 2,4, 3,50,1a 12,4a 1,03,5a 3,50,1b 2,42,4b 3,53,5b 2,4:確定化:01X,1,Y1,Y21，Y1,Y22r1,y0 000給狀態(tài)編號(hào):01012112213333最小化：0,1，2,30,10 1 0,11 22,3o 1,32,3i 30,1,2,3P81 - 1(1)按照T,S的順序消除左遞歸G (S)S aF| 仃)T STT ,ST |遞歸子程序:procedure S;beginif sym=a or sym=人the n abva nee else if sym=( the n beg

6、i nadvance;T;if sym=) the n adva nee; else error;endelse erroren d;procedure T;beginS;Ten d;procedure T ;beginif sym=,the n begi nadvanee; S;T end en d;其中：sym:是輸入串指針I(yè)P所指的符號(hào) advanee:是把IP調(diào)至下一個(gè)輸入符號(hào) error:是出錯(cuò)診察程序FIRST(S)=a,(FIRST(T)=af,(FIRST(T )=,FOLLOW(S)=),#FOLLOW(T)=)FOLLOW )=)預(yù)測(cè)分析表aA()J#SS aS AS (T

7、)Tr T STr T STT STTTT ,ST是LL(1)文法P81 - 2文法:E TEEE|TFTTT |FPFF*F|P (E)|a|b$(1)FIRST(E)=(,a,bfFIRST(E)=+, FIRST(T)=(,a,bFIRST(T)=(,a,b,A, FIRST(F)=(,a,b,AFIRST(F)=*, FIRST(P)=(,a,bfFOLLOW(E)=#,)FOLLOW(E)=#,)FOLLOW(T)=+,),#FOLLOW(T)=+,),#FOLLOW(F)=(,a,b,A,+,),#FOLLOW(F)=(,a,b,A,+,),#FOLLOW(P)=*,(,a,bf,

8、+,),#考慮下列產(chǎn)生式：E E|TT|F*F |P(E)|A|a|bFIRST(+E) A FIRST( )=+ n = $FIRST(+E) A FOLLOW(E)=+ A #,)=$FIRST(T) A FIRST( )=(,a,b,AA = $FIRST(T) A FOLLOW(T)=(,a,b,A A +,),#=$FIRST(*F) A FIRST( )=* A = $FIRST(*F) A FOLLOW(F)=* A (,a,b,A,+,),#=$FIRST(E) A FIRST(a) A FIRST(b) A FIRST(A)= $ 所以,該文法式LL(1)文法.+*()abA

9、#EE TEE TEE TEE TEEEEEETT FTT FTT FTT FTTTT TTT TT TTTTFFPFFPFFPFF PFFFF *FFFFFFF :PP(E)PaPbP Aprocedure E;beginif sym=( or sym=a or sym=b or sym=人 the n beg in T; E end else errorendprocedure E：beginif sym=+the n beg in adva nee; E endelse if sym) and sym# then error endprocedure T;beginif sym=( or

10、 sym=a or sym=b or sym=人 the n beg in F; T end else errorendprocedure T;beginif sym=( or sym=a or sym=b or sym=人 the n Telse if sym=* then errorendprocedure F;beginif sym=( or sym=a or sym=b or sym=人 the n beg in P; F end else errorendprocedure F;beginif sym=*the n beg in adva nee; F endendprocedure

11、 P;beginif sym=a or sym=b or sym=Athe n adva neeelse if sym=( the nbeginadvanee; E;if sym=) the n adva nee else error end else erroren d;P81 3/*(1) 是，滿(mǎn)足三個(gè)條件。(2) 不是，對(duì)于A不滿(mǎn)足條件3。(3) 不是，A、B均不滿(mǎn)足條件3。(4) 是，滿(mǎn)足三個(gè)條件。*/第五章P133- 1E E T E T* F短語(yǔ)：E+T*F, T*F,直接短語(yǔ)：T*F 句柄:T*FP133-2文法:(1)最左推導(dǎo):(a,(S,S)(a,(a, S)(a,(a,a)

12、(S,S,S),S)(T),S,S),S)(a,a),S,S),S)(a,a)T ,(a),S)S (T)(T,S)(S,S)(a,S)(a,(T)(a,(T,S)S (T,S)(S,S)(T),S)(T,S),S)(T,S,S),S)(T,S),S, S), S) ( S,S), S,S), S) (a,S),S,S),S)(a,a)T ,S),S)(a,a)T,(T), S) (a,a),A ,( S), S)(a,a)T ,(a), a)最右推導(dǎo):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

13、,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)(a,a),A,(a),a)(S0,(a),a)(T, a),A,(a),a) (LSV，(a),a)(TL，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

14、，a)(S，a)(TS)(T)_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#(T,a),A,(a),a)#歸7#(T，a),A,(a),a)#進(jìn)8#(T，a),A,(a),a)#進(jìn)9#(T，S),A,(a),a)#歸10#(T),A,(a),a)#歸11#(T),A,(a),a)#進(jìn)12#(S,A,(a),a)#歸13#(T,A,(a),a)#歸14#(T，A,(a),a)#進(jìn)1

15、5#(T，a,(a),a)#進(jìn)16#(T,S,(a),a)#歸17#(T,(a),a)#歸18#(T，(a),a)#進(jìn)19#(T，(a),a)#進(jìn)20#(T，(a),a)#進(jìn)21#(T，(S),a)#歸22#(T，(T),a)#歸23#(T，(T),a)#進(jìn)24#(T,S),a)#歸25#(T),a)#歸26#(T),a)#進(jìn)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-3(1)FIRSTVT(S)=a,( FIRSTVT(T)=,a】,( LASTVT(S)=a,) LASTVT(T)

16、=,a】,) aA()5aA(=5G6是算符文法，并且是算符優(yōu)先文法(3)優(yōu)先函數(shù)aA()5f44244g55523(4)棧輸入字符串動(dòng)作#(a,(a,a) ) #預(yù)備#(a, (a,a)#進(jìn)#(a,(a,a)#進(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#歸successP134-5(1)0.SS1.S

17、S2. SAS3.SA S4.SAS 5.Sb6. Sb7.ASA8.AS A9.ASA10.A a11.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,10112,3,5,7,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,1011611000060000SAAsAssbAAA

18、7sAsSAAsbSAaAsSASAaSasssSAAsbi aAsbSAa1GO函數(shù)來(lái)計(jì)算得到。所得到的項(xiàng)目集規(guī)范族與上圖中的AS, Sb= 13項(xiàng)目集樣：10 = ss，sAS， S b， ASA，A aGO(I o，a)= Aa = IiGO(I o，b)= Sb = 12GO(I o，S)= SS，A S A，ASA，A a，SDFA構(gòu)造LR(O)項(xiàng)目集規(guī)范族也可以用G0（| 0，A）=SA S，SAS，Sb，ASA，Aa = 14GO（13，a）=Aa=I1G0（| 3，b）=Sb=I 2GO（13，S）=AS A，SAS，Sb，ASA，Aa= I5G0（| 3，A）=ASA，SA

19、S，SAS，Sb，ASA，Aa = I 6G0（| 4，a）=Aa=I1G0（| 4，b）=Sb=I 2G0（| 4，S）=SAS，AS A，SAS，Sb，ASA，Aa = I7G0（I 4，A）=SA S，SAS，Sb，ASA，Aa = 14G0（15，a）=Aa=I1G0（15，b）=Sb=I 2G0（I 5，S）=AS A，SAS，Sb，ASA，Aa = 15G0（l5，A）=ASA，SA S，SAS，Sb，ASA，Aa = I 6G0（16，a）=Aa=I1G0（16，b）=Sb=I 2G0（I 6，S）=SAS，AS A，SAS，Sb，ASA，Aa = 17GOg，A）=SA S，S

20、AS，Sb，ASA，Aa = 14G0（17，a）=Aa=I1G0（17，b）=Sb=I 2G0（I 7，S）=AS A，SAS，Sb，ASA，Aa = 15G0（l7，A）=ASA，SA S，SAS，Sb，ASA，Aa = I 6項(xiàng)目集規(guī)范族為C= 11， I2， II 3， I 4，I5，I 6， I 7不是SLR文法狀態(tài)3, 6, 7有移進(jìn)歸約沖突狀態(tài) 3: FOLLOW)=#不包含 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)歸約沖突消解所以不是SLR文法。(4)構(gòu)造例如LR(1)項(xiàng)目集規(guī)范族見(jiàn)下

21、圖：對(duì)于狀態(tài)5，因?yàn)榘?xiàng)目A AS a/b，所以遇到搜索符號(hào)a或b時(shí)，應(yīng)該用A AS 歸約。又因?yàn)闋顟B(tài) 5包含項(xiàng)目A a a/b，所以遇到搜索符號(hào) a時(shí)，應(yīng)該移進(jìn)。因此 存在“移進(jìn)-歸約”矛盾，所以這個(gè)文法不是LR(1)文法。5:ASAa/bSA Sa/bSASa/bSba/bASAa/bAaa/b8:SA Sa/bSASa/bSba/bASAa/bAaa/b0：aSS#SAS#/a/bSb#/a/bASAba/bAaa/b4:S b #/a/b6:AS Aa/bASAa/bAaa/bSASa/bSba/b -9:SASa/bAS Aa/bASAa/bAaa/bSASa/bSba/b2:7:

22、SA S#/a/bSAS#/a/bSAS#/a/bAS Aa/bS#/a/bbASAa/bASAa/bAaa/bAaa/bSASa/bSba/bA/*第六章會(huì)有點(diǎn)難第六章P164 5(1)E E1 + T if (El.type = in t) a nd (type = int ) then E.type := int else E.type := realETE.type:=T.typeTnum.num T.type := realTnum T.type := intP164-7SL1|L2S.val:=L1.val+(L2.val/2L2.length SLS.val:=L.valLL1B

23、L.val:=2*L1.val + B.val;L.le ngth:=L1.le ngth+1LBL.val:=B.c;L.le ngth :=1B0B.c:=0B1B.c:=1*/第七章P217- 1a*(-b+c) a+b*(c+d/e) -a+b*(-c+d)abc+* abcde/+*+ abcd+*+A(C D)ACD(AB) ( C D)ABCD(AB) (CD E)ABCDEif (x+y)*z =0 then (a+b)f c else af b f c xy+z*0= ab+c f abc ff 或 xy+z*O= P1 jez ab+cf P2 jump abc ffP1

24、P2P217- 3-(a+b)*(c+d)-(a+b+c) 的 三元式序列：(1) +, a, b , (1),- +, c, d(4) *, (2), (3) +, a, b(6) +, (5), c(7) -, (4), (6)間接三元式序列：(1) +, a, b , (1),- +, c, d(4) *, (2), (3)(5) +, (1), c(6) -, (4), (5)間接碼表：(1)(1)四元式序列：(1) +, a, b,T1 , T1, -,T2 +, c, d,T3*, T2, T3, T4 +, a, b,T5 +, T5, c,T6-,T4, T6, T7P218-

25、4自下而上分析過(guò)程中把賦值句翻譯成四兀式的步驟:A:=B*(-C+D)步驟輸入串棧PLACE四兀式(1)A:=B*(-C+D):=B*(-C+D)iAB*(-C+D)i:=A-*(-C+D)i:=iA-B*(-C+D)i:=EA-B*(-C+D)i:=E(-C+D)i:=E*(8)-C+D)i:=E*(9)C+D)i:=E*(-(10)+D)i:=E*(-i(11)+D)i:=E*(-E(12)+D)i:=E*(E(13)D)i:=E*(E+(14)i:=E*(E+iA-BA-B-A-B-A-B-A-BCA-BC(15)(16)(17)(18)(19)=E*(E+E =E(E =E*(E) =

26、E+ET1T -1T -D1T -D1T2T -2A-B-A-B-A-B-A-B-A-B-A-B-=EA-B- T2A-T3(20) A(,C,-, T1)(+, T1 ,D,T2)(*,B, T ,2(:=,T ,-,A)3T3)產(chǎn)生的四元式：(,C,-, T )1 (+, T1,D, T2) (*,B, T , T ) 23(:=，T3,-,A)P218-5/*設(shè) A : 10*20 , B、C、 D: 20,寬度為w = 4T1:= i * 20T1:=T1+jT2:=A -84T3:=4*T1Tn:=T2T3這T4:= i + jT5:=B 步是多余的T6:=4*T4T7:=T5T6T

27、8:= i * 20T8:=T8+jT9:=A -84T10:=4*T8T11:=T9T10T12:= i + jT13:=D -T14:=4*T12T15:= T13T14T16:=T11+T15T17:=C T18:=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

28、. (j, -, -, 100)- 假鏈：106,104 , 103 真鏈：107,100P218-7100.(j, A, C, 102)101.(j, -, -, 0)102.(j, El.place , E2.place ,0 ); emit(I.Place := El.place);F.truelist := makelist (n extquad); emit( j,-,-,-);F.place := I.place;F.e nd := E2.place;I idp:=lookup(id. name);if p nil the nI.place := pelse errorMM.qua

29、d := nextquad*/方法2:St for id:=E1 to E2 do S1St F S1Ft for id:=E1 to E2 doF forid : EltoE 2doINITIAL=NEWTEMP;emit( :=， E1.PLACE，-， INITIAL); FINAL=NEWTEMP;emit( :=， E2.PLACE，-， FINAL); p:= n extquad+2;p);emit( j , INITIAL , FINAL F.n extlist:=makelist (n extquad);emit( j,);F.place:=lookup(id. name);i

30、f F.placenil the nemit(F.place := INITIAL)F.quad:=n extquad;F.fi nal:=FINAL;S FS1backpatch(S1. nextlist, n extquad)p:=n extquad+2;emit( j , F.place , F.final , p );S.n extlist := merge(F. nextlist, makelist (n extquad); emit( j,);emit( succ， F.place-， F.place);emit( j, , , F.quad);第九章P270-9(1)傳名即當(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); print A; A=9傳地址即當(dāng)程序控制轉(zhuǎn)入被調(diào)用段后，被調(diào)用段首先把實(shí)在參數(shù)抄進(jìn)相應(yīng)的形式參數(shù)的形式單元中，