编译原理答案

7 8 9 10 11 12 13 14 0346 03461 034618 0346189 0346187 0346186 0346182 03461820 #V:=T #V:=T* #V:=T*( #V:=T*(c #V:=T*(F #V:=T*(T #V:=T*(E #V:=T*(E+ -Va-Tb -Va-Tb -Va-Tb -Va-Tb-Fc -Va-Tb-Tc -Va-Tb-Ec -Va-Tb-Ec -Va-Tb-Ec -Va-Tb-Ec-Fd -Va-Tb-Ec-Td -Va-Tb-T1 -Va-Tb-T1 -Va-Tb-T1 -Va-T2 -Va-T2 -Va-T2 - *(c+d)# (c+d)# c+d)# +d)# +d)# +d)# +d)# d)# )# )# )# )# # # # # # F∷＝i T∷＝F E∷＝T F∷＝i T∷＝F E∷＝E(1)+T F∷＝(E) T∷＝T(1)*F E∷＝T A∷＝V:=E acc SUB7 SUB5 SUB3 SUB7 SUB5 SUB2 SUB6 SUB4 SUB3 SUB1 (+, c, d, T1) (+, c, d, T1) (+, c, d, T1) (*, b, T1, T2) (*, b, T1, T2) (:=, T2, , a) 15 034618209 #V:=T*(E+d 16 034618207 #V:=T*(E+F 17 034618203 #V:=T*(E+T 18 19 20 21 22 23 0346182 03461825 034614 0346 0345 01 #V:=T*(E #V:=T*(E) #V:=T*F #V:=T #V:=E #A

P195 10. 将下列布尔表达式翻译成四元式序列，并给出语法制导翻译过程（作为条件控制）：

a∧b∧c>d

解：四元式序列如下所示：

(1) (jnz, a, , 3) a的四元式，当a为真时，则转向第3个四元式 (2) (j, , , 0)

(3) (jnz, b, , 5) b的四元式，当b为真时，则转向第3个四元式 (4) (j, , , 2) 无条件转向第2个四元式 (5) (j>, c, d, 0) c>d的四元式

(6) (j, , , 4) 无条件转向第4个四元式

?TC表示真出口的链首

?FC表示假出口的链首 每个链尾的四元式第4分量均为0，表示结束标记

语法制导翻译过程 四元式 a∧b∧c>d

(1) E∧b∧c>d 100 (jnz, a, , 0/102)

{E?TC:=100; E?FC:=101} 101 (j, , , 0)

∧

(2) Eb∧c>d

{BP(E(1)?TC=100, NXQ=102); ∧

E?FC:= E(1)?FC=101}

∧

(3) EE∧c>d 102 (jnz, b, , 0/104)

{E?TC:=102; E?FC:=103} 103 (j, , , 0/101)

∧∧

(4) EE’c>d

３３

{BP(E(1)?TC=102, NXQ=104); ∧

E’?FC:= E(1)?FC=103}

∧∧

(5) EE’E 104 (j>, c, d, 0)

{E?TC:=104; E?FC:=105} 105 (j, , , 0/103)

∧

(6) EE(1)

∧

{ E(1)?TC:= E?TC =104; E(1)?FC:= MERG(E’?FC=103, E?FC=105)=105} (7) E(2)

∧

{ E(2)?TC= E(1)?TC =104; E(2)?FC:= MERG(E?FC=101, E?FC=105)=105}

第十二次作业：

P195 12. 写出下列条件赋值语句的四元式序列： z := if a>c then x+y else x+y-0.5

解：根据语义子程序，其条件赋值语句四元式序列为：

100 (j>, a, c, 102) 101 (j, , , 105) 102 (+, x, y, T1) 103 (:=,T1, , z) 104 (j, , , 108) 105 (+, x, y, T2) 106 ( -, T2, 0.5, T3) 107 (:=,T3, -, z) 108

P195 13. 将下列条件语句翻译成四元式序列：

if x=y+1 then x := x*y else while x<>0 do begin x :=x-1; y :=y+2 end

解：根据语义子程序，其条件赋值语句四元式序列为：

100 (+, y, 1, T1) 101 (j=, x, T1, 103) 102 (j, , , 106) 103 (*, x, y, T2) 104 (:=,T2, , x) 105 (j, , , 113) 106 (j<>, x, 0, 108) 107 (j, , , 113) 108 (-, x, 1, T3) 109 (:=,T3, , x) 110 (+, y, 2, T4) 111 (:=,T4, , y) 112 (j, , , 113) 113

P195 14. 将下列while语句翻译成四元式序列：

(2) while a

３４

if a=1 then c :=c+1 else while a<=d do a :=a+2 一 语法制导翻译过程: (1) W A

{W·Q∪AD:=100}

(2) WE(1)∧B

{BACKPATCH(E(1)·TC:=100,NXQ=102); E·FC:= E(1)·FC:=101}

(4) WEE(2) do...... 102(J<,B,D,104) { E(2)·TC:=102;E(2)·FC:=103} 103(J,-,-,101) (5) WE do...... {E·TC:=E(2)·TC:=102; E·FC:=MERG(E·FC=101,E(2)·FC=103)=103} (6) Wif A:=1 then......

{BACKPATCH(E·TC=102,NXQ=104); W·CHAIN:=E·TC=103; W·Q∪AD:=W·Q∪AD=100} (7) W if E then C:=C+1...... {E·TC:=104;E·FC:=105} 104(J=,A,’1’.106) 105(J,-,-,1O9) (8) WC C:=C+1 else...... {BACKPATCH(E·TC=104,NXQ=106); C·CHAIN:=E·FC=105}

(9) WCS(1) else...... 106(+,C,’1’,T1) {S(1)·CHAIN:=0; 107(:=,T1,-,C) T1:=NEWTEMP} (10) WT while A<=D do......

{q:=108; 108(J,-,-.100) BACKPATCH(C·CHAIN=105,NXQ=109);

T·CHAIN:=MFRG(S(1)·CHAN=0,q:=108)}

P

A

A

A

A

d

dd

d

d

d

dP

３５

(11) WTW’A<=D do......

{W’·Q∪AD:=NXQ=109} (12) WTW’E do A:=A+2

{E·TC:=109; 109(J:=,A,D,111) E·FC:=110} 110(J,-,-,100) (13) WTW A:=A+2

{BACKPATCH(E·TC=109,NXQ=111); W ·CHAIN:=E·FC=110; W ·Q∪AD:=W·Q∪AD=109} (14) WTWS(1)

{S·CHAIN:=0; 111(+,A,’2’,T2) T2:=NEWTEMP} 112(:=,T2,-,A) (15) WTS(2)

{BACKPATCH(S(1)·CHAINW·Q∪AD=109) S(2)·CHAIN:=W·CHAIN=110} 113(J,-,-,109)

d

d’

d’

dPdP

d’

dd

dP

ddP

dP

(16) WS(1)

P

{S·CHAIN:=MERG(T·CHAIN=108; S(1)·CHAIN=110)=110} (17) S {BACRPATCH(S(1) ·CHAIN=110,WQ∪AD=100);

d

d

S·CHAIN:=W·CHAIN=103} 114(J,-,-,100) 二 序列：

100(J<,A,C,102); 101(J,-,-,0)

102(J<,B,D,104) 103(J,-,-,101) 104(J=,A,’1’.106)

３６

105(J,-,-,1O9) 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,-,-,100) 115 S·CHAIN=103

P195 15. 根据for循环语句和条件语句的语义子程序，for i:=a+b*2 to c+d+10 do if h>g then p:=p+1被翻译成如下四元式序列：

100 (*, b, 2, T1) 101 (+, a, T1, T2) 102 (:=, T2, , i) 103 (+, c, d, T3) 104 (+, T3, 10, T4) 105 (:=, T4, , T) 106 (j, , , 108) 107 (+, i, 1, i) 108 (j>, i, T, 114) 109 (j>, h, g, 111) 110 (j, , , 113) 111 (+, p, 1, T5) 112 (:=, T5, , p) 113 (j, , , 107) 114 115

３７