编译原理第8章作业及习题参

1．给出下面表达式的逆波兰表示(后缀式)：

(1) a*(-b+c) 

(4) (A∧B) ∨(C ∨ D)

(7) if(x+y)*z=0 then s∶=(a+b)*c else s∶=a*b*c

解(1) ab-c+* 

  (4) AB∧CD∨∨

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

2. 请将表达式-(a+b)*(c+d)-(a+b+c)分别表示成三元式、间接三元式和四元式序列。

答案：三元式 

　　(1) (+ a, b) 

　　(2) (+ c, d) 

　　(3) (* (1), (2)) 

　　(4) (- (3), /)

　　(5) (+ a, b)

(6) (+,(5),c)

(7) (- (4), (6))

　　间接三元式

　　间接三元式序列 　　间接码表

　　(1) (+ a, b)　　　　(1)

　　(2) (+ c, d)　　　　(2) 

　　(3) (* (1), (2))　　(3) 

　　(4) (- (3), /) 　 　(4)

　　(5) (- (4), (1))　　(1) 

(6) (- (4), (5))　　(5)

(6)

　　四元式

　　(1) (+, a, b, t1)

　　(2) (+, c, d, t2)

　　(3) (*, t1, t2, t3) 

　　(4) (-, t3, /, t4) 

(5) (+, a, b, t5)

(6) (+, t5, c, t6)

　　(6) (-, t4, t6, t7)

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。

4. 假如习题3中表达式E的“值”有两种类型：整型和实型。语义处理增加"类型匹配检查"，请给出相应的语义描述。

解：

　　(0) S′→E { if error≠1 then print E.VAL} 

　　(1) E→E1+E2 { if E1.TYPE=int AND E2.TYPE=int then

　　　　　　　　　　　begin

　　　　　　　　　　　　E.VAL:=E1.VAL + E2.VAL;

　　　　　　　　　　　　E.YTPE:=int;

　　　　　　　　　　　end 

　　　　　　　　　else if E1.TYPE=real AND E2.TYPE=real then 

　　　　　　　　　　　　　begin 

　　　　　　　　　　　　　　E.VAL:=E1.VAL + E2.VAL;

　　　　　　　　　　　　　　E.YTPE:=real; 

　　　　　　　　　　　　　end 

　　　　　　　　　　　else error=1 

　　　　　　　　　} 

　　(2) E→E1*E2 { if E1.TYPE=int AND E2.TYPE=int then 

　　　　　　　　　　　begin

　　　　　　　　　　　　E.VAL:=E1.VAL * E2.VAL;; 

　　　　　　　　　　　　E.YTPE:=int; 

　　　　　　　　　　　end 

　　　　　　　　　else if E1.TYPE=real AND E2.TYPE=real then

　　　　　　　　　　　　begin

　　　　　　　　　　　　　E.VAL:=E1.VAL * E2.VAL;; 

　　　　　　　　　　　　　E.YTPE:=real;

　　　　　　　　　　　　end 

　　　　　　　　　　　else error=1

　　　　　　　　　} 

　　(3) E→(E1) { E.VAL:=E1.VAL; 

　　　　　　　　E.TYPE:=E1.TYPE } 

　　(4) E→n { E.VAL:=n.LEXVAL;

　　　　　　　　E.TYPE:=n.LEXTYPE }

5. 令综合属性 val 给出在下面的文法中的 S 产生的二进制数的值 ( 如，对于输入 101.101 ，则S.val=5.625)。

S -> L.L | L

L -> LB | B

B -> 0 | 1

解1：提示画出对应于输入101.101的语法树，然后设置相应的属性进行语义规则的创立。

解2：