编译原理课后习题答案陈火旺第三版.pdf

课后答案网课后答案网 课后答案网课后答案网 http:// 第二章第二章 P P3636- -6 6 (1) L G() 1是 09 组成的数字串 (2) 最左推导: NNDNDDNDDDDDDDDDDDDD NNDDDD NNDNDDDDDDDD 0010120127 334 556568 最右推导: NNDNNDNNDND NNDND NNDNNDND 7727271271270127 4434 886868568 P P3636- -7 7 G(S) O NO DN SO AO AAD N 1357 9 2 4 68 0 | | | | | | | | | | | P36P36- -8 8 文法： ET ET ET TF TF TF FE i | |*|/ ( )| 最左推导: EETTTFTiTiTFiFFiiFii i ETTFFFiFiEiETiTTiFT iiTiiFiii * *()*()*()*() *()*()*() 最右推导: EETETFET iEF iEi iTi iFi iii i ETF TFFFEFETFEFFEi FTiFFiFiiiii * *()*()*()*() *()*()*()*() 语法树：/* 课后答案网课后答案网 课后答案网课后答案网 http:// E EF TE+ T F F T + i i i E EF TE- T F F T - i i i E E F T+ T F F T i i i * i+i+ii-i-ii+i*i */ P36P36- -9 9 句子 iiiei 有两个语法树： SiSeSiSeiiiSeiiiiei SiSiiSeSiiSeiiiiei P36P36- -1010 /* ) ( | )( | ST TTSS */ P36P36- -1111 /* L1: | | cCC abaAbA ACS L2: bcbBcB aAA ABS | | L3: 课后答案网课后答案网 课后答案网课后答案网 http:// | | aBbB aAbA ABS L4: ABB AA BAS |01 |10 | */ 第三章习题参考答案第三章习题参考答案 P64P647 7 (1) 1 01 101( | )* 0 1 1 0 1 1 确定化： 0 1 X 1,2,3 1,2,3 2,3 2,3,4 2,3 2,3 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 0 0 0 1 1 0 0 1 0 1 1 1 最小化： X 1 2 3 4 Y 5 X Y 6 0 1 2 3 5 4 课后答案网课后答案网 课后答案网课后答案网 http:// , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , 012 34 56 012 34 5135012 34 512 4 6 012 3456 012 34135 012 3456 012 31 01 0 0 3012 312 4 012 3 456 0110112 2 332 34 012 3456 1 01 01 , , , , , , , , , , , , , , , , , , , , , 0 1 0 0 1 0 0 1 0 1 1 1 P64P648 8 (1) 01)0|1 ( * (2) )5|0( | )5|0()9|8|7|6|5|4|3|2| 1|0)(9|8|7|6|5|4|3|2|1 ( * (3) * ) 110|0(01|) 110|0( 10 P64P641212 (a) a a,b a 确定化： a b 0 0,1 1 0,1 0,1 1 1 0 5 0 1 2 4 3 0 1 课后答案网课后答案网 课后答案网课后答案网 http:// 给状态编号： a b 0 1 2 1 1 2 2 0 3 3 3 3 a a a b b b b a 最小化： , , , , , , , , , , , 012 3 011012 2 30 32 33 0123 ab ab a a b b a b (b) b b a a b a a b b a a a 已经确定化了,进行最小化 0 1 2 3 0 1 2 0 2 3 1 4 5 课后答案网课后答案网 课后答案网课后答案网 http:// 最小化： , , , , , 0 12 3 4 5 0 110 12 4 2 3 4 51 3 0 52 3 4 52 3 4 5 2 41 02 43 5 3 53 53 52 4 0 12 43 5 0 110 12 4 2 4 , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ab ab ab ab ab a , , , , , , , 1 02 43 5 3 53 53 52 4 b ab b b a a b a P64P641414 (1) 0 1 0 (2): ( |)*010 0 1 0 确定化： 0 1 X,1,Y 1,Y 2 0 1 2 0 1 Y X Y X 2 1 课后答案网课后答案网 课后答案网课后答案网 http:// 1,Y 1,Y 2 2 1,Y 给状态编号： 0 1 0 1 2 1 1 2 2 1 3 3 3 3 0 0 1 0 1 1 1 0 最小化： , , , , , , , , , , , 0 12 3 0 110 12 2 31 32 33 0 123 01 01 0 1 1 1 0 0 第四章第四章 P81P811 1 (1) 按照 T,S 的顺序消除左递归 |, )( | )( TST TST TaS SG 递归子程序： procedure S; begin if sym=a or sym= then abvance else if sym=( 0 2 1 3 0 1 3 课后答案网课后答案网 课后答案网课后答案网 http:// then begin advance;T; if sym=) then advance; else error; end else error end; procedure T; begin S;T end; procedure T; begin if sym=, then begin advance; S;T end end; 其中: sym:是输入串指针 IP 所指的符号 advance:是把 IP 调至下一个输入符号 error:是出错诊察程序 (2) FIRST(S)=a,( FIRST(T)=a,( FIRST(T)=, FOLLOW(S)=),# FOLLOW(T)=) FOLLOW(T)=) 预测分析表 a ( ) , # S Sa S ST( ) T TST TST TST T T TST, 是 LL(1)文法 P81P812 2 文法： 课后答案网课后答案网 课后答案网课后答案网 http:// | )( |* | | baEP FF FPF TT TFT EE ETE (1) FIRST(E)=(,a,b, FIRST(E)=+, FIRST(T)=(,a,b, FIRST(T)=(,a,b, FIRST(F)=(,a,b, FIRST(F)=*, FIRST(P)=(,a,b, FOLLOW(E)=#,) FOLLOW(E)=#,) FOLLOW(T)=+,),# FOLLOW(T)=+,),# FOLLOW(F)=(,a,b,+,),# FOLLOW(F)=(,a,b,+,),# FOLLOW(P)=*,(,a,b,+,),# (2) 考虑下列产生式: EE TT FF PEa b | | *| ()| | FIRST(+E)FIRST()=+= FIRST(+E)FOLLOW(E)=+#,)= FIRST(T)FIRST()=(,a,b,= FIRST(T)FOLLOW(T)=(,a,b,+,),#= FIRST(*F)FIRST()=*= FIRST(*F)FOLLOW(F)=*(,a,b,+,),#= FIRST(E)FIRST(a) FIRST(b) FIRST()= 所以,该文法式 LL(1)文法. (3) + * ( ) a b # E ETE ETE ETE ETE E EE E E T TFT TFT TFT TFT T T TT T TT TT TT T 课后答案网课后答案网 课后答案网课后答案网 http:// F FPF FPF FPF FPF F F FF* F F F F F F P PE( ) Pa Pb P (4) procedure E; begin if sym=( or sym=a or sym=b or sym= then begin T; E end else error end procedure E; begin if sym=+ then begin advance; E end else if sym# then error end procedure T; begin if sym=( or sym=a or sym=b or sym= then begin F; T end else error end procedure T; begin if sym=( or sym=a or sym=b or sym= then T else if sym=* then error end procedure F; begin if sym=( or sym=a or sym=b or sym= then begin P; F end else error end procedure F; begin if sym=* then begin advance; F end end procedure P; begin if sym=a or sym=b or sym= then advance else if sym=( then 课后答案网课后答案网 课后答案网课后答案网 http:// begin advance; E; if sym=) then advance else error end else error end; P81P813 3 /* (1) 是，满足三个条件。 (2) 不是，对于 A 不满足条件 3。 (3) 不是，A、B 均不满足条件 3。 (4) 是，满足三个条件。 */ 第五章第五章 P133P1331 1 EETET F* 短语: E+T*F, T*F, 直接短语: T*F 句柄: T*F P P1331332 2 文法： SaT TT S S |( ) , | (1) 最左推导: STT SS Sa Sa Ta T SaS Sa a Sa a a ST SS STST SST S SSS S SSTS SS T SS SSS SS SSa S ( )( , )( , )( , )( ,( )( ,( , )( ,( , )( ,( , )( ,( , ) ( , )( , )( ), )( , ), )( , , ), )( , , ), )( ), , ), ) ( , ), , ), )( , ), , ), )( , ), , ), )( , ), , ), ) ( , ), ), )( , ),( ), )( , ),( ), )( , ),( ), ) ( , ),( ), ) S SSa aS SS a aSSa aTSa aSSa aaS a aaa 最右推导: STT STTTT STT aTS aTa a Sa aa a a ST ST aS aTaT SaTTaTSa TaaT SaaTaa ( )( , )( ,( )( ,( , )( ,( , )( ,( , )( ,( , ) ( ,( , )( ,( , ) ( , )( , )( , )( ), )( , ), )( ,( ), )( ,( ), ) ( ,( ), )( , ,( ), )( ,( ), )( ,( ), )( ),( ), ) ( , ),( ), )( , ),( ), )( , ),( ), )( , ),( ), ) SaaTaa T SaaT aaaS aaaa aaa (2) (a a,a),(a),a) 课后答案网课后答案网 课后答案网课后答案网 http:// (S,a),(a),a) (T,a a),(a),a) (T,ST,S),(a),a) (T)(T),(a),a) (S S,(a),a) (T,(a),a) (T,ST,S,(a),a) (T,(a a),a) (T,(S S),a) (T,(T T),a) (T,ST,S),a) (T)(T),a) (S S,a) (T,ST,S) (T)(T) S “移进-归约”过程： 步骤 栈 输入串 动作 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)# 进 5 #(S ,a),(a),a)# 归 6 #(T ,a),(a),a)# 归 7 #(T, a),(a),a)# 进 8 #(T,a ),(a),a)# 进 9 #(T,S ),(a),a)# 归 10 #(T ),(a),a)# 归 11 #(T) ,(a),a)# 进 12 #(S ,(a),a)# 归 13 #(T ,(a),a)# 归 14 #(T, ,(a),a)# 进 15 #(T, ,(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)# 归 课后答案网课后答案网 课后答案网课后答案网 http:// 26 #(T) ,a)# 进 27 #(S ,a)# 归 28 #(T ,a)# 归 29 #(T, a)# 进 30 #(T,a )# 进 31 #(T,S )# 归 32 #(T )# 归 33 #(T) # 进 34 #S # 归 P P1331333 3 (1) FIRSTVT(S)=a,( FIRSTVT(T)=,a,( LASTVT(S)=a,) LASTVT(T)=,a,) (2) a ( ) , a ( , 6 G是算符文法，并且是算符优先文法 (3)优先函数 a ( ) , f 4 4 2 4 4 g 5 5 5 2 3 fa f f( f) f, ga g g( g) g, （4） 栈 输入字符串 动作 # （a,(a,a)）# 预备 #( a, (a,a)# 进 #(a , (a,a)# 进 #(t , (a,a)# 归 课后答案网课后答案网 课后答案网课后答案网 http:// #（t, (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 P P1341345 5 (1) 0. SS 1. SS 2.SAS 3.SA S 4.SAS 5.Sb 6.Sb 7.ASA 8.AS A 9.ASA 10.Aa 11.Aa (2) S A S a A S d 确定化： 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,102,5,7,8,10 2,3,5,7,9,1011 6 0 10 5 7 6 1 11 2 3 4 8 9 课后答案网课后答案网 课后答案网课后答案网 http:// 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 6 A S S A a b S a A S b S A b a A A S b a a b b a DFA 构造 LR(0)项目集规范族也可以用 GO 函数来计算得到。所得到的项目集规范族与上图中的 项目集一样: 0 I= SS，SAS，Sb，ASA，Aa GO( 0 I，a)= Aa= 1 I GO( 0 I，b)= Sb= 2 I GO( 0 I，S)= SS，AS A，ASA，Aa，SAS，Sb= 3 I 0: SS SAS Sb ASA Aa 4:SA S SAS Sb ASA Aa 3: SS AS A ASA Aa SAS Sb 2:Sb 1:Aa 5:AS A SAS Sb ASA Aa 6:ASA SA S SAS Sb ASA Aa 7:SAS AS A SAS Sb ASA Aa 课后答案网课后答案网 课后答案网课后答案网 http:// GO( 0 I，A)= SA S，SAS，Sb，ASA，Aa= 4 I GO( 3 I，a)= Aa= 1 I GO( 3 I，b)= Sb= 2 I GO( 3 I，S)= AS A，SAS，Sb，ASA，Aa= 5 I GO( 3 I，A)= ASA，SA S，SAS，Sb，ASA，Aa= 6 I GO( 4 I，a)= Aa= 1 I GO( 4 I，b)= Sb= 2 I GO( 4 I，S)= SAS，AS A，SAS，Sb，ASA，Aa= 7 I GO( 4 I，A)= SA S，SAS，Sb，ASA，Aa= 4 I GO( 5 I，a)= Aa= 1 I GO( 5 I，b)= Sb= 2 I GO( 5 I，S)= AS A，SAS，Sb，ASA，Aa= 5 I GO( 5 I，A)= ASA，SA S，SAS，Sb，ASA，Aa= 6 I GO( 6 I，a)= Aa= 1 I GO( 6 I，b)= Sb= 2 I GO( 6 I，S)= SAS，AS A，SAS，Sb，ASA，Aa= 7 I GO( 6 I，A)= SA S，SAS，Sb，ASA，Aa= 4 I GO( 7 I，a)= Aa= 1 I GO( 7 I，b)= Sb= 2 I GO( 7 I，S)= AS A，SAS，Sb，ASA，Aa= 5 I GO( 7 I，A)= ASA，SA S，SAS，Sb，ASA，Aa= 6 I 项目集规范族为 C= 1 I， 2 I， 3 I， 4 I， 5 I， 6 I， 7 I (3)不是 SLR 文法 状态 3，6，7 有移进归约冲突 状态 3：FOLLOW(S)=#不包含 a,b 状态 6：FOLLOW(S)=#,a,b包含 a,b,；移进归约冲突无法消解 状态 7：FOLLOW(A)=a,b包含 a,b；移进归约冲突消解 所以不是 SLR 文法。 (4) 构造例如 LR(1)项目集规范族 见下图： 对于状态5， 因为包含项目baASA/ ， 所以遇到搜索符号a或b时， 应该用ASA 归约。又因为状态 5 包含项目baaA/ ，所以遇到搜索符号 a 时，应该移进。因此 存在“移进-归约”矛盾，所以这个文法不是 LR(1)文法。 课后答案网课后答案网 课后答案网课后答案网 http:// b b b A A A S a a S S a S a a A a A S b S A b a a S b b S b A A 0： a/baA a/bSAA #/a/bbS #/a/bASS SS # 2： a/baA a/bSAA #/a/bbS #/a/bASS #/a/bSAS 1： a/bbS a/bASS a/baA a/bSAA a/bASA SS # 3： a/baA 4： a/b bS/# 5： a/baA a/bSAA a/bbS a/bASS a/bSAS a/bSAA 6： a/bbS a/bASS a/baA a/bSAA a/bASA 7： a/bbS a/bASS a/baA a/bSAA a/bASA a/b ASS /# 9： a/bbS a/bASS a/baA a/bSAA a/bASA a/bASS 8： a/baA a/bSAA a/bbS a/bASS a/bSAS 10： a/bbS 3： 5： 课后答案网课后答案网 课后答案网课后答案网 http:// 第六章第六章 /*第六章会有点难 P1P164645 5 (1) EE1T if (E1.type = int) and (T.type = int ) then E.type := int else E.type := real ET E.type := T.type Tnum.num T.type := real Tnum T.type := int (2) P1P164647 7 SL1|L2 S.val:=L1.val+(L2.val/2 lengthL . 2 ) SL S.val:=L.val LL1B L.val:=2*L1.val + B.val; L.length:=L1.length+1 LB L.val:=B.c; L.length :=1 B0 B.c:=0 B1 B.c:=1 */ 第七章第七章 P217P2171 1 a*(-b+c) abc+* a+b*(c+d/e) abcde/+*+ -a+b*(-c+d) abcd+*+ )(DCA CDA )()(DCBA DCAB )()(EDCBA ECDAB if (x+y)*z =0 then (a+b)c else abc xy+z*0= ab+cabc ￥ 或 xy+z*0= P1 jez ab+c P2 jump abc P1 P2 课后答案网课后答案网 课后答案网课后答案网 http:// P217P2173 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), c (6) -, (4), (5) 间接码表： (1) (2) (3) (4) (1) (5) (6) 四元式序列: (1) +, a, b, 1 T (2) , 1 T, -, 2 T (3) +, c, d, 3 T (4) *, 2 T, 3 T, 4 T (5) +, a, b, 5 T (6) +, 5 T, c, 6 T (7) -, 4 T, 6 T, 7 T P218P2184 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+D) i:=i A-B (5) *(-C+D) i:=E A-B 课后答案网课后答案网 课后答案网课后答案网 http:// (6) *(-C+D) i:=E A-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*(-i A-B-C (11) +D) i:=E*(-E A-B-C (,C,-, T 1 ) (12) +D) i:=E*(E A-B-T 1 (13) D) i:=E*(E+ A-B-T 1 - (14) ) i:=E*(E+i A-B-T 1 -D (15) ) i:=E*(E+E A-B-T 1 -D (+,T 1 ,D,T2) (16) ) i:=E(E A-B-T2 (17) i:=E*(E) A-B-T2- (18) i:=E+E A-B-T2 (*,B,T2,T3) (19) i:=E A-T3 (:=,T3,-,A) (20) A 产生的四元式： (,C,-, T 1 ) (+,T 1 ,D,T2) (*,B,T2,T3) (:=,T3,-,A) P218P2185 5 /* 设 A ：10*20，B、C、D：20，宽度为 w4 则 T1:= i * 20 T1:=T1+j T2:=A84 T3:=4*T1 Tn:=T2T3 /这一步是多余的 T4:= i + j T5:=B4 T6:=4*T4 T7:=T5T6 T8:= i * 20 T8:=T8+j T9:=A84 T10:=4*T8 T11:=T9T10 T12:= i + j T13:=D4 T14:=4*T12 T15:= T13T14 T16:=T11+T15 T17:=C4 课后答案网课后答案网 课后答案网课后答案网 http:// T18:=4*T16 T19:=T17T18 T20:=T7+T19 Tn:=T20 */ P218P2186 6 100. (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,100 P218P2187 7 100. (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; idI p:=lookup(); if p nil then I.place := p else error M M.quad := nextquad */ 方法 2： S for id:=E1 to E2 do S1 S F S1 F for id:=E1 to E2 do 21:toEEforidFdo INITIAL=NEWTEMP; emit(:=， E1.PLACE ， -， INITIAL); FINAL=NEWTEMP; emit(:=， E2.PLACE ， -， FINAL); p:= nextquad+2; emit(j, INITIAL , FINAL , p); F.nextlist:=makelist(nextquad); 课后答案网课后答案网 课后答案网课后答案网 http:// emit(j,); F.place:=lookup(); if F.placenil then emit(F.place := INITIAL) F.quad:=nextquad; F.final:=FINAL; 1FSS backpatch(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, F.quad); 第九章第九章 P P2702709 9 (1) 传名 即当过程调用时， 其作用相当于把被调用段的过程体抄到调用出现处， 但必须将其中出现的 任一形式参数都代之以相应的实在参数。 A:=2; B:=3; A:=A+1; A:=A+(A+B); print A; A=9 (2) 传地址 即当程序控制转入被调用段后，被调用段首先把实在参数抄进相应的形式参数的形式单元 中， 过程体对形参的任何引用或赋值都被处理成对形式单元的