编译原理陈火旺第三版练习答案.pdf

《编译原理陈火旺第三版练习答案.pdf》由会员分享，可在线阅读，更多相关《编译原理陈火旺第三版练习答案.pdf（28页珍藏版）》请在装配图网上搜索。

1、第二章 P-36-6 （1）L（G）是 09 组成的数字串； （2）最左推导： N NDNDDNDDDDDDD0DDD01DD012D0127 N NDDD3D34 N NDNDDDDD5DD56D568 最右推导： N NDN7ND7N27ND27N127D1270127 N NDN4D434 N NDN8ND8N68D68568 P-36-7 G（S） ： （没有考虑正负符号问题） SP|AP P1|3|5|7|9 AAD|N N2|4|6|8|P D0|N 或者： （）SC 13579 P-36-8 G（E） ：ET|E+T|E-T TF|T*F|T/F

2、 F（E）|i 最左推导： EE+TT+TF+Ti+Ti+T*Fi+F*Fi+i*Fi+i*i ETT*FF*Fi*Fi*（E）i*（E+T）i*（T+T）i*（F+T）i*（i+T）i*（i+F）i*（i+i） 最右推导： EE+TE+T*FE+T*iE+F*iE+i*iT+i*iF+i*ii+i*i ETT*FT*（E）T*（E+T）T*（E+F）T*（E+i）T*（T+i）T*（F+i）T*（i+i） F*（i+i）i*（i+i） 1 语法树： E i+i+i E + T E + T T F i F i F i E E+T T F i T* F F i i i+i*i E i-i-i E

3、 - T E- T T F i F i F i P-36-9 句子：iiiei 有两个语法树： S iSeS iS i i S i S i S e S i i SiSeSiSeiiiSeiiiiei SiSiiSeSiiSeiiiiei 因此 iiiei 是二义性句子，因此 该文法是二义性的。 P-36-10 STS|T T(S)|() P-36-11 L1: G(S): SAC AaAb|ab CcC| L2: G(S): SAB AaA| BbBc|bc L3: G(S): SAB AaAb| BaAb| L4: G(S): S1S0|A A0A

4、1| 或者：SA|B A0A1| B1B0|A 2 第三章 （1） X Y 1（0|1）*101 0 X 1 Y 1 2 3 4 5 0 1 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，2，3，4，5，6 0，1，2，3，4，5 0 =1，3，5 0，1，2，3，4，5 1 =1，2，4，6 0，1，2，3，4，5，6 0，1，2，3，4 0 =1，3，5 0，1，2，3，4，5，6 0，1，2，3 0 =

5、1，3 0，1，2，3 1 =1，2，4 0，1，2，3，4，5，6 0，1 0 =1 0，1 1 =1，2 2 ，3 0 =3 2，3 1 =4 0，1，2，3，4，5，6 2 0 3 5 4 1 0 6 1 0 1 1 0 0 0 0 1 0 1 1 1 3 0 2 4 3 1 0 5 1 0 1 1 1 0 0 0 0 1 1 P64-8 (1) （0|1） * 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） (3) 0 * 1（0|10 * 1） * | 1 * 0（1|01 * 0） * P84-12

6、（a） a 0 1 a，b a 确定化： a b 0 0,1 1 0,1 0,1 1 1 0 给状态编号： a B 0 1 2 1 1 2 2 0 3 3 3 3 4 0 1 2 3 a a a b b b b a 最小化： 0，1 2，3 0，1a=1，0，1b=2 2，3a=0，3，2，3=3 0，1，2，3 0 a 2 1 a a b b b （b） 已经确定化，只需最小化： 0，1，2，3，4，5 0，1 a = 1 0，1 b = 2，4 2，3，4，5 a = 1，3，0，5 2，3，4，5 b = 2，3，4，5 又：2，4 a = 1，0 2，4b = 3，5 3，5

7、 a =3，5 3，5 b = 2，4 分划为：0，1，2，4，3，5 0，1 a = 1 0，1 b = 2，4 2，4 a = 1，0 2 ，4 b = 3，5 3，5 a = 3，5 3 ，5 b = 2，4 所以不能再分 0 a 2 1 a a b b b 5 P64-14 正规式： （0|10） * 0 0 1 0 1 还可以： 然后再确定化，最小化，结果应该一样。 P65-15 首先构造 NFA： 0|1 则有：G（f） f A1|B0|C1|C0 CC0|C1|A1|B0 AS1|1 BS0|0 SS0|S1| 或者是确定化，然后最小化： G（

8、C） CC0|C1|A0|B1 A0|B0 B1|A1 f S C 0 A B 1 0 1 0 0 1 1 1 0 0 Y X 1 0 1 0 2 A S C B 0 1 0 1 1 0 0，1 1 6 人、狼、羊、白菜： M、W、G、C，表示在左岸，，M、W、G、C在右岸，将可能存在的状态中去掉不安全 ，，M、W、G、C，M、W、G，C，M、W、C，G， G：表示人和羊过河、：表示人和狼过河、： 状态，剩下： M、W、G、C， M、G、C，W ，C，M、W、G ，G，M、W、C，W，M、G、C， M、G，W、C ，W，C，M、G 箭弧上的标记符：：表示人单独过河、

9、白菜过河 M、W、G、C， W，C，M、G M、W、C，G G，M、W、C C，M、W、G M、C、G ， W W，M、G、C W、M、G， C M、G， W、 C ,M、W、G、C 7 第四章 P81-1 （1） 按照 T，S 的顺序消除左递归 G（S） ：Sa||（T） TST T，ST| 递归下降子程序： procedure S: begin if sym = aor sym= then advance else if sym= （ then begin advance；T； if sym = ) then advance; else error; end else

10、 error end procedure T; begin S;T End Procedure T; Begin If sym = , Then begin Advance; S;T End End 其中：sysm为输入串指针所指的符号；advance是把输入指针调至下一输入符号。 （2） 求 First 和Follow 集合： First（S）=a 、 、 （ First（T）=a 、 、 （ First（T）=， 、 Follow（S）= , 、) 、 # Follow(T) = ) Follow(T）= ) a ( ) , # S Sa S S (T) T TST

11、TST TST T T T， ST 8 P81-2 文法：ETE E+E| TFT TT| FPF F*F| P（E）|a|b| （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)=+，(,

12、a,b,,),# Follow(P) =*，+,(,a,b,,),# （2）文法无左递归，考察 E+E| TT| F*F| P（E）|a|b| E+E|： First(E) = +,Follow(E)=#,) = TT|： First(T) = (,a,b, , Follow(T)=+,),# = F*F|：First(F) = *,Follow(F)= (,a,b,,),# = P（E）|a|b|：候选式终结首符集两两不相交 所以该文法为 LL(1)文法。 （3） LL(1)分析表 + * （ ） a b # E ETE ETE ETE ETE E E+E E E T TFT TFT TFT

13、 TFT T T TT T TT TT TT T F FPF FPF FPF FPF F F F*F F F F F F F P P（E） 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 ) and sym # then error End Procedure T; Be

14、gin If sym = ( or sym = a or sym = b or sym = Then begin F; T end Else error End 9 Procedure T; Begin if sym = ( or sym = a or sym = b or sym = Then begin 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 Procedur

15、e 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 Begin advance; E ; If sym = ) then advance Else error End Else error end P81-3 解答： （1）该文法不含左递归，计算 First 集合和 Follow集合 Fisrt(S) = a，b，c First(A) = a， First（B）=

16、b, Follow(S)=# Follow（A）=b，c Follow(B) = c 满足LL(1)文法的3 个条件，所以是 LL(1)文法； （2）该文法不含左递归，计算 First 集合和Follow 集合 Fisrt(S) = a，b First(A) = a，b， First（B）= b, Follow(S)=# Follow（A）=b Follow(B) = b 考虑 Aa|B|,Fisrt(A)中含有，而 Fisrt(A)Follow（A）=b，所以不是 LL(1)文法； （3）该文法不含左递归，计算 First 集合和Follow 集合 Fisrt(S) =

17、a，b， First(A) = a， First（B）= b, Follow(S)=# Follow（A）=a，b，# Follow(B) = a，b，# 考虑 Aa|,Fisrt(A)中含有，而 Fisrt(A)Follow（A）=a，所以不是 LL(1)文法； (4)是 LL（1）文法 10 P82-4 文法：Expr-Expr Expr(Expr)|Var ExprTail ExprTail-Expr| Varid VarTail VarTail(Expr) | 解答：First(Expr)=-， （，id First（Var）=id First(ExprTail)=-,

18、 First(VarTail) = (, Follow(Expr)=#,) Follow(Var) = -，#， ） Follow（ExprTail）=#,) Follow(VarTail)= -，#， ） 所以 LL(1)分析表： - id （ ） # Expr Expr-Expr ExprVar ExprTail Expr(Expr) ExprTail ExprTail-Expr ExprTail ExprTail Var Varid VarTail VarTail VarTail VarTail(Expr) VarTail VarTail 分析 idid((id)) 分析栈

19、 输入 所用产生式 #Expr id--id((id)) # #ExprTail Var id--id((id)) # ExprVar ExprTail #ExprTail VarTail id id--id((id)) # Varid VarTail #ExprTail VarTail --id((id)) # #ExprTail --id((id)) # VarTail #Expr- --id((id)) # ExprTail-Expr #Expr -id((id)) # #Expr-

20、 -id((id)) # Expr-Expr #Expr id((id)) # #ExprTail Var id((id)) # ExprVar ExprTail #ExprTail VarTail id id((id)) # Varid VarTail #ExprTail VarTail ((id)) # #ExprTail )Expr( ((id)) # VarTail(Expr) #ExprTail )Expr (id)) # #ExprTail ))Expr( (id)) #

21、 Expr(Expr) #ExprTail ))Expr id)) # #ExprTail ))ExprTail Var id)) # ExprVar ExprTail #ExprTail ))ExprTail VarTail id id)) # Varid VarTail #ExprTail )) ExprTail VarTail )) # #ExprTail )) ExprTail )) # VarTail #ExprTail )) )) # ExprTail #ExprTail ) ) # #ExprTail

22、 # # # ExprTail 11 第五章 P133-1 EE+TE+T*F 短语：E+T*F，T*F 直接短语：T*F 句柄：T*F P133-2 文法：Sa||（T） TT，S|S （1）最左推导： S （ T ）（ T ，S ）（ S ，S ）（ a ，S ）（ a ， （T） ） （a， （T， S） ） (a,(S,S)) (a,(a,S)) (a,(a,a)) S(T,S)(S,S)((T),S)((T,S),S)((T,S,S),S)((S,S,S),S)(((T),S,S),S) (((T,S),S,S),S)(((S,S),S,

23、S),S)(((a,S),S,S),S)(((a,a),S,S),S) (((a,a),,S),S) (((a,a),,(T)),S)(((a,a),,(S)),S) (((a,a),,(a)),S) (((a,a),,(T)),a) 最右推导：S（T）（T，S）（T， （T） ）（T， （T，S） ）（T， （T，a） ）（T， （S，a） ） （T， （a，a） ）（S， （a，a） ）（a， （a，a） ） S（T，S）（T，a）（S，a）（ （T） ，a）（ （T,S） ，a）（ （T,(T)） ，a）（ （T,(S)） ，a） ((T,(a)）,a）（ （T,S,(a)）,a）

24、（ （T,,(a)） ，a）（ （S, ,(a)） ，a）（ （(T), ,(a)） ，a） (((T,S), ,(a)） ，a）（ （(T,a), ,(a)） ，a）（ （(S,a), ,(a)） ，a）（ （(a,a), ,(a)） ，a） （2） （ （ （a，a） ，， （a） ） ，a） （ （ （S，a） ，， （a） ） ，a） （ （ （T，a） ，， （a） ） ，a） （ （ （T，S） ，， （a） ） ，a） （ （（T），， （a） ） ，a） （ （S，， （a） ） ，a） （ （T，， （a） ） ，a） （ （T，S， （a） ） ，a） （ （T， （a）

25、） ，a） （ （T， （S） ） ，a） （ （T，（T）） ，a） （ （T，S） ，a） （（T），a） 12 （S，a） （T，a） （T，S） （T） S 移进归约过程： 步骤 栈 输入串 动作 0 # （ （ （a，a） ，， （a） ） ，a）# 初始 1 #（ （ （a，a） ，， （a） ） ，a）# 移进 2 #（ （ （a，a） ，， （a） ） ，a）# 移进 3 #（ （ （ A，a） ，， （a） ） ，a）# 移进 4 #（ （a ，a） ，， （a） ） ，a）# 移进 5 #（ （ （S ，a） ，， （a） ） ，a）# 归约 6 #（ （ （T ，a） ，

26、， （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）# 归约 1

27、7 #（ （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， a）# 移进 30 #（T，a ）# 移进 31 #（T，S ）

28、# 归约 32 #（T ）# 归约 33 #（T） # 移进 34 #S # 归约 13 P133-3：文法：G（S） ：Sa||(T) TT,S|S （1）FIRSTVT（S）= a、、( FIRSTVT（T）= ， 、a、、( LASTVT（S）= a、、 ） LASTVT（T）=， 、a、、 ） （2）算符优先分析表 a （ ） ， # a （ = ） ， # = （3）优先函数： a （ ） ， # f 6 6 2 6 4 2 g 7 7 7 2 3 2 f a f f ( f ) f , f # g a g g ( g ) g , g # 如果不考

29、虑#，则：优先函数： a （ ） ， f 4 4 2 4 4 g 5 5 5 2 3 分析过程： 栈 输入 # （a,(a,a)）# 初始 #( a,(a,a)）# 移进 #(a ,(a,a)）# 移进 #(S ,(a,a)）# 归约 #(S, (a,a)）# 移进 #(S,( a,a)）# 移进 #(S,(a ,a)）# 移进 #(S,(S ,a)）# 归约 #(S,(S, a)）# 移进 14 #(S,(S,a )）# 移进 #(S,(S,S )）# 归约 #(S,(T )）# 归约 #(S,(T) ）# 移进 #(S,S ）# 归约 #(T ）# 归约 #(T) # 移进 #S # 归约

30、 P134-5 （1） 考察I1、I6、I7: I1:存在移进-归约冲突，因为 Follow（S）=#,不包含 a 或 b，因此冲突可以使用 SLR 解决方 法解决。 I6：存在移进-归约冲突，因为 Follow（A）=a，b，因此无法使用 SLR 方法解决移进-归约冲 突 I7：存在移进-归约冲突，因为 Follow（S）=#，a，b，因此无法解决移进-归约冲突 所以不是 SLR(1)文法。 构造LR（1）项目集规范族： I0：SS SAS Sb ASA Aa I1：SS ASA ASA Aa SAS Sb I2：SAS SAS Sb ASA Aa S A I4：Sb b I3：Sa a a

31、 b I5：ASA ASA Aa SAS Sb I6：ASA SAS SAS Sb ASA Aa A S S A a a b I7：SAS ASA SAS Sb ASA Aa a A b b b a A A S S 15 I0: S.S,# S.AS,#/a/b S.b,#/a/b A.SA,a/b A.a,a/b I1: SS.,# AS.A,a/b A.SA,a/b A.a,a/b S.AS,a/b S.b,a/b S I2: SA.S,#/a/b S.AS,#/a/b S.b,#/a/b A.SA,a/b A.a,a/b A A I4: Sb.,#/a/b b b I3: Aa.,a/b

32、 a a I7: SAS.,#/a/b AS.A,a/b A.SA,a/b A.a,a/b S.AS,a/b S.b,a/b a a S I6: AS.A,a/b A.SA,a/b A.a,a/b S.AS,a/b S.b,a/b S I5: ASA.,a/b SA.S,a/b S.AS,a/b S.b,a/b A.SA,a/b A.a,a/b A I8: SA.S,a/b S.AS,a/b S.b,a/b A.SA,a/b A.a,a/b A I9: SAS.,a/b AS.A,a/b A.SA,a/b A.a,a/b S.AS,a/b S.b,a/b S A a I10: Sb.,a/b

33、b bb S a S S b S a A b A I5 b A I5 a I3 检查I5，ASA.，a/b，要求输入为a 或者b使用ASA归约，而S.b，a/b及A.a，a/b 要求移进，因此存在移进-归约冲突，所以不是 LR（1）文法。 P135-8 解答： 不存在左递归； 因为 Fist(AaAb)=a，First(BbBa)=b所以交集为空 所以该文法是 LL(1)文法。 I0=S.AaAb，S.BbBa，A.，B. I1=GO(I0，A)= SA.aAb I2=GO(I0，B)= SB.bBa I3=GO(I1,a)= SAa.Ab，A. I4=GO(I2,b)= SBb.Ba，B.

34、I5=GO(I3,A)= SAaA.b I6=GO(I4,B)= SBbB.a I7=GO(I5,b)= SAaAb. I8=GO(I6,a)= SBbBa. 考虑：I0:存在两个归约项目，A.,B.,Follow(A)=a,b，Follow(B)=a,b，所以冲突不能 解决，不是 SLR(1)文法。 16 第六章 P164-1 解答：表达式（4*7+1）*2 的附注语法树： L E.val=58 n T.val=58 T.val=29 * F.val=2 F.val=29 ( ) digit.val=2 E.val=29 + T.val=1 E.val=28 F.val=1 digit.va

35、l=1 T.val=28 T.val=4 * F.val=7 digit.val=7 F.val=4 digit.val=4 P164-2 + a b + ab (1) (2) p165-5 (1) EE 1 +T if ( E 1 .type = int) and (T.type = int) then E.type = int E ls e E . ty pe = r eal ET E .type = T .type Tnum. num T.type = real Tnum T . ty pe = int (2) EE 1 +T if (E1.type = int)

36、and (T.type = int) then E.type = int E.code = E 1 .code || T.code || + Else if (E 1 .type = real) and (T.type = real) E.type = real E.code = E 1 .code || T.code || + Else if E 1 .type = int then E.type = real E.code = E 1 .code ||inttoreal || T.code || + 17 Else E.type = real E.code = E 1 .code ||

37、T.code || inttoreal || + E nd if ET E . ty pe = T . ty pe E.code = T.code Tnum. num T.type = real E.code = num.num Tnum T.type = int E.code = num P164-7 SL 1 .L 2 S .v al = L 1 .val + L 2 .val / 2 L 2 .length SL S.val = L.val LL 1 B L.val = 2*L 1 .val + B.c L.length = L 1 .length + 1 L

38、B L. val = B .c L.length = 1 B0 B . c = 0 B1 B . c = 1 P165-11 对 D，L，T 设置综合属性 type。过程 addtype（id.entry，type）用来将标识符 id 的类型 type 填 入到符号表中。 （1） 翻译模式： Did L addtype （id.entry，L.type） L,id L 1 L . ty pe = L 1 .type ；addtype（id.entry，L 1 .type） L:T L.type = T.type Tinteger T.type = integer T

39、real T.type = real (2) 假设 Ttype 为已定义的表示“类型”的数据结构，预测翻译器如下： procedure D； var l_type：Ttype begin if sym = “id” then begin a dv an ce ; l _ty p e = L ; addtype(id.entry , l_type) end else error end； 18 procedure L； var l_type :Ttype； begin if s ym = “， ” then beg i n a dva nce ; if s ym =

40、 “ id” th en beg in a dv an ce ; l _ty p e = L ; a dd dty p e ( id. e ntr y ，l_type) end else error ; end else if sym = “:” then be gi n a dv ance ; l _ty pe = T ; e nd else error ; return (l_type) ； end； procedure T ; var t_type: Ttype ; begin if sym = “integer” then begin a

41、dvance ; t_type = integer ; end else if sym = “real” then begin advance ; t_type = real ; end else error return(t_type); end; 19 第七章 P217-1 a*（-b+c） 后缀式：ab-c+* a+b*（c+d/e） 后缀式：abcde/+*+ -a+b*（-c+d） 后缀式：a-bc-d+*+ not A or not（C or not D） 后缀式：A not C D not or not or （A and B）or（not C or D） 后缀式：A B

42、 and C not D or or （A or B）and（C or not D and E）后缀式： A B or C D not E and or and if （x + y）*z = 0 then （a+b）c else abc 后缀式：xy+z*0= ab+c abc if-then-else 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）-， （

43、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，T7 20 P218-8 自下而上分析过程中把赋值语句 A := B * （-C + D）翻译成四元式的步骤： 步骤 输入串 栈 PLACE 四元式 （1） A := B * （-C + D）

44、 （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 （6） （-C + D） i := E* A-B- （7） -C + D） i := E*（ A-B-- （8） C + D） i := E*（- A-B--- （9） + D） i := E*（-i A-B---C （10） + D） i := E*（-E A-B---C （-，C，-，T1） （11） + D） i := E*（E A-B--T1 （12） D ） i := E*（E+

45、A-B--T1- （13） ） i := E*（E+i A-B--T1-D （14） ） i := E*（E+E A-B--T1-D （+，T1，D，T2） （15） ） i := E*（E A-B--T2 （16） i := E*（E） A-B--T2- （17） i := E*E A-B-T2 （*，B，T2，T3） （18） i := E A-T3 （:=，T3，-，A） （19） A P218-5 设 A、B 为 10 x 20 的数组，C、D大小为 10 的数组，数组每维下届为 1，每个数据项宽度为 4， 则： Ai，j := Bi，j + CAk，1 + Di+j T1 := i

46、 * 20 T1 := T1 + j T2 := A 84 T3 := 4 * T1 T4 := i * 20 T4 := T4 + j T5 := B 84 T6 := 4 * T4 T7 := T5T6 T8 := k*20 T8 = T8 + 1 T9 := A 84 T10 := 4 * T8 T11 := T9T10 T12 := C 4 T13 := 4 * T11 T14 := T12T13 21 T15 := T7 + T14 T16 := i + j T17 := D 4 T18 := 4*T16 T19 :=T17T18 T20 :=T15 + T19 T2T3 := T2

47、0 P218-6 A or （B and not（C or D） ） ： E E A or M E E not M E E E or M E C D B t=100 f=101 quad=102 quad=104 quad=106 t=102 f=103 t=104 f=105 t=106 f=107 t=107 f=104，106 t=107 f=103，104，106 t=100，107 f=103，104，106 and 100： （jnz，A，-，0） 101： （j，-，-，102） 102： （jnz，B，-，104） 103： （j，-，-，0） 104： （jnz，C，-，0）

48、 105： （j，-，-，106） 106： （jnz，D，-，0） 107： （j，-，-，0） 22 P218-7 L L1 M S ; S while M1 do S1 E E1 and M1 E2 A

49、09 t=109 f=110 111 nextlist=110 nextlist=108,110 nextlist=101,103 nextlist=101,103 115 100： （j<，A，C，102） 101： （j，-，-，115） 102： （j<，B，D，104） 103： （j，-，-，115） 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） 11

50、2： （:=，T2，-，A） 113： （j，-，-，109） 114： （j，-，-，100） 115： 23 P219-12 （1） 如果该程序执行，则先会打印出： MAXINT-5 MAXINT-4 MAXINT-3 MAXINT-2 MAXINT-1 MAXINT 然后对于有些可能出现的整型数溢出而出现运行时的异常。 （2） 根据其语义，先确定 PA S C A L 语言 for语句的中间代码结构如下： t1 := initial t2 := final if t1 t2 goto L2 v := t1 L1：S 的代码 if v = t2 goto L2 v := v +

51、1 goto L1 L2： 为了便于语法制导的翻译，将 PA S C A L 语言的 for语句： Sfor V := E1 to E2 do S1 改写成如下产生式： SF do S1 Ffor v := E1 to E2 翻译模式如下： Ffor v := E1 to E2 F.nextlist := makelist(nextquad)； emit（j，E1.place，E2.place，0） ； emit（:=，E1.place，-，v.place） ； F.quad := nextquad； F.place1 := E2.place； F.place2 := entry（

52、v） ； SF do S1 backpatch（S1.nextlist，F.q uad） ； S.nextlist := merge（F.nextlist，makelist（nextquad） ） ； emit(j=，F.place1，F.place2，0)； emit（+，F.place2，1，F.place2） ； em it （j，-，-，F.quad） 24 第十章 P306-1： read C A :=0 B := 1 L1: A:=A+B if B C GOTO L2 B := B +1 GOTO L1 L2: wirte A halt B1 B2 B3 B4 r

53、ead C A := 0 B := 1 L1: A := A + B if B C GOTO L2 B := B +1 GOTO L1 L2: write A halt P306-2 read A , B F := 1 C := A*A read A , B F := 1 C := A*A D := B*B if C 100 goto L2 halt L2：F := F+1 goto L1 B1 B2 B3 B4 B5 D := B*B if C 100 goto L2 halt L2：F := F+1 goto L1 25 P306-3 基本块： B1： A := B*C D

54、:= B/C E :=A+D F := 2*E G :=B * C H :=G*G F :=H *G L := F M :=L B2： B := 3 D := A+C E : =A * C G :=B *F H :=A + C I :=A *C J :=H +I K := B * 5 L :=K +J M: =L n9 F、L、M 如果只有 G、 L、 M 在 基本块后还要被引 用，则优化为： n1 n2 2 C n3 * A，G n4 / D n5 + E n6 n7 F * n8 * H * G :=B*C S1 :=G*G L := S1*G M :

55、= L （S1 为临时变量） 如果只有 L 在基本块后 还要被引用， 则优化为： S1 :=B*C S2 :=S1*S1 L := S2*S1 （S1、S2 为临时变量） B n3 n2 n4 + D、 H n5 * n8 + n10 K n9 J + 如果只有 G、L、M 在基本块 后还要被引用，则优化为： G :=3*F S1:=A+C S2:=A*C S3:=S1+S2 L := 15 + S3 （S1、S2、S3 为临时变量） L，M G 3 n1 * n7 n6 E、I 如果只有 L 在基本块后还要 被引用，则优化为： S1:=A+C S2:=A*C S3:=S1+S2 L := 1

56、5 + S3 （S1、S2、S3 为临时变量） B 15 F AC 26 P307-4 对一下四元式程序，对其中循环进行循环优化： I ：=1 read J，K L： A ：=K* I B ：=J*I C ：=A* B w r ite C I ：=I + 1 if I < 100 goto L hal t 解答：首先进行基本块划分，画出程序流图：从图中可以看出需要优化的循环块为 B2 I ：= 1 read J，K L A ：= K * I B ：= J*I C ：=A*B w ir te C I ：= I + 1 if I<100 goto L halt B1 B2 B

57、3 I ：= 1 read J，K L C ：=A*B w ir te C A ：= A +K B ：= B +J I ：= I + 1 if I<100 goto L halt B1 B2 B3 A ：= K * I B ：= J*I B2 强度削弱 I ：= 1 read J，K A ：= K * I B ：= J*I L C ：=A*B w ir te C A ：= A +K B ：= B +J I ：= I + 1 T 1 ：=100*K if A

58、：= J*I T1：=100*K L C ：=A*B w ir te C A ：= A +K B ：= B +J if A