2022年《编译原理》课后作业参考答案ch- .pdf

《2022年《编译原理》课后作业参考答案ch- .pdf》由会员分享，可在线阅读，更多相关《2022年《编译原理》课后作业参考答案ch- .pdf（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 第 6 章 属性文法和语法制导翻译7.下列文法由开始符号S产生一个二进制数，令综合属性val 给出该数的值：试设计求 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:=

2、B.val; L. length:= 1 B0 B.val:= 0 B1 B.val:=1 11. 设下列文法生成变量的类型说明：(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 B.val:= 0 SL.L L LLBB B0

3、1 L id L L, id L:T T integerreal 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 10 页 - - - - - - - - - 2 第 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

4、 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)*z=0 then (a+b) c else abc if xy+z*0= then ab+celse abc3. 请将表达式 (a+b)*(c+d)-(a+b+c) 分别表示成三元式、间接三元式和四元式序列。【答案】间接码表：(1) (2)(3)(4)(1)(5)(6) 4. 按 7.3 节所说的办法， 写

5、出下面赋值句A:=B* ( C+D ) 的自下而上语法制导翻译过程。给出所产生的三地址代码。【答案】三元式(1) + a b (2)(1) (3) + c d (4) * (2) (3) (5) + a b (6) + (5) c (7) (4) (6) 四元式(1) + a b T1 (2)T1 T2 (3) + c d T3 (4) * T2 T3 T4 (5) + a b T5 (6) + T5 c T6 (7) T4 T6 T7 间接三元式(1) + a b (2)(1) (3) + c d (4) * (2) (3) (5) + (1) c (6) (4) (5) 四元式(1) um

6、inus c T1 (2)+ T1 D T2 (3) * B T2 T3 (4) := T3 A 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 10 页 - - - - - - - - - 3 5. 按照 7.3.2 节所给的翻译模式，把下列赋值句翻译为三地址代码：Ai, j:=B i, j + CA k, l + d i+j 【答案】6. 按 7.4.1 和 7.4.2 节的翻译办法， 分别写出布尔式A or ( B and not (C or D) ) 的四元式序列

7、。【答案】用作数值计算时产生的四元式：用作条件控制时产生的四元式：其中：右图中 (1)和(8)为真出口， (4)(5)(7) 为假出口。7. 用 7.5.1 节的办法，把下面的语句翻译成四元式序列：While AC and BD do if A=1 then C:=C+1 else while AD do A:=A+2; 【答案】中间代码中间代码(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(

8、17) 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:=T20四元式(1) or C D T1(2)not T1T2(3) and B T2T3(4) or A T3T4四元式四元式(1) ( jnz, A, -, 0 )

9、(5) ( jnz, C, -, (4) (2)( j, -, -, (3) (6) ( j, -, -, (7) (3) (jnz, B, -, (5) (7) ( jnz, D, -, (5) (4) ( j, -, -, 0 ) (8) ( j, -, -, (1) 四元式四元式名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 10 页 - - - - - - - - - 4 (1) (j, A, C, (3) (9) ( j, -, -, (1) (2)( j, -

10、, -, 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 ) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - -

11、- 名师精心整理 - - - - - - - 第 4 页，共 10 页 - - - - - - - - - 5 第 9 章 运行时存储空间组织4. 下面是一个Pascal程序：当第二次 ( 递归地 ) 进入 F 后， DISPLAY 的内容是什么？当时整个运行栈的内容是什么？【答案】第 1 次进入 F 后，运行栈的内容：第 2 次进入 F 后，运行栈的内容：第 2 次进入 F 后， Display 内容为：5. 对如下的 Pascal程序，画出程序执行到(1)和(2)点时的运行栈。10 4 9 0 8 n(形参 ) 7 1(形参个数 ) 6 2(全局 display) 5 返回地址4 0 3

12、k 2 0(display) 1 返回地址0 0 17 11 16 0 15 n(形参 ) 14 1(形参个数 ) 13 9(全局 display) 12 返回地址11 4 10 4 9 0 8 n(形参 ) 7 1(形参个数 ) 6 2(全局 display) 5 返回地址4 0 3 k 2 0(display) 1 返回地址0 0 11 0 program PP (input, output); VAR k: integer; FUNCTION F (n: integer): integer; begin if n=0 then F:=1 else F:=n*F(n-1); end; be

13、gin K:=F(10); end. 主程序 P F 主程序 P 第 1 次 F 第 2 次 F program Tr (input, output); VAR i: integer; d: integer; procedure A ( k: real ); VAR p: char; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 10 页 - - - - - - - - - 6 【答案】运行到 (1) 时的运行栈： （静态链）运行到 (2) 时的运行栈：（静态链）15

14、c 14 0(形参个数 ) 13 5 12 返回地址11 5 10 p 9 k(形参 ) 8 1(形参个数 ) 7 0 6 返回地址5 0 4 d 3 i 2 0 1 返回地址0 0 15 c 14 0(形参个数 ) 13 5 12 返回地址11 5 10 p 9 k(形参 ) 8 1(形参个数 ) 7 0 6 返回地址5 0 4 d 3 i 2 0 1 返回地址0 0 procedure B; VAR c: char; Begin (1)end; B procedure C; VAR t: real; Begin (2)end; C Begin B; C; end; A Begin main

15、 A(d); end. Tr A B Tr A C 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 10 页 - - - - - - - - - 7 【答案】运行到 (1) 时的运行栈： （Display 表）运行到 (2) 时的运行栈： （Display 表）6. 有如下示意的Pascal源程序，并已知在运行时刻，以过程为单位对程序中的变量进行动态存储分配。当运行主程序而调用过程语句X 时，试分别给出以下时刻的运行栈的内容和 Display 的内容。(1) 已开始而尚未

16、执行完毕标号为10 的语句；(2) 已开始而尚未执行完毕标号为11的语句；20 c 19 13 18 5 17 0 16 0(形参个数 ) 15 10(全局 display) 14 返回地址13 5 12 p 11 5 10 0 9 k(形参 ) 8 1(形参个数 ) 7 2(全局 display) 6 返回地址5 0 4 d 3 i 2 0(display) 1 返回地址0 0 20 t 19 13 18 5 17 0 16 0(形参个数 ) 15 10(全局 display) 14 返回地址13 5 12 p 11 5 10 0 9 k(形参 ) 8 1(形参个数 ) 7 2(全局 dis

17、play) 6 返回地址5 0 4 d 3 i 2 0(display) 1 返回地址0 0 主程序 Tr A B 主程序 Tr A C 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; Y procedure Z( k: integer); Z VAR h, i, j: real; Begin end; Z 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - -

18、- - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 10 页 - - - - - - - - - 8 【答案】(1) 运行到标号10 时，运行栈的内容：(2) 运行到标号11 时，运行栈的内容：main X(a,b) Ymain X(a,b) Y Z26 j 25 i 24 h 23 16 22 6 21 0 20 k 19 1(形参个数 ) 18 12(全局 display) 17 返回地址16 6 15 e 14 d 13 6 12 0 11 j 10 i 9 2(形参个数 ) 8 2(全局 display) 7 返回地址6 0 5 c 4 b 3 a 2

19、 0 (display) 1 返回地址0 0 24 g 23 f 22 16 21 6 20 0 19 0(形参个数 ) 18 12(全局 display) 17 返回地址16 6 15 e 14 d 13 6 12 0 11 j 10 i 9 2(形参个数 ) 8 2(全局 display) 7 返回地址6 0 5 c 4 b 3 a 2 0(display) 1 返回地址0 0 Begin 10: Y; 11: Z; end; X Begin main X (a, b); end. main main X (a, b) Y main X (a, b) Z 名师资料总结 - - -精品资料欢

20、迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 10 页 - - - - - - - - - 9 第 10 章 优化1. 试把以下程序划分为基本块并作出其程序流图。【答案】2. 试把以下程序划分为基本块并作出其程序流图。【答案】real C A:=0 B:=1 L1: A:=A+B if BC goto L2 B:=B+1 goto L1 L2: write A halt real C A:=0 B:=1 L1: A:=A+B if BC goto L2 B:=B+1 goto L1 L2: write

21、A halt real A, B F:=1 C:=A*A D:=B*B if C100 goto L2 halt L2: F:=F-1 real A,B F:=1 C:=A*A D:=B*B if C100 goto L2 halt 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 10 页 - - - - - - - - - 10 3. 试对以下基本块B1 和 B2：分别应用 DAG 对它们进行优化，并就以下两种情况分别写出优化后的四元式序列：(1)假设只有 G,L,M

22、在基本块后面还要被引用；(2)假设只有 L 在基本块后面还要被引用。【答案】B1 基本块： (1) G, L, M 可用(2) L 可用B2 基本块： (1) G, L, M 可用(2) L 可用B1: A:=B*C D:=B/C E:=A+D F:=2*E G:=B*C H:=G*G F:=H*G L:=F M:=L B2: B:=3 D:=A+C E:=A*C G:=B*F H:=A+C I:=A*C J:=H+I K:=B*5 L:=K+J M:=L (1) G:=B*C (2) H:=G*G (3) L:=H*G (4) M:=L (1) G:=B*C (2) H:=G*G (3) L:=H*G (1) D:=A+C (2) E:=A*C (3) G:=3*F (4) J:=D+E (5) L:=15+J (6) M:=L (1) D:=A+C (2) E:=A*C (3) J:=D+E (4) L:=15+J 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 10 页 - - - - - - - - -