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

1、第二章習(xí)題解答 P36-6 (1) L(Gi)是o9組成的數(shù)字串 (2) 最左推導(dǎo) : N ND NDD NDDD DDDD 0DDD 01DD 012D 0127 N ND DD 3D 34 N ND NDD DDD 5DD 56D 568 最右推導(dǎo) : N ND N7 ND7 N27 ND27 N127 D127 0127 N ND N4 D4 34 N ND N8 ND8 N68 D68 568 P36-7 G(S) O 1|3|5|7|9 N 2|4|6|8|O D 0|N S O|AO A AD|N P36-8 文法： E T|E T|E T TF|T*F|T / F F(E)|i

2、最左推導(dǎo) : E E T T TF Ti T i T* F i F* F i i* F i i*i ET T*F F*F i*F i*( E) i*( E T) i*( T T) i*( F T) i*( i T) i *( i F) i *( i i ) 最右推導(dǎo) EE TE T*F E T*i E F*i E i*i T i * i F i*i i i* ET 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) /* E E T i i+i+i i-i-i i i+i*i * *

3、/ P36-9 句子iiiei有兩個(gè)語法樹： S iSeS iSei iiSei iiiei S iS iiSeS iiSei iiiei P36-10 /* S TS |T T (S)|() */ P36-11 /* L1: S AC A aAb | ab C cC | L2: S AB A aA| B bBc|bc L3: S AB A aAb| B aBb| L4: S A| B A 0A1| B 1B0| A *I 第三章習(xí)題參考答案 P64 - 7 0 1(01)*101 7 n 1 1 確定化: 0 1 X 0 1,2,3 0 0 0 1,2,3 2,3 2,3,4 2,3 2,3

4、 2,3,4 2,3,4 2,3,5 2,3,4 2,3,5 2,3 2,3,4,Y 2,3,4,Y 2,3,5 2,3,4, 最小化: 0,1,2,3,4耳,6 0,123,4,5。1,3,50,1,2,3,4,511,2,4 0,1,2,3,4, 5,6 0,1,2,34。1,3,5 0,1,23,4, 5,6 0,1,23。1,30,1,2,311,2,4 0,1,2,04, $,6 0,1 0 1 0,11 1,2 2,30 B 門匡4 0,1,2,3, 4, 5, 6 0 1 2 0 4 1 1 1 P64 8 (1) P64 - 12 (1|0) 01 (1|2|3|4|5|6|7

5、|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) 13 a L ( 0 確定化: a b 0 0,1 1 0,1 0,1 1 1 0 0 0 0 0 給狀態(tài)編號(hào): a b 0 1 2 1 1 2 2 0 3 3 3 3 最小化： 0,1, 2,3 0,1 a 1 0,1b 2 2,3a 0,32,3b 3 0,1, 2, 3 aa 已經(jīng)確定化了，進(jìn)行最小化 最小化: 0,1, 2,3,4,5 0,1a 10,1b 2,4 2,3,4,5爲(wèi)1,3,0,52,3,4,5b 2,3,4,5 2,4a 1,02,4b 3,

6、5 3,5a 3,53,5b 2,4 0,1, 2,4, 3,5 0,1a 2,4a 3,5a 1 1,0 3,5 0,嘰2,4 2,4b 3,5b 3,5 2,4 : 0 0 1 X,1,Y 1,Y 2 確定化: 1，Y 1，Y 2 2 1，Y 0 0 0 0 給狀態(tài)編號(hào): 0 1 0 1 2 1 1 2 2 1 3 3 3 3 最小化： 0,1，2,3 0,10 1 0,11 2 2,3o 1,32,3i 3 0,1,2,3 P81 - 1 (1)按照T,S的順序消除左遞歸 G(S) S aF|(T) T ST T ,ST | 遞歸子程序： procedure S; begin if sy

7、m=a or sym=人 the n abva nee else if sym=( the n begi n advance;T; if sym=) the n adva nee; else error; end else error en d; procedure T; begin S;T en d; procedure T ; begin if sym=, the n begi n advanee; 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

8、,( FIRST(T )=, FOLLOW(S)=),# FOLLOW(T)=) FOLLOWT )=) 預(yù)測(cè)分析表 a A ( ) J # S S a S A S (T) T r T ST r T ST T ST T T T ,ST 是LL(1)文法 P81 - 2 文法: E TE EE| TFT TT | FPF F*F| P (E)|a|b$ (1) FIRST(E)=(,a,bf FIRST(E)=+, FIRST(T)=(,a,b FIRST(T)=(,a,b,A, FIRST(F)=(,a,b,A FIRST(F)=*, FIRST(P)=(,a,bf FOLLOW(E)=#,)

9、 FOLLOW(E)=#,) FOLLOW(T)=+,),# FOLLOW(T)=+,),# FOLLOW(F)=(,a,b,A,+,),# FOLLOW(F)=(,a,b,A,+,),# FOLLOW(P)=*,(,a,bf,+,),# 考慮下列產(chǎn)生式： E E| TT| F*F | P(E)|A|a|b FIRST(+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

10、FIRST( )=* A = $ FIRST(*F) A FOLLOW(F)=* A (,a,b,A,+,),#=$ FIRST(E) A FIRST(a) A FIRST(b) A FIRST(A)= $ 所以,該文法式LL(1)文法. + * ( ) a b A # E E TE E TE E TE E TE E EE E E T T FT T FT T FT T FT T T T T T T T T T TT T F F PF F PF F PF F PF F F F *F F F F F F F : P P (E) P a P b P A procedure E; begin if s

11、ym=( or sym=a or sym=b or sym=人 the n beg in T; E end else error end procedure E： begin if sym=+ the n beg in adva nee; E end else if sym) and sym# then error end procedure T; begin if sym=( or sym=a or sym=b or sym=人 the n beg in F; T end else error end procedure T; begin if sym=( or sym=a or sym=b

12、 or sym=人 the n T else if sym=* then error end procedure F; begin if sym=( or sym=a or sym=b or sym=人 the n beg in P; F end else error end procedure F; begin if sym=* the n beg in adva nee; F end end procedure P; begin if sym=a or sym=b or sym=A the n adva nee else if sym=( the n end; begin advanee;

13、 E; if sym=) the n adva nee else error end else error P81 3 /* (1) 是，滿足三個(gè)條件。 不是，對(duì)于A不滿足條件3。 不是，A、B均不滿足條件3。 是，滿足三個(gè)條件。 */ 第五章 P133- 1 E E T E 短語：E+T*F, T*F, 直接短語：T*F 句柄:T*F T* F P133-2 文法: S a|A|(T) T T,S|S (1) 最左推導(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

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

15、(T,A,(a),a)(S,a ,(a), a) (T),a)(T,S),a) (T,(S), a) (T),a ,(a),a) (T,S),a ,(a), a) (T,a),A ,(a),a)( S,a),A ,(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，a) (S，a) (TS) (T)_ S

16、 “移進(jìn)-歸約”過程: 步驟 棧 輸入串 動(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,

17、(a),a)# 歸 13 #(T ,A,(a),a)# 歸 14 #(T， A,(a),a)# 進(jìn) 15 #(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,

18、a)# 進(jìn) 30 #(T,a )# 進(jìn) 31 #(T,S )# 歸 32 #(T )# 歸 33 #(T) # 進(jìn) 34 #S # 歸 P133-3 (1) 輸入字符串動(dòng)作 (4) 棧 # #( #(a #(t FIRSTVT(S)=a,( FIRSTVT(T)=,a】,( LASTVT(S)=a,) LASTVT(T)=,a】,) a A ( ) 5 a A ( = 5 G6是算符文法，并且是算符優(yōu)先文法 (3)優(yōu)先函數(shù) a A ( ) 5 f 4 4 2 4 4 g 5 5 5 2 3 預(yù)備 (a,(a,a) ) # a, (a,a)#進(jìn) ,(a,a)#進(jìn) ,(a,a)#歸 # (t, (

19、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 # 歸 success P134-5 (1) 0. S S 1. S S 2. S AS 3. S A S 4. S AS 5. S b 6. Sb 7. A SA 8. A S A9. A SA 10. A a 11. A

20、 a 確定化: S A a b 0,2,5,7,10 1,2,5,7,8,10 2,3,5,7,10 11 6 1,2,5,7,8,10 2,5,7,8,10 2,3,5,7,9,10 11 2,3,5,7,10 2,4,5,7,8,10 2,3,5,7,10 11 6 2,5,7,8,10 2,5,7,8,10 2,3,5,7,9,10 11 6 2,3,5,7,9,10 2,4,5,7,8,10 2,3,5,7,10 11 6 2,4,5,7,8,10 2,5,7,8,10 2,3,5,7,9,10 11 6 11 0 0 0 0 6 0 0 0 0 SA DFA ss SA As bi

21、a Asb SAa A 1 Sas Asb SAa As SAa As A s b A A A 7 s As SA As SA GO函數(shù)來計(jì)算得到。所得到的項(xiàng)目集規(guī)范族與上圖中的 10 = s S，S AS， S b， A GO(I 0， a)= A a = Ii GO(I 0， b)= S b = 12 GO(I 0， S)= S S，A S A，A 構(gòu)造LR(O)項(xiàng)目集規(guī)范族也可以用 項(xiàng)目集一樣： SA，Aa SA，A a，SAS，Sb= 13 GO（I 0 ， A）= S A S， S AS， S b， A SA， A a = I 4 GO（I 3 ， a）= A a = I1 GO（I

22、 3 ， b）= S b = I2 GO（I 3 ， S）= A S A ， S AS， S b， A SA， A a = I 5 GO（I 3 ， A）= A SA ， S A S， S AS，S b， A SA， A a= I 6 GO（I 4 ，a）= A a = I1 GO（I 4 ，b）= S b = I2 GO（I 4 ，S）= S AS ， A S A ， S AS， S b， A SA ， A a = I 7 GO（I 4 ，A）= S A S， S AS， S b， A SA， A a = I 4 GO（I 5 ， a）= A a = I1 GO（I 5 ， b）= S b

23、= I2 GO（I 5 ， S）= A S A ， S AS， S b， A SA， A a = I 5 GO（I 5，A）= A SA ， S A S， S AS，S b， A SA， A a= I 6 GO（I 6 ，a）= A a = I1 GO（I 6 ，b）= S b = I2 GO（I 6 ，S）= S AS ， A S A ， S AS，S b， A SA， A a= I 7 GO（I6，A）= S A S， S AS， S b， A SA， A a= I 4 GO（I 7，a）= A a = I1 GO（I7，b）= S b = I2 GO（I 7，S）= A S A ， S

24、AS， S b，A SA， A a = I 5 GO（I 7，A）= A SA ， S A S， S AS，S b， A SA ， A a = I 6 項(xiàng)目集規(guī)范族為 C= I1 ， I 2， I3 ， I 4， I5， I 6， I7 不是SLR文法 狀態(tài) 3，6，7 有移進(jìn)歸約沖突 狀態(tài) 3：FOL LOW(S )=# 不包含 a,b 狀態(tài) 6： FOLLOW(S)=#,a,b 包含 a,b, ；移進(jìn)歸約沖突無法消解 狀態(tài)7： FOLLOW(A)=a,b包含a,b ;移進(jìn)歸約沖突消解 所以不是SLR文法。 (4) 構(gòu)造例如 LR(1) 項(xiàng)目集規(guī)范族 見下圖： 對(duì)于狀態(tài)5，因?yàn)榘?xiàng)目A A

25、S 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) 文法。 S 5: /* * 第六章會(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 := real ETE.type:=T.type Tnum.num T.type := real Tnum T.type := int P164-7 S L1|L2

26、S.val:=L1.val+(L2.val/2 L2.length S L S.val:=L.val L L1B L.val:=2*L1.val + B.val; L.le ngth:=L1.le ngth+1 L B L.val:=B.c; L.le ngth :=1 B 0 B.c:=0 B 1 B.c:=1 */ 第七章 P217- 1 a*(-b+c) a+b*(c+d/e) -a+b*(-c+d) abc+* abcde/+*+ abcd+*+ A (C D) A CD (A B) ( C D) AB CD (A B) (CD E) AB CDE if (x+y)*z =0 then

27、 (a+b) f c else af b f c xy+z*0= ab+c f abc ff 或 xy+z*O= P1 jez ab+c f P2 jump abc ff P1 P2 P217- 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),

28、 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 , T7 P218-4 自下而上分析過程中把賦值句翻譯成四元式的步驟 :A:=B*(-C+D) 步驟 輸入串 棧 PLACE 四元式 (1) A:=B*(-C+D) (2) :=B*(-C+D) i A (3) B*(-C+D) i:= A- (4) *(-C

29、+D) i:=i A-B (5) *(-C+D) i:=E A-B (6) *(-C+D) (7) (-C+D) (8) -C+D) (9) C+D) (10) +D) (11) +D) (12) +D) (13) D) (14) ) (15) ) (16) ) (17) (18) (19) i:=E i:=E* i:=E*( i:=E*(- i:=E*(-i i:=E*(-E i:=E*(E i:=E*(E+ i:=E*(E+i i:=E*(E+E i:=E(E i:=E*(E) i:=E+E i:=E A-B A-B- A-B- A-B- A-B-C A-B-C A-B- T 1 A-B-

30、 T - 1 A-B- T -D 1 A-B- T -D 1 A-B- T 2 A-B- T - 2 A-B- T 2 A-T 3 (20) A (,C,-, T1 ) (+, T1,D, T2 ) (*,B, T2, T3) (:=, T3,-,A) 產(chǎn)生的四元式： (,C,-, T ) 1 (+, T1,D, T2 ) (*,B, 1T , T2 ) 23 (:=, T3 ,-,A) P218- 5 * 設(shè) A : 10*20 , B、C、D: 20,寬度為 w = 4 則 T1:= i * 20 T1:=T1+j T2:=A -84 T3:=4*T1 Tn:=T2T3/這一步是多余的 T

31、4:= i + j T5:=B -4 T6:=4*T4 T7:=T5T6 T8:= i * 20 T8:=T8+j T9:=A -84 T10:=4*T8 T11:=T9T10 T12:= i + j T13:=D -4 T14:=4*T12 T15:= T13T14 T16:=T11+T15 T17:=C-4 T18:=4*T16 T19:=T17T18 T20:=T7+T19 Tn:=T20 * P218- 6 100. (jnz, A, -, 0) 101. (j, -, -, 102) 102. (jnz, B, -, 104) 103. (j, -, -, 0) 104. (jnz,

32、 C, -, 103) 105. (j, -, -, 106) 假鏈鏈?zhǔn)?真鏈鏈?zhǔn)?106. (jnz, D, -, 104) - 107. (j, -, -, 100) - 假鏈： 106,104 ， 103 真鏈： 107,100 P218-7 100. (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, -, -, 1

33、00) 109. (j , El.place , E2.place 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 n I.place := p else error MM.quad := nextquad */ 方法2: St for id:=E1 to E2 do S1 St F S1 Ft for id:=E1 to E2 d

34、o F forid : EltoE 2do M.quad); ,0 ); INITIAL=NEWTEMP; emit( :=， E1.PLACE , FINAL=NEWTEMP; emit( :=， E2.PLACE , p:= n extquad+2; emit( j , INITIAL ,INITIAL); ,FINAL); FINAL p); F.n extlist:=makelist (n extquad); emit( j,); F.place:=lookup(id. name); if F.placenil the n emit(F.place := INITIAL) F.quad:=n extquad; F.fi nal:=FINAL; S FS1 backpatch(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