《编译原理》(陈火旺版)课后作业参考答案ch6-10

1、第6章 属性文法和语法制导翻译7. 下列文法由开始符号S产生一个二进制数，令综合属性val给出该数的值：SL.LLLLBBB01 试设计求S.val的属性文法，其中，已知B的综合属性c, 给出由B产生的二进位的结果值。例如，输入101.101时，S.val=5.625，其中第一个二进位的值是4，最后一个二进位的值是0.125。【答案】产生式语义规则SL1. L2 S.val := L1.val + L2.val*2L2.length SL S.val:= L.val LL1B L.val:=L1.val*2+B.val;L. length:= L1.length +1 LB L.val:=B.

2、val;L. length:= 1 B0 B.val:= 0 B1 B.val:=1 11. 设下列文法生成变量的类型说明：L id LL, id L:TT integerreal (1) 构造一下翻译模式，把每个标识符的类型存入符号表；参考例6.2。【答案】产生式语义规则L id L1 S.val := L1.val + L2.val*2L2.length L, id L1 S.val:= L.val L :T L.val:=L1.val*2+B.val;L. length:= L1.length +1 T integer L.val:=B.val;L. length:= 1 T real

3、B.val:= 0 第7章 语义分析和中间代码产生1. 给出下面表达式的逆波兰表示（后缀式）： 【答案】原式后缀式(1) a*(-b+c) ab-c+*(2) a+b*(c+d/e)abcde/+*+(3) a+b*(-c+d)a-bc-d+*+(4) not A or not (C or not D)A not C D not or not or(5) (A and B) or (not C or D)A B and C not D or or(6) (A or B) and (C or not D and E)A B or C D not E and or and(7) if (x+y)*

4、z=0 then (a+b)c else abcif xy+z*0= then ab+c else abc3. 请将表达式(a+b)*(c+d)-(a+b+c)分别表示成三元式、间接三元式和四元式序列。 【答案】三元式(1)+ab(2)(1)(3)+cd(4)*(2)(3)(5)+ab(6)+(5)c(7)(4)(6)四元式(1)+abT1(2)T1 T2(3)+cdT3(4)*T2T3T4(5)+abT5(6)+T5cT6(7)T4T6T7间接三元式(1)+ab(2)(1)(3)+cd(4)*(2)(3)(5)+(1)c(6)(4)(5) 间接码表：(1)(2)(3)(4)(1)(5)(6)

5、4. 按7.3节所说的办法，写出下面赋值句A:=B*(C+D) 的自下而上语法制导翻译过程。给出所产生的三地址代码。四元式(1)uminuscT1(2)+T1DT2(3)*BT2T3(4):=T3A 【答案】5. 按照7.3.2节所给的翻译模式，把下列赋值句翻译为三地址代码： Ai, j:=B i, j + CA k, l + d i+j 【答案】中间代码中间代码(1)T1:=i*NA2(13)T10:=WA*T8(2)T1:=T1+j(14)T11:=T9T10(3)T2:=A-CA(15)T12:=C-Cc(4)T3:=WA*T1(16)T13:=Wc*T11(5)T4:=i* NB2(1

6、7)T14:=T12T13(6)T4:=T4+j(18)T15:=T7+ T14(7)T5:=B-CB(19)T16:=i+j(8)T6:=WB*T4(20)T17:=d-Cd(9)T7:=T5T6(21)T18:=Wd*T16(10)T8:=k* NA2(22)T19:=T17T18(11)T8:=T8+l(23)T20:=T15+ T19(12)T9:=A-CA(24)T2T3:=T206. 按7.4.1和7.4.2节的翻译办法，分别写出布尔式A or ( B and not (C or D) )的四元式序列。 【答案】用作数值计算时产生的四元式： 用作条件控制时产生的四元式：四元式(1)

7、orCDT1(2)notT1T2(3)andBT2T3(4)orAT3T4四元式四元式(1)( jnz, A, -, 0 )(5)( jnz, C, -, (4)(2)( j, -, -, (3)(6)( j, -, -, (7)(3)(jnz, B, -, (5)(7)( jnz, D, -, (5)(4)( j, -, -, 0 )(8)( j, -, -, (1)其中：右图中(1)和(8)为真出口，(4)(5)(7)为假出口。7. 用7.5.1节的办法，把下面的语句翻译成四元式序列： While AC and BD do if A=1 then C:=C+1 else while AD

8、do A:=A+2;【答案】四元式四元式(1)(j, A, C, (3)(9)( j, -, -, (1)(2)( j, -, -, 0)(10)( j, A, D,(12)(3)(j, B, D, (5)(11)( j, -, -, (1)(4)( j, -, -, 0 )(12)(+, A, 2, T2 )(5)(j=, A, 1, (7)(13)(:=,T2, -, A )(6)( j, -, -, (10) )(14)( j, -, -, (10)(7)(+, C, 1, T1 )(15)( j, -, -, (1)(8)(:=,T1, -, C )第9章 运行时存储空间组织4. 下面

9、是一个Pascal程序：program PP (input, output); VAR k: integer; FUNCTION F (n: integer): integer; beginif n=0 then F:=1 else F:=n*F(n-1); end;begin K:=F(10); end. 当第二次( 递归地) 进入F后，DISPLAY的内容是什么？当时整个运行栈的内容是什么？【答案】第1次进入F后，运行栈的内容： 第2次进入F后，运行栈的内容：10主程序PF4908n(形参)71(形参个数)62(全局display)5返回地址403k20(display)1返回地址0017

10、主程序P第1次F第2次F1116015n(形参)141(形参个数)139(全局display)12返回地址114104908n(形参)71(形参个数)62(全局display)5返回地址403k20(display)1返回地址00 第2次进入F后，Display内容为： 11 05. 对如下的Pascal程序，画出程序执行到(1)和(2)点时的运行栈。program Tr (input, output); VAR i: integer; d: integer; procedure A ( k: real ); VAR p: char; procedure B; VAR c: char; Beg

11、in (1) end; Bprocedure C; VAR t: real; Begin (2) end; C Begin B; C; end; A Begin main A(d); end.【答案】运行到(1) 时的运行栈：（静态链） 运行到(2) 时的运行栈：（静态链）15c140(形参个数)13512返回地址11510p9k(形参)81(形参个数)706返回地址504d3i20 1返回地址0015TrACc140(形参个数)13512返回地址11510p9k(形参)81(形参个数)706返回地址504d3i20 1返回地址00TrAB 【答案】运行到(1) 时的运行栈：（Display表

12、） 运行到(2) 时的运行栈：（Display表）20主程序TrABc1913185170160(形参个数)1510(全局display)14返回地址13512p1151009k(形参)81(形参个数)72(全局display)6返回地址504d3i20(display)1返回地址0020主程序TrACt1913185170160(形参个数)1510(全局display)14返回地址13512p1151009k(形参)81(形参个数)72(全局display)6返回地址504d3i20(display)1返回地址006. 有如下示意的Pascal源程序，并已知在运行时刻，以过程为单位对程序中的

13、变量进行动态存储分配。当运行主程序而调用过程语句X时，试分别给出以下时刻的运行栈的内容和Display的内容。(1) 已开始而尚未执行完毕标号为10的语句；(2) 已开始而尚未执行完毕标号为11的语句；program main; VAR a, b, c: integer; procedure X ( i, j: integer); X VAR d, e: real;procedure Y; Y VAR f, g: real; Begin end; Yprocedure Z( k: integer); Z VAR h, i, j: real; Begin end; Z Begin 10: Y;

14、11: Z; end; XBegin main X (a, b); end. main mainX (a, b)Z【答案】(1) 运行到标号10时，运行栈的内容： (2) 运行到标号11时，运行栈的内容：26j25i24h231622621020k191(形参个数)1812(全局display)17返回地址16615e14d13612011j10i92(形参个数)82(全局display)7返回地址605c4b3a20 (display)1返回地址0024mainX (a, b)Yg23f2216216200190(形参个数)1812(全局display)17返回地址16615e14d1361

15、2011j10i92(形参个数)82(全局display)7返回地址605c4b3a20(display)1返回地址00 main X(a,b) Y main X(a,b) Y Z第10章 优化1. 试把以下程序划分为基本块并作出其程序流图。 real C A:=0 B:=1L1: A:=A+B if BC goto L2 B:=B+1 goto L1L2: write A halt 【答案】 real C A:=0 B:=1L1: A:=A+B if BC goto L2 B:=B+1 goto L1L2: write A halt 2. 试把以下程序划分为基本块并作出其程序流图。 real

16、 A, B F:=1 C:=A*AD:=B*Bif C100 goto L2haltL2: F:=F-1 goto L1【答案】 real A,B F:=1 C:=A*AD:=B*Bif C100 goto L2halt 3. 试对以下基本块B1和B2：B1: A:=B*C D:=B/CE:=A+DF:=2*EG:=B*CH:=G*GF:=H*GL:=FM:=LB2: B:=3 D:=A+CE:=A*CG:=B*FH:=A+CI:=A*CJ:=H+IK:=B*5L:=K+JM:=L 分别应用DAG对它们进行优化，并就以下两种情况分别写出优化后的四元式序列：(1) 假设只有G,L,M在基本块后面还要被引用；