編譯原理第三版課后答案

1、編譯 原理 課后題答案第二章P36-6(1)L(G1)是09組成的數(shù)字串(2)最左推導(dǎo) :NDNDDNDDDDDDD 0DDD01DD012D0127NDDD3D 34NDNDDDDD5DD56D568最右推導(dǎo) :NDN7ND7N27ND27N127D1270127NDN4D434NDN8ND8N68D68568P36-7G(S)O 1|3|5|7|9N 2|4|6|8|OD 0|NS O|AOA AD | NP36-8文法：E T|E T|E TT F|T*F|T/FF (E)|i最左推導(dǎo) :E ET TTF T i T i T*F i F*Fi i*F i i*iE T T*F F*Fi*

2、Fi *( E) i *( E T) i*( T T) i*( F T)i*( i T) i*(i F) i*( i i)最右推導(dǎo) :E E T E T*F E T*i E F*iE i *i T i *i F i*i i i*iE 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)*語法樹:/*FFiii+i+ii-i-iii+i*i*/P36-9句子iiiei有兩個語法樹：S iSeS iSei iiSei iiieiS iS iiSeS iiSei iiieiP36-10/*S TS

3、|TT (S)|()*/P36-11/*L1:S ACA aAb | abC cC |L2:S ABA aA|B bBc|bcL3:S ABA aAb|B aBb|L4:S A| BA 0A1|B 1B0| A*/第三章習(xí)題參考答案P64 - 71確定化:01X1,2,31,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,101V11最小化： 0,1,2,3,456 0,123,4,5 01,3,50,1,2,3,4,51 1,2,4向0,1,2,3,4, 5,6 0,1,2,3,4 01,3,50,1

4、,2,3,4, 5,6 0,1,2,3。1,30,1,2,311,2,40,1,234, 5,6 0,1 0 1 0,11 1,2 2,30 32,31 40,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 1) |1 0(0|10 1)P64- 12(a) a確定化:ab00,110,10,111r0給狀態(tài)編號:ab012112203333最小化：0,1, 2,30,1 a 1 0,1b 2 a2,30,3 2,3b 3ab0,1, 2, 3aa

5、(b)a已經(jīng)確定化了 ,進行最小化 最小化：0,1, 2,3,4,50,1a 10,1b2,3,4,5a 1,3,0,5-O2,4 2,3,4,5b 2,3,4,5ab2,4a 1,02,4b 3,53,5a 3,53,5b 2,40,1, 2,4, 3,50,1a 10,1b 2,42,4a 1,02,4b 3,53,5a 3,53,5b 2,4aP64- 14(1) 0. ,1 1(2)：一X(010)* MY0”一J f21X1確定化:01X,1,Y1，Y21，Y1，Y22r1,丫給狀態(tài)編號:010121122133330,1,2,30,10 10,11 22,3o 1,32,3i 30

6、，1，2,3第四章P81- 1(1)按照T,S的順序消除左遞歸G (S)S a 1Al(T)T STT ,ST |遞歸子程序: procedure S;beginif sym='a' or sym='A'then abvance else if sym='(' then begin advance;T; if sym=')' then advance;else error;end else error end;procedure T;beginS;Tend;procedure T ;beginif sym=','t

7、hen begin advance; S;Tendend;其中：sym:是輸入串指針I(yè)P所指的符號 advance:是把IP調(diào)至下一個輸入符號 error:是出錯診察程序(2)FIRST(S尸a,A,(FIRST(T尸a,A,(FIRST(T )=,FOLLOW(S)=),#FOLLOW(T)=)FOLLOWT )=)預(yù)測分析表aA(),#SS aS aS (T)Tr T STr T STT STTTT ,ST是LL(1)文法P812文法:E TEEE|TFTTT IFPFF*F|P (E)|a|br FIRST(E尸(,ah> FIRST(E'尸+,£ FIRST(T

8、尸(.ah> FIRST(T')=(,a,b,A,£ FIRST(F)=(,a,b,A FIRST(F尸*,£ FIRST(P)=(,a,b,A FOLLOW(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)生式：E E|TTIF*F |P (E)|A|a|bFIRST(+E) A FIRST( £ )=+

9、A &=() FIRST(+E) A FOLLOW(E')=+ n #,)=() FIRST(T) n FIRST( £ )=(,a,b,A&=()FIRST(T) n FOLLOW(T')=(,a,b,A n +,),#=() FIRST(*F') A FIRST( £ )=* &=()FIRST(*F') n FOLLOW(F')=* n (,a,b,A,+,),#=()FIRST(E) n FIRST(a) n FIRST(b) n FIRST(A)= (j) 所以，該文法式LL(1)文法. +*()ab

10、A#EE TE'E TE'E TE'E TE'E'EEEETT FTT FTT FTT FTT'TT TTT TT TT TTFF PFF PFF PFF PFF'FF *FfF FFFF PP (E)P aP bP A(4) procedure E; beginif sym='(' or sym='a' or sym='b' or sym='A' then begin T; E' end else errorendprocedure E'beginif sy

11、m='+'then begin advance; E endelse if sym<>')' and sym<>'#' then error endprocedure T;beginif sym='(' or sym='a' or sym='b' or sym='A' then begin F; T' end else errorendprocedure T'beginif sym='(' or sym='a'

12、or sym='b' or sym='A' then Telse if sym='*' then errorendprocedure F;beginif sym='(' or sym='a' or sym='b' or sym='A' then begin P; F' end else errorendprocedure F'beginif sym='*'then begin advance; F' endendprocedure P;begi

13、nif sym='a' or sym='b' or sym='A' then advance else if sym='(' thenbeginadvance; E;if sym=')' then advance else errorendelse errorend;P813/*(2)(4)是，滿足三個條件。不是，對于A不滿足條件3。不是，A、B均不滿足條件3。 是，滿足三個條件。*/第五章P133- 1E E T E 短語：E+T*F, T*F, 直接短語：T*F 句柄：T*FT* FP133- 2文法：S a|

14、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 ,(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), S)S (T)(T,S)(T,(T)(T,(T,S)(T,(T,a)

15、(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/，(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,(

16、 a),a)(T,( S),a)(T,( T),a)(TS),a)(IL，a)(S,a)(IS)(I)S“移進-歸約”過程:步驟棧輸入串動作0#(a,a),A,(a),a)#預(yù)備1#(a,a),A,(a),a)#進2#(a,a),A,(a),a)#進3#(a,a),A,(a),a)#進4#(a,a),A,(a),a)#進5#(S,a),A,(a),a)#歸6#(I,a),A,(a),a)#歸7#(I,a)F,(a),a)#進8#(I,a),A,(a),a)#進9#(I,S),A,(a),a)#歸10#(I),A,(a),a)#歸11#(I),A,(a),a)#進12#(S,A,(a),a)#歸

17、13#(I,A,(a),a)#歸14#(I,A,(a),a)#進15#(I,a,(a),a)#進16#(I)S,(a),a)#歸17#(I,(a),a)#歸18#(I,(a),a)#進19#(I,(a),a)#進20#(I,(a),a)#進21#(I,(S),a)#歸22#(I,(I),a)#歸23#(I,(I),a)#進24#(I)S),a)#歸25#(I),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-3FIRSTVT(S尸a,A,(F

18、IRSTVT(T尸,a,A,(LASTVT(S尸a/,)LASTVT(T尸“a。)(2)aA(),a>>A>>(<<<=<)>>,<<<>>G6是算符文法，并且是算符優(yōu)先文法優(yōu)先函數(shù)aA(),f44244g55523(4)預(yù)備棧輸入字符串動作# (a,(a,a) # (a, (a,a)#進# (a, (a,a)#進# (t, (a,a)#歸# (t,(a,a) ) #進# (t,(a,a) #進# (t, (a,a) #進# (t, (t,a) #歸# (t, (t,a) #進# (t, (t,a)#進#

19、 (t, (t,s)#歸# (t, (t)#歸# (t, (t)#進# (t,s)#歸# (t)#歸# (t)#進# s#歸success0. S4. S8. AP134 5AS 3. S A S7. A SA11. A aS 1. S S 2. SAS 5. Sb 6. s bS A9. ASA 10. A a確定化:SAab0,2,5,7,101,2,5,7,8,10 2,3,5,7,101161,2,5,7,8,102,5,7,8,102,3,5,7,9,101162,3,5,7,102,4,5,7,8,10 2,3,5,7,101162,5,7,8,102,5,7,8,102,3,5,

20、7,9,10 1162,3,5,7,9,10 2,4,5,7,8,10 2,3,5,7,101162,4,5,7,8,10 2,5,7,8,102,3,5,7,9,10 116116Io=S S, SGO(10, a)= A GO(I o , b)= S GO(I。，S)= SDFA構(gòu)造LR(0)項目集規(guī)范族也可以用 GO函數(shù)來計算得到。所得到的項目集規(guī)范族與上圖中的項目集一樣：AS, S b, A SA, A aa = 11b = I 2AS, Sb= I3S , A SA, A SA, A a, SGO(I 0 ，A)=SA S，SAS，Sb， ASA，Aa = I 4GO(I 3 ，a)

21、=Aa=I1GO(I 3 ，b)=Sb=I2GO(I 3 ，S)=AS A ，SAS，Sb， ASA，Aa = I 5GO(I 3 ，A)=ASA ，SA S，SAS ， Sb，ASA ， Aa = I6GO(I 4 ，a)=Aa=I1GO(I 4 ，b)=Sb=I2GO(I 4 ，S)=SAS ，AS A ，SAS ， Sb，ASA ， Aa = I7GO(I 4 ，A)=SA S，SAS，Sb， ASA，Aa = I 4GO(I 5 ，a)=Aa=I1GO(I 5 ，b)=Sb=I2GO(I 5 ，S)=AS A ，SAS，Sb， ASA，Aa = I 5GO(I 5 ，A)=ASA ，S

22、A S，SAS ， Sb，ASA ， Aa = I6GO(I 6 ，a)=Aa=I1GO(I 6 ，b)=Sb=I2GO(I 6 ，S)=SAS ，AS A ，SAS ， Sb，ASA ， Aa = I7GO(I 6 ，A)=SA S，SAS，Sb， ASA，Aa = I 4GO(I 7 ，a)=Aa=I1GO(I 7 ，b)=Sb=I2GO(I 7 ，S)=AS A ，SAS，Sb， ASA，Aa = I 5GO(I 7 ，A)=ASA ，SA S，SAS ， Sb，ASA ， Aa = I6項目集規(guī)范族為C=I1， I2，I3 ， I4，I5，I6， I7不是SLR文法狀態(tài) 3， 6， 7

23、 有移進歸約沖突狀態(tài) 3： FOLLOW(S)=# 不包含 a,b狀態(tài) 6： FOLLOW(S)=#,a,b 包含 a,b, ；移進歸約沖突無法消解狀態(tài)7： FOLLOW(A尸a,b包含a,b ;移進歸約沖突消解所以不是SLR文法。(4) 構(gòu)造例如 LR(1) 項目集規(guī)范族見下圖：對于態(tài)5,因為包含項目A AS a/b,所以遇到搜索符號a或b時，應(yīng)該用A AS歸約。又因為狀態(tài)5 包含項目 A a a/b ，所以遇到搜索符號a 時，應(yīng)該移進。因此存在“移進- 歸約”矛盾，所以這個文法不是LR(1) 文法。bZ5:SAa/b8:a/bSa/ba/bASa/bSAa/bASa/ba/bASAS#/a

24、/b#/a/bSAb a/ba a/b2：ASSAa/ba/ba/ba/bSAa/bA3 :AaA a/b4:S b #/a/b#/a/b#/a/b#/a/ba/ba/bSAa/ba/ba/b3：6:AS Aa/bASAa/bAaa/bSASa/bSba/b .9：ASSAASa/ba/ba/ba/ba/ba/baA7:SAS#/a/bAS Aa/bASAa/bAaa/bSASa/bSba/bbA10：S b a/b5:/*第六章會有點難第六章P164 5E E1 + T if (El.type = int) and (T.type = int) then E.type := int else

25、 E.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;L.length:=L1.length+1LBL.val:=B.c;L.length :=1B0B.c:=0B1B.c:=1*/第七章P217- 1abcde/+*+A CDa*(-b+c) a+b*(c+d/e) -a+b*(-c+d)A (C D)(A B) ( C D)AB

26、CD(A B) (C D E)AB CDET b T c xy+z*0= ab+c T abc T TT P2 jump abc T Tif (x+y)*z =0 then (a+b)T c else a或 xy+z*0= P1 jez ab+cP1 P2P217- 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

27、(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自下而上分析過程中把賦值句翻譯成四元式的步驟: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

28、)*(-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 -D 1A-B- T2 A-B- T - A-B- T 22A- T3(20) A(16) )(17)(18)(19)產(chǎn)生的四元式：(,C,-, T )(+, T1,D, T

29、2)(*,B, T , T )(:=, T3,-,A)P218- 5/*i:=E(E i:=E*(E) i:=E+E i:=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:=T9T10T12:= i + jT13:=D 4

30、T14:=4*T12T15:= T13T14T16:=T11+T15T17:=C WT18:=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)106. (jnz, D, -, 104) -107. (j, -, -, 100) -假鏈：106,104 ， 103真鏈：107,100P218-7100. (j&l

31、t;, 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/*(

32、1)MAXINT - 5MAXINT - 4MAXINT - 3MAXINT - 2MAXINT - 1MAXINT(2)翻譯模式方法1：for E1 := E2 to E3 do SSFdo MS1FFor I : E1 to E2IidMSFdo MS1backpatch(S1.nextlist,nextquad);backpatch(F.truelist,M.quad);emit(F.place ' := ' F.place '+' 1);emit( 'j ,' F.place ',' F.end ', '

33、M.quad); S.nextlist := F.falselist;F For I : E1 to E2 F.falselist:= makelist(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; I idp:=looku

34、p();if p <> nil then I.place := p else error MM.quad := nextquad*/方法2:Sf for id:=E1 to E2 do S1Sf F S1Ff for id:=E1 to E2 doF forid : E1toE2doINITIAL=NEWTEMP;emit( ' := ,' E1.PLACE，-, ' INITIAL);FINAL=NEWTEMP;emit( ' := ,' E2.PLACE，-, ' FINAL);p:= nextquad+2;emit

35、( 'j ,' INITIAL ',' FINAL ' ,' p);F.nextlist:=makelist(nextquad);emit( 'j,一,一,');F.place:=lookup();if F.placenil thenemit(F.place'k'INITIAL)F.quad:=nextquad;F.final:=FINAL;S FS1backpatch(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, 一 , 一,