编译原理课后作业参考答案

1、第 6 章 属性文法和语法制导翻译7. 下列文法由开始符号 S 产生一个二进制数，令综合属性 val 给出该数的值：例如，试设计求的属性文法， 其中，已知 B 的综合属性 c, 给出由 B产生的二进位的结果值。 输入时， =，其中第一个二进位的值是 4，最后一个二进位的值是。【答案】产生式语义规则S L1. L 2 := + *2SL := LL1B :=*2+;L. length:=+1 LB :=;L. length:=1 B0 := 0 B1 :=1 11. 设下列文法生成变量的类型说明：L id LL, id L :T T integer (1) 构造一下翻译模式，把每个标识符的类型存

2、入符号表；参考例。 【答案】产生式语义规则L id L 1 := + *2L, id L 1 := L :T :=*2+;L. length:=+1 T integer :=;L. length:=1 T real := 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

3、 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)*z=0 then (a+b) c else a b cif xy+z*0= then ab+c else ab c3. 请将表达式 (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)T1T2(3 )+cdT3(

4、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)4. 按节所说的办法，写出下面赋值句A:=B*( C+D) 的自下而上语法制导翻译过程。给出所产生的三地址代码。四元式(1 )uminuscT1(2+T1DT2答案】)(3 )BT2T3(4 ):=T3A5. 按照 7.3.2 节所给的翻译模式，把下列赋值句翻译为三地址代码： Ai, j:=B i, j + CA k, l + d i+j的四元式序【答案

5、】中间代码中间代码(1)T1:=i*N A2(13)T10:=WA*T8(2)T1:=T 1+j(14)T11:=T 9T 10(3)T2:=A-C A(15)T12:=C-C c(4)T3:=WA*T1(16)T13:=Wc*T11(5)T4:=i* N B2(17)T14:=T 12T 13(6)T4:=T 4+j(18)T15:=T 7+ T 14(7)T5:=B-C B(19)T16:=i+j(8)T6:=WB*T4(20)T17:=d-C d(9)T7:=T 5T 6(21)T18:=Wd*T 16(10)T8:=k* N A2(22)T19:=T 17T 18(11)T8:=T 8

6、+l(23)T20:=T 15+ T 19(12)T9:=A-C A(24)T2T 3:=T 206. 按 7.4.1 和节的翻译办法，分别写出布尔式A or ( B and not (C or D) )列。【答案】用作数值计算时产生的四元式： 用作条件控制时产生的四元式：四元式(1 )orCDT1(2 )notT1T2(3 )andBT2T3(4orAT3T4)其中：右图中 (1) 和 (8) 为真出口，(4)(5)(7) 为假出口。7. 用 7.5.1 节的办法， 把下面的语句 翻译成四元式序列：While AC and BD do四元式四元式(1)( jnz, A, -,0 )(5)(

7、jnz, C, -, (4)(2)( j, -, -, (3)(6)( j, -, -, (7)(3)(jnz, B, -,(5)(7)( jnz, D, -, (5)(4)( j, -, -, 0 )(8)( j, -, -, (1)if A=1 then C:=C+1else while AD doA:=A+2;答案】四元式四元式(1)(j,(3)A,C,(9)( j, -, -, (1)(2)( j, -, -, 0)(10)( j , A, D,(12)(3)(j,(5)B,D,(11)( j, -, -, (1)(4)( j, -, -, 0 )(12)(+, A, 2, T 2 )

8、(5)(j=,(7)A,1,(13)(:=,T 2, -, A )(6)( j, -, -,(10) )(14)( j, -, -, (10)(7)(+, C, 1, T1 )(15)( j, -, -, (1)(8)(:=,T1, -, C )第 9 章 运行时存储空间组织4. 下面是一个 Pascal 程序：program PP (input, output);VAR k: integer;FUNCTION F (n: integer): integer; beginif n=0 then F:=1else F:=n*F(n-1);end;begin K:=F(10);end.当第二次 (

9、 递归地 ) 进入 F后， DISPLAY的内容是什么当时整个运行栈的内容是什么 【答案】第 2 次进入 F 后，运行栈的内容：109876543210第 1 次进入 F 后，运行栈的内容：主程序 P第 2 次进入 F 后， Display 内容为：1105. 对如下的 Pascal 程序，画出程序执行到 (1) 和 (2) 点时的运行栈。program Tr (input, output);VAR i: integer; d: integer;procedure B;VAR c: char;Begin (1) end; B procedure C; VAR t: real; Begin (2

10、) end; CBeginB;C;end; A Begin main A(d);end.答案】运行到 （1） 时的运行栈： （静态链）15c140（ 形参个数 ）B13512返回地址11510p9k（ 形参 ）81（ 形参个数 ）A706返回地址504d3i20Tr1返回地址00答案】运行到 （2） 时的运行栈： （ Display 表）运行到 （1） 时的运行栈： （ Display 表）20c1913185170B160（ 形参个数 ）1510（ 全局 display）14返回地址13512p1151009k（ 形参 ）A81（ 形参个数 ）72（ 全局 display）6返回地址主程序2

11、0191817161514131211109876543210t13500（ 形参个数 ） 10（ 全局 display） 返回地址5 p50 k（ 形参 ） 1（ 形参个数 ） 2（ 全局 display） 返回地址0di 0（display） 返回地址0CA主程序6. 有如下示意的 Pascal 源程序，并已知在运行时刻，以过程为单位对程序中的变量进行 动态存储分配。当运行主程序而调用过程语句 X 时，试分别给出以下时刻的运行栈的内 容和 Display 的内容。(1) 已开始而尚未执行完毕标号为 10 的语句；(2) 已开始而尚未执行完毕标号为 11 的语句；program main;V

12、AR a, b, c: integer; procedure X ( i, j: integer);XVAR d, e: real; procedure Y; Y VAR f, g: real; Beginend; Yprocedure Z（ k: integer）; Z VAR h, i, j: real;BeginBegin10: Y;11: Z;答案】(1)2423222120191817161514131211109876543210gf1660Y0（ 形参个数 ）12( 全局 display)返回地址6ed60X (a, b)ji2（ 形参个数 ）2( 全局 display)返回地址

13、0cbamain0(display)返回地址0运行到标号 10 时，运行栈的内容： （2）main X(a,b) Ymain运行到标号 11 时，运行栈的内容：第 10 章 优化答案】答案】1. 试把以下程序划分为基本块并作出其程序流图。real CA:=0B:=1L1: A:=A+Bif B C goto L2B:=B+1goto L1L2: write Ahalt2. 试把以下程序划分为基本块并作出其程序流图。real A, BF:=1C:=A*A D:=B*B if C100 gotoL2 haltL2: F:=F-13. 试对以下基本块 B1和 B2：B1: A:=B*CD:=B/CE:=A+DF:=2*EG:=B*CB2: B:=3D:=A+CE:=A*CG:=B*FH:=A+CI:=A*C分别应用 DAG对它们进行优化，并就以下两种情况分别写出优化后的四元式序列：(1) 假设只有 G,L,M 在基本块后面还要被引用；(2) 假设只有 L 在基本块后面还要被引用。【答案】B1 基本块： (1) G,