第08章 语法制导翻译和中间代码生成

《编译原理》课后习题答案第八章

第 8 章 语法制导翻译和中间代码生成

第 1 题

给出下面表达式的逆波兰表示(后缀式)： (1)a*(-b+c)

(2) if(x+y)*z=0 then s∶=(a+b)*c else s∶=a*b*c 答案：

给出下面表达式的逆波兰表示(后缀式)： (1) ab-c+*

(2)xy+z*0=sab+c*:=sab*c*:=￥（注：￥表示 if-then-else 运算）

如果写成这样： xy+z*0=sab+c*:=sabc**:=￥，则是错误的，因为写表达式和赋值语句 的中间代码序列，或是写它们的代码生成过程，必须注意按照算符优先序进行，这实际上是 按照 LR 分析过程进行的。例如：写出赋值语句 a:=a+b*c*(d+e)的四元式中间代码,当前四元 式序号为 100。不能写成：

100 (+,d,e,t1) 101 (*,b,c,t2) 102 (*,t2,t1,t3) 103 (+,a,t3,t4) 104 (:=,t4,-,a) 应该写成：

100 101 102 103 104

(*,b,c,t1) (+,d,e,t2) (*,t1,t2,t3) (+,a,t3,t4) (:=,t4,-,a)

第 2 题

请将表达式-(a+b)*(c+d)-(a+b+c)分别表示成三元式、间接三元式、四元式序列、树形、 逆波兰，当前序号为 100。 答案：

三元式： 100 (+, a, b)

101 (+, c, d) 102 (* , (1), (2))

盛威网（www.snwei.com）专业的计算机学习网站 1

《编译原理》课后习题答案第八章

103 104 105 106 (-, (3), /) (+, a, b) (+,(5),c) (- (4), (6))

间接三元式：

间接三元式序列 100 (+，a, b) 101 102 103 104 105

(+，c, d) (*，(1), (2)) (-，(3), /) (+，(1), c) (-，(4), (1))

间接码表 (100) (101) (102) (103) (100) (104) (105)

或者： 间接三元式：

100 (+，a, b) 101 (+，c, d) 102 (*，(1), (2)) 103 (-，(3), /) 104 (+，(1), c) 105 (-，(4), (1))

间接码表：100 101 102 103 100 104 105

四元式：

100 (+, a, b, t1) 101 (+, c, d, t2) 102 (*, t1, t2, t3) 103 (-, t3, /, t4) 104 (+, a, b, t5) 105 (+, t5, c, t6) 106 (-, t4, t6, t7) 树形：

盛威网（www.snwei.com）专业的计算机学习网站 2

《编译原理》课后习题答案第八章

逆波兰：ab+cd+*-ab+c+-

［典型例题］：

写出 if A and B and C > D then

if A

else G:=G+1; 的四元式序列, 翻译过程中, 采用 then 与 else 的最近匹配原则。

/* A and B and C>D 的四元式 */

(1) (jnz,A,_,3) (2) (j, _, _, 13) (3) (jnz,B,_,5) (4) (j, _, _, 13) (5) (j>,C,D,7) (6) (j, _, _, 13) (7) (j<,A,B,9) (8) (j, _, _, 11) (9) (:=,1, _, F) (10) (j, _, _,14) (11) (:=, 0, _,F) (12) (j, _, _,14) (13) (:=,G,1,G) (14)

/* A < B 的四元式 */ /* F:=1 */ /* F:=0 */

［典型例题］：

写出 WHILE A

IF A=1 THEN C:=C+1 ELSE

WHILE A<=D DO A:=A+2;的四元式序列。 (100) (j<,A,C,102) (101) (j,-,-,114) (102) (j<,B,D,104)

盛威网（www.snwei.com）专业的计算机学习网站 3

《编译原理》课后习题答案第八章

(103)

(105)

(110)

(112) (113) (114)

(j,-,-,114) (104) (j=,A,1,106) (j,-,-,109) (106) (+,C,1,T) (107) (:=,T,-,C) (108) (j,-,-,100) (109) (j<=,A,D,111) (j,-,-,100) (111)(+,A,2,T) (:=,T,-,A) (j,-,-,109)

盛威网（www.snwei.com）专业的计算机学习网站 4

《编译原理》课后习题答案第八章

第 3 题

采用语法制导翻译思想，表达式 E 的“值”的描述如下：

产生式 语义动作 (0) S′→E {print E.VAL}

(1) E→E1+E2 {E.VAL∶=E1.VAL+E2.VAL}

(2) E→E1*E2 {E.VAL∶=E1.VAL*E2.VAL} (3) E→(E1) {E.VAL∶=E1.VAL} (4) E→n {E.VAL∶=n.LEXVAL}

如采用 LR 分析方法，给出表达式(5*4+8)*2 的语法树并在各结点注明语义值 VAL。

答案：

盛威网（www.snwei.com）专业的计算机学习网站 5