编译原理第三版课后习题解答

1、第二章习题解答 P36-6 (1) L(Gi)是o9组成的数字串 (2) 最左推导 : N ND NDD NDDD DDDD 0DDD 01DD 012D 0127 N ND DD 3D 34 N ND NDD DDD 5DD 56D 568 最右推导 : 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、最左推导 : 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 ) 最右推导 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有两个语法树： 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 第三章习题参考答案 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 给状态编号: 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 已经确定化了，进行最小化 最小化: 0,1, 2,3,4,5 0,1a 10,1b 2,4 2,3,4,5爲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 给状态编号: 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:是输入串指针IP所指的符号 advanee:是把IP调至下一个输入符号 error:是出错诊察程序 FIRST(S)=a,( FIRST(T)=af

8、,( FIRST(T )=, FOLLOW(S)=),# FOLLOW(T)=) FOLLOWT )=) 预测分析表 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,+,),# 考虑下列产生式： 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) 是，满足三个条件。 不是，对于A不满足条件3。 不是，A、B均不满足条件3。 是，满足三个条件。 */ 第五章 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) 最左推导: S (T)(T,S) S (T,S)(S,S) (T,S),S,S), S) (a,a),A ,S),S) (a,a),A ,(a), a) 最右推导: (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、 “移进-归约”过程: 步骤 栈 输入串 动作 0 # (a,a),A,(a),a)# 预备 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 #(T ,a),A,(a),a)# 归 7 #(T， a),A,(a),a)# 进 8 #(T，a ),A,(a),a)# 进 9 #(T，S ),A,(a),a)# 归 10 #(T ),A,(a),a)# 归 11 #(T) ,A,(a),a)# 进 12 #(S ,A,

17、(a),a)# 归 13 #(T ,A,(a),a)# 归 14 #(T， A,(a),a)# 进 15 #(T，a ,(a),a)# 进 16 #(T,S ,(a),a)# 归 17 #(T ,(a),a)# 归 18 #(T， (a),a)# 进 19 #(T，( a),a)# 进 20 #(T，(a ),a)# 进 21 #(T，(S ),a)# 归 22 #(T，(T ),a)# 归 23 #(T，(T) ),a)# 进 24 #(T,S ),a)# 归 25 #(T ),a)# 归 26 #(T) ,a)# 进 27 #(S ,a)# 归 28 #(T ,a)# 归 29 #(T,

18、a)# 进 30 #(T,a )# 进 31 #(T,S )# 归 32 #(T )# 归 33 #(T) # 进 34 #S # 归 P133-3 (1) 输入字符串动作 (4) 栈 # #( #(a #(t FIRSTVT(S)=a,( FIRSTVT(T)=,a】,( LASTVT(S)=a,) LASTVT(T)=,a】,) a A ( ) 5 a A ( = 5 G6是算符文法，并且是算符优先文法 (3)优先函数 a A ( ) 5 f 4 4 2 4 4 g 5 5 5 2 3 预备 (a,(a,a) ) # a, (a,a)#进 ,(a,a)#进 ,(a,a)#归 # (t, (

19、a,a) ) # 进 # (t,( a,a) # 进 # ( t, ( a ,a ) # 进 # ( t, ( t ,a ) # 归 # ( t, ( t, a) # 进 # (t, (t,a )# 进 # (t, (t,s )# 归 # ( t, ( t )# 归 # ( t, ( t ) )# 进 # (t,s )# 归 # (t )# 归 # (t) # 进 # 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函数来计算得到。所得到的项目集规范族与上图中的 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 构造LR(O)项目集规范族也可以用 项目集一样： 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 项目集规范族为 C= I1 ， I 2， I3 ， I 4， I5， I 6， I7 不是SLR文法 状态 3，6，7 有移进归约冲突 状态 3：FOL LOW(S )=# 不包含 a,b 状态 6： FOLLOW(S)=#,a,b 包含 a,b, ；移进归约冲突无法消解 状态7： FOLLOW(A)=a,b包含a,b ;移进归约冲突消解 所以不是SLR文法。 (4) 构造例如 LR(1) 项目集规范族 见下图： 对于状态5，因为包含项目A A

25、S a/b，所以遇到搜索符号a或b时，应该用A AS 归约。又因为状态 5 包含项目 A a a/b ，所以遇到搜索符号 a 时，应该移进。因此 存在“移进 -归约”矛盾，所以这个文法不是 LR(1) 文法。 S 5: /* * 第六章会有点难 第六章 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) 产生的四元式： (,C,-, T ) 1 (+, T1,D, T2 ) (*,B, 1T , T2 ) 23 (:=, T3 ,-,A) P218- 5 * 设 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) 假链链首 真链链首 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