陳火旺編譯原理課后習(xí)題答案

1、第二章P36-6(1)L(G1)是 09 組成的數(shù)字串(2)最左推導(dǎo):NDNDNDNDD NDDDDD 3D 34NDD最右推導(dǎo):NNDN 7NNDN4NNDN8DDDD 0DDD01DD012D0127DDD 5DD 56D568ND 7 N 27D 434ND 8 N 68ND27 N127D68568D1270127P36-7G(S)O 1|3|5|7| 9N 2|4|6|8|OD0| NSO| 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*Fi F*F i i*F i i*iE T T*F

2、F*Fi*( i T) i*(i F)i* F i *( E) i *( E T) i *( i i )i *( T T) i *( F T)最右推導(dǎo):E E T E T*FE T*i E F*iE i*i T i*iF i*i i i*iE T F*T F*FF *( E ) F *( E T)F *( E F ) F *( E i )語(yǔ)法樹：F *( T i )F *( F i )F *( i i ) i *( i i )/*Eii+i+ii-i-iii+i*i*/P36-9句子iiiei有兩個(gè)語(yǔ)法樹：S iSeS iSei iiSei iiieiS iS iiSeS iiSei iiie

3、iP36-10/*S TS |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(01) 1010確定化:01101X1,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,最小化:0,1,2,3,4,5,60,123,4,5 01,3,50,1,2,3,431,2,4向0,1,2,3,4, 5,60,1

4、,2,3,4 01,3,50,1,2,3,4, 5,60,1,2,3。1,30,1,2,311,2,40,1,234, 5,60,1 0 1 0,11 1,22,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,1110給狀態(tài)編號(hào):ab012112203333最小化：0,1, 2,30,1 a 1 0,1b 2 a2,30,3 2,3b 3ab0

5、,1, 2, 3aa已經(jīng)確定化了，進(jìn)行最小化最小化:0,1, 2,3,4,50,1a 10,1b 2,42,3,4,5a 1,3,0,52,3,4,5b 2,3,4,52,4a 1,02,4b 3,53,5a 3,53,5b 2,40,1, 2,4, 3,50,1a2,4a3,5a11,03,50,1b 2,42,4b3,5b3,52,4P64 14-01X,1,Y1,Y2確定化：1，Y1，Y221，Y給狀態(tài)編號(hào):01012112213333最小化：0,1,2,30,10 10,11 22,3o 1,32,3i 30，1，2,3第四章P81- 1(1)按照T,S的順序消除左遞歸G(S)Sa1A

6、l(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;end;procedure ;beginif sym=','then begin advance; S;endend;其中：sym:是輸入串指針I(yè)P所

7、指的符號(hào) advance:是把IP調(diào)至下一個(gè)輸入符號(hào) error:是出錯(cuò)診察程序(2)FIRST(S尸叱,(FIRST(T尸aF,(FIRST()=, FOLLOW(S)=),# FOLLOW(T)=) FOLLOW()=) 預(yù)測(cè)分析表aA(),#ST是LL(1)文法P812文法:E TEEE|TFTTT IFPFF*F|P (E)|a|brFIRST(E尸(,ah>FIRST(E'尸+,£ FIRST(T尸(.ah>FIRST(T')=(,a,b,A,£ FIRST(F)=(,a,b,AFIRST(F尸*,£ FIRST(P)=(,a

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

9、T(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)文法. +*()abA#EE TE'E TE'E TE'E TE'E'EEEETT FTT FTT FTT FTT'TT TTT TT TT TTFF PFF P

10、FF 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 sym='+'then begin advance; E endelse if sym<>')' and sym<>'#'

11、 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' or sym='b' or sym='A' then Telse if sym='*' then errorendprocedure F;be

12、ginif 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;beginif sym='a' or sym='b' or sym='A' then advance else if sym='('

13、thenbeginadvance; E;if sym=')' then advance else errorendelse errorend;P813/*(2)(4)是，滿足三個(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)

14、(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)(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

15、)(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,( a),a)(T,( S),a)(T,( T),a)(TS),a)(IL，a)(S,a)(IS)(I)S“移進(jìn)-歸約”過(guò)程:步驟棧輸入串動(dòng)作0#(a,a),A,(a),a)#預(yù)備1#(a,a

16、),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)#歸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#

17、(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)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>>(<<<=<)>>,

18、<<<>>G6是算符文法，并且是算符優(yōu)先文法優(yōu)先函數(shù)(4)棧輸入字符串動(dòng)作# (a,(a,a) # (a, (a,a)#進(jìn)# (a, (a,a)#進(jìn)# (t, (a,a)#歸預(yù)備aA(),f44244g55523#(t,#(t,(#(t,(a#(t,(t#(t,(t,#(t,(t,a#(t,(t,s#(t,(t#(t,(t)#(t,s#(t#(t)#ssuccess(a,a) ) #進(jìn)a,a) #進(jìn),a) #進(jìn),a) #歸a) #進(jìn))#進(jìn))#歸)#歸)#進(jìn))#歸)#歸#進(jìn)#歸P134 50. S4. S8. AS 1. S S 2. SAS 5. Sb 6. s

19、bS A9. ASA 10. A aAS 3. S A S7. A SA11. A a(2)確定化: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,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 116116構(gòu)造LR(0)項(xiàng)目集規(guī)范族也可以用 項(xiàng)目

20、集一樣：I0=S S, S AS, SGO(I o, a)=Aa= IiGO(10, b)= Sb= 12GO。，S)= S S , ADFAGO函數(shù)來(lái)計(jì)算得到。所得到的項(xiàng)目集規(guī)范族與上圖中的b, A SA, A aS A, A SA, A a, S AS, S b= 13GO（I 0， A）=SA S，SAS，Sb， ASA，Aa = I 4GO（I 3 ， a）=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 = I 6GO（I 4， a）=Aa=I1G

21、O（I 4， b）=Sb=I2GO（I 4， S）=SAS ，AS A，SAS， Sb，ASA，Aa = I 7GO（I 4， A）=SA S，SAS，Sb， ASA，Aa = I4GO（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 ，SA S，SAS， Sb，ASA，Aa = I 6GO（I 6， a）=Aa=I1GO（I 6， b）=Sb=I2GO（I 6， S）=SAS ，AS A，SAS， Sb，ASA，Aa = I 7GO（I 6， A）=SA S，SAS，Sb， AS

22、A，Aa = I4GO（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 = I 6項(xiàng)目集規(guī)范族為C= I 1 ， 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)歸約沖突消解所以不是SLR文法。(4) 構(gòu)造例如LR(1) 項(xiàng)目集

23、規(guī)范族見下圖：對(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:SAa/b8:a/ba/ba/bASa/bSAa/bASa/ba/bASAS#/a/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：9：a/bASa/bSAa/ba/ba/bSAa/bASa/ba/ba

24、/bASa/ba/b7:SAS#/a/bAS Aa/bASAa/bAaa/bSASa/bSba/bb10：S b a/b5:/*第六章會(huì)有點(diǎn)難第六章P164 5E E1+T if = int) and = int ) then := int else := realET := := realTnum := int(2)P164-7SL1|L2:=+2 L2.length)SL:=LL1B:=2* + ;:=+1LB:=;:=1B0:=0B1:=1*/第七章abc+* abcde/+*+ abcd+*+A CDP217- 1a*(-b+c) a+b*(c+d/e) -a+b*(-c+d)A (C

25、 D)(A B) ( C D)AB CD(A B) (C D E)AB CDEif (x+y)*z =0 then (a+b)T c else a或 xy+z*0= P1 jez ab+cT b T c xy+z*0= ab+c T abc T T ¥T P2 jump abc T TP1 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

26、(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)步驟輸入串棧PLACE四元式(1)A:=B*(-C+D)(2):=B*(-C+D)iA(3)B*(-C+D)i:

27、=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,-, T )(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 1(+, T ,D, T )(16)(17)i:=E(E i:=E*(E)A-B- T2 A-B- T

28、-(18)i:=E+EA-B- T 22(*,B, T , T )(19)產(chǎn)生的四元式：(,C,-, T )(+, T1,D, T2) (*,B, T , T )(:=, T3,-,A)P218 5i:=EA- T3(20) A(:=, T ,-,A)/*設(shè) A : 10*20, B、G D: 20,寬度為 w= 4 則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

29、12:= i + jT13:=D - 4T14:=4*T12T15:= T13T14T16:=T11+T15T17:=C 4T18:=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)假鏈鏈?zhǔn)渍骀滄準(zhǔn)?05. (j, -, -, 106)106. (jnz, D, -, 104) -107. (j, -, -, 100) -假鏈：106,104 ， 103真鏈：10

30、7,100P218-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,

31、-, - 100)P219- 12/*(1)MAXINT - 5MAXINT - 4MAXINT - 3MAXINT - 2MAXINT - 1MAXINT(2)翻譯模式方法1：for E1 := E2 to E3 do SS F do MS1F For I : E1 to E2I idMS F do MS1 backpatch,nextquad);backpatch,;emit k''+' 1);emit( 'j ,'','',':=; F For I : E1 to E2:= makelist(nextquad);em

32、it( 'j>, '', '',0');emit 'k':=makelist(nextquad);emit( 'j,-,-,-');:=;:=;I idp:=lookup;if p <> nil then :=p else error M := nextquad*/ 方法2:Sf for id:=E1 to E2 do S1Sf F S1Ff for id:=E1 to E2 doF forid : E1toE2doINITIAL=NEWTEMP;emit( ':=,'',

33、 - / INITIAL);FINAL=NEWTEMP;emit( ':=,'', - / FINAL);p:= nextquad+2;emit( 'j ,' INITIAL ',' FINAL ' ,' p); kmakelist(nextquad);emit( ' j,一,一,'); :=lookup;if nil thenemit 'k'INITIAL) :=nextquad;kFINAL;S FS1backpatch, nextquad)p:=nextquad+2;emit( 'j , '', '' , ' p );:=merge, makelist(nextquad);emit( j,一,一,');emit( ' succ ,'',-,'emit( ' j,一,一,'第九章P270-9傳名但必須將其中出現(xiàn)的即當(dāng)過(guò)程調(diào)用時(shí)，其作用相當(dāng)于把被調(diào)用段的過(guò)程體抄到調(diào)用出現(xiàn)處, 任一形式參數(shù)都代之以相應(yīng)