编译原理第8章作业及习题参考答案.doc

编译原理作业参考答案 - 3 -第八章 语法制导翻译和中间代码生成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∧CØD∨∨(7) xy+z*0=sab+c*:=sab*c*:=￥（注：￥表示if-then-else运算）￥=:=*0:=+xyzs+cxabs*c*ab2. 请将表达式-(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。

S’*E1E2E0E32E5.VAL=585*E5E6+E44E6.VAL=4E4.VAL=8E3.VAL=20E1.VAL=28E2.VAL=2E0.VAL=56Print(56)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的语法树，然后设置相应的属性进行语义规则的创立产生式 语义规则 S ->L 1.L2 S->L S.val:=L.val L -> L1B L.val:=L1.val*2+B.val L.length:=L1.length+1 L -> B L.val:=B.val L.length:=1 B -> 0 B.val:=0 B -> 1 B.val:=1 S.LLBLBBLBLLBB解2：产生式语义规则          S -> L S.val:=L.val;           S -> L1.L2 S.val:=L1.val+L2.val*L2.p;           L -> B L.val:=B.val;    L.p:=2-1;           L -> L1B L.val:=L1.val*2+B.val; L.p:=L.p*2-1;          B -> 0 B.val:=0;           B -> 1 B.val:=1; 。