龙书第六章参考答案.doc

1、6.1 节的练习为下面的表达式构造 DAG(x+y)-(x+y)*(x-y)+(x+y)*(x-y)解答为下列表达式构造 DAG，且指出他们每个子表达式的值编码。假定 + 是左结合的。1 a+b+(a+b)2 a+b+a+b3 a+a+(a+a+a+(a+a+a+a)解答a+b+(a+b)1ida2idb3+124+33a+b+a+b1ida2idb3+124+315+42a+a+(a+a+a+(a+a+a+a)1ida2+113+214+315+346+256.2 节的练习6.2.1将算数表达式 a+-(b+c) 翻译成4 抽象语法树5 四元式序列6 三元式序列7 间接三元式序列解答抽象语法

2、树四元式序列oparg1arg2result0+bct11minust1t22+at2t3三元式序列oparg1arg20+bc1minus(0)2+a(1)间接三元式序列oparg1arg20+bc1minus(0)2+a(1)instruction0(0)1(1)2(2)参考 间接三元式更详细的讲解6.2.2对下列赋值语句重复练习 6.2.18 a = bi + cj9 ai = b*c - b*d10 x = f(y+1) + 211 x = *p + &y解答a = bi + cj四元式0) = b i t11) = c j t22) + t1 t2 t33) = t3 a 三元式0)

3、 = b i1) = c j2) + (0) (1)3) = a (2) 间接三元式0) = b i1) = c j2) + (0) (1)3) = a (2) 0）1）2）3）ai = b*c - b*d四元式0) * b c t11) * b d t22) - t1 t2 t33) = a i t44) = t3 t4三元式0) * b c1) * b d2) - (0) (1)3) = a i4) = (3) (2)间接三元式0) * b c 1) * b d 2) - (0) (1) 3) = a i 4) = (3) (2)0) 1) 2) 3) 4)x = f(y+1) + 2四元

4、式0) + y 1 t11) param t12) call f 1 t23) + t2 2 t34) = t3 x三元式0) + y 11) param (0)2) call f 13) + (2) 24) = x (3)间接三元式0) + y 11) param (0)2) call f 13) + (2) 24) = x (3)0)1)2)3)4)参考 数组元素的取值和赋值6.2.3 !说明如何对一个三地址代码序列进行转换，使得每个被定值的变量都有唯一的变量名。6.3 节的练习6.3.1确定下列声明序列中各个标识符的类型和相对地址。float x;record float x; floa

5、t y; p;record int tag; float x; float y; q;解答SDTS - top = new Evn(); offset = 0; D D - T id; top.put(id.lexeme, T.type, offset); offset += T.width D1D - T - int T.type = interget; T.width = 4;T - float T.type = float; T.width = 8;T - record Evn.push(top), top = new Evn(); Stack.push(offset), offset

6、= 0; D T.type = record(top); T.width = offset; top = Evn.top(); offset = Stack.pop();标识符类型和相对地址line id type offset Evn 1) x float 0 1 2) x float 0 2 2) y float 8 2 2) p record() 8 1 3) tag int 0 3 3) x float 4 3 3) y float 12 3 3) q record() 24 1 6.3.2 !将图 6-18 对字段名的处理方法扩展到类和单继承的层次结构。12 给出类 Evn 的一个实

7、现。该实现支持符号表链，使得子类可以重定义一个字段名，也可以直接引用某个超类中的字段名。13 给出一个翻译方案，该方案能够为类中的字段分配连续的数据区域，这些字段中包含继承而来的域。继承而来的字段必须保持在对超类进行存储分配时获得的相对地址。6.4 节的练习6.4.1向图 6-19 的翻译方案中加入对应于下列产生式的规则：14 E - E1 * E215 E - +E1解答产生式 语义规则E - E1 * E2 E.addr = new Temp(); E.code = E1.code | E2.code | gen(E.addr = E1.addr * E2.addr); | +E1 E.a

8、ddr = E1.addr; E.code = E1.code; 6.4.2使用图 6-20 的增量式翻译方案重复练习 6.4.1解答产生式 语义规则E - E1 * E2 E.addr = new Temp(); gen(E.addr = E1.addr * E2.addr; | +E1 E.addr = E1.addr; 6.4.3使用图 6-22 的翻译方案来翻译下列赋值语句：16 x = ai + bj17 x = aij + bij18 ! x = abijck解答x = ai + bj语法分析树:三地址代码t_1 = i * awidtht_2 = at_1t_3 = j * bw

9、idtht_4 = bt_3t_5 = t_2 + t_4x = t_5x = aij + bij语法分析树：三地址代码：t_1 = i * ai_widtht_2 = j * aj_widtht_3 = t_1 + t_2t_4 = at_3t_5 = i * bi_widtht_6 = j * bj_widtht_7 = t_5 + t_6t_8 = bt_7t_9 = t_4 + t_8x = t_9! x = abijck6.4.4 !修改图 6-22 的翻译方案，使之适合 Fortran 风格的数据引用，也就是说 n 维数组的引用为 idE1, E2, , En解答仅需修改 L 产生

10、式（同图 6-22 一样，未考虑消除左递归）L - idA L.addr = A.addr; global.array = top.get(id.lexeme); A - E A.array = global.array; A.type = A.array.type.elem; A.addr = new Temp(); gen(A.addr = E.addr * A.type.width; A - A1,E A.array = A1.array; A.type = A1.type.elem; t = new Temp(); A.addr = new Temp(); gen(t = E.addr

11、 * A.type.length); gen(A.addr = A1.addr + t); 注意令 a 表示一个 i*j 的数组，单个元素宽度为 wa.type = array(i, array(j, w)a.type.length = ia.type.elem = array(j, w)6.4.5将公式 6.7 推广到多维数据上，并指出哪些值可以被存放到符号表中并用来计算偏移量。考虑下列情况：19 一个二维数组 A，按行存放。第一维的下标从 l_1 到 h_1，第二维的下标从 l_2 到 h_2。单个数组元素的宽度为 w。20 其他条件和 1 相同，但是采用按列存放方式。21 ！一个 k 维

12、数组 A，按行存放，元素宽度为 w，第 j 维的下标从 l_j 到 h_j。22 ！其他条件和 3 相同，但是采用按列存放方式。解答令 n_i 为第 i 维数组的元素个数，计算公式：n_i = h_i - l_i + 13. Ai_1i_k = base + ( (i_1 - l_1) * n_2 * * n_k + + (i_k-1 - l_k-1) * n_k + (i_k - l_k) ) * w4. Ai_1i_k = base + ( (i_1 - l_1) + (i_2 - l_2) * n_1 + + (i_k - l_k) * n_k-1 * n_k-2 * * n_1 ) *

13、 w6.4.6一个按行存放的整数数组 Ai, j 的下标 i 的范围为 110，下标 j 的范围为 120。每个整数占 4 个字节。假设数组 A 从 0 字节开始存放，请给出下列元素的位置：23 A4, 524 A10, 825 A3, 17解答计算公式：(i-1) * 20 + (j-1) * 426 (3 * 20 + 4) * 4 = 25627 (9 * 20 + 7) * 4 = 74828 (2 * 20 + 16) * 4 = 2246.4.7假定 A 是按列存放的，重复练习 6.4.6解答计算公式：(j-1) * 10 + (j-1) * 429 (4 * 10 + 3) *

14、4 = 17230 (7 * 10 + 9) * 4 = 31631 (16 * 10 + 2) * 4 = 6486.4.8一个按行存放的实数型数组 Ai, j, k 的下标 i 的范围为 14，下标 j 的范围为 04，且下标 k 的范围为 510。每个实数占 8 个字节。假设数组 A 从 0 字节开始存放，计算下列元素的位置：32 A3, 4, 533 A1, 2, 734 A4, 3, 9解答计算公式：(i-1) * 5 * 6 + j * 6 + (k-5) * 835 (3-1) * 5 * 6 + 4 * 6 + (5-5) * 8 = 67236 (1-1) * 5 * 6 +

15、 2 * 6 + (7-5) * 8 = 11237 (4-1) * 5 * 6 + 3 * 6 + (9-5) * 8 = 8966.4.9假定 A 是按列存放的，重复练习 6.4.8解答计算公式：(i-1) + j * 4 + (k-5) * 5 * 4) * 838 (3-1) + 4 * 4 + (5-5) * 5 * 4) * 8 = 14439 (1-1) + 2 * 4 + (7-5) * 5 * 4) * 8 = 38440 (4-1) + 3 * 4 + (9-5) * 5 * 4) * 8 = 7606.5 节的练习6.5.1假定图 6-26 中的函数 widen 可以处理

16、图 6-25a 的层次结构中的所有类型，翻译下列表达式。假定 c 和 d 是字符类型，s 和 t 是短整型， i 和 j 为整型， x 是浮点型。41 x = s + c42 i = s + c43 x = (s + c) * (t + d)解答x = s + ct1 = (int) st2 = (int) ct3 = t1 + t2x = (float) t3i = s + ct1 = (int) st2 = (int) ci = t1 + t2x = (s + c) * (t + d)t1 = (int) st2 = (int) ct3 = t1 + t2t4 = (int) tt5 =

17、(int) dt6 = t4 + t5t7 = t3 + t6x = (float) t76.5.2像 Ada 中那样，我们假设每个表达式必须具有唯一的类型，但是我们根据一个子表达式本身只能推导出一个可能类型的集合。也就是说，将函数 E1 应用于参数 E2（文法产生式为 E - E1(E2)）有如下规则：E.type = t | 对 E2.type 中的某个 s, s - t 在 E1.type 中描述一个可以确定每个字表达式的唯一类型的 SDD。它首先使用属性 type，按照自底向上的方式综合得到一个可能类型的集合。在确定了整个表达式的唯一类型之后，自顶向下地确定属性 unique 的值，整

18、个属性表示各子表达式的类型。6.6 节的练习6.6.1在图 6-36 的语法制导定义中添加处理下列控制流构造的规则：44 一个 repeat 语句：repeat S while B45 ！一个 for 循环语句：for (S1; B; S2) S3解答Production Syntax RuleS - repeat S1 while B S1.next = newlabel() B.true = newlabel() B.false = S.next S.code = label(B.true) | S1.code | label(S1.next) | B.codeS - for (S1; B

19、; S2) S3 S1.next = newlabel() B.true = newlabel() B.false = S.next S2.next = S1.next S3.next = newlabel() S.code = S1.code | lable(S1.next) | B.code | lable(B.true) | S3.code | label(S3.next) | S2.code | gen(goto, S1.next)6.6.2现代计算机试图在同一个时刻执行多条指令，其中包括各种分支指令。因此，当计算机投机性地预先执行某个分支，但实际控制流却进入另一个分支时，付出的代价是

20、很大的。因此我们希望尽可能地减少分支数量。请注意，在图 6-35c 中 while 循环语句的实现中，每个迭代有两个分支：一个是从条件 B 进入到循环体中，另一个分支跳转回 B 的代码。基于尽量减少分支的考虑，我们通常更倾向于将 while(B) S 当作 if(B) repeat S until !(B) 来实现。给出这种翻译方法的代码布局，并修改图 6-36 中 while 循环语句的规则。解答Production Syntax RuleS - if(B) B.true = newlabel() repeat S1 B.false = S.next until !(B) S1.next =

21、 newlabel() S.code = B.code | label(B.true) | S1.code | label(S1.next) | B.code6.6.3！假设 C 中存在一个异或运算。按照图 6-37 的风格写出这个运算符的代码生成规则。解答B1 B2 等价于 !B1 & B2 | B1 & !B2 (运算符优先级 ! & |)Production Syntax RuleB - B1 B2 B1.true = newlabel() B1.false = newlabel() B2.true = B.true B2.false = B1.true b3 = newboolean(

22、) b3.code = B1.code b3.true = newlabel() b3.false = B.false b4 = newboolean() b4.code = B2.code b4.true = B.false b4.false = B.true S.code = B1.code | label(B1.false) | B2.code | label(B1.true) | b3.code | label(b3.true) | b4.code6.6.4使用 6.6.5 节中介绍的避免 goto 语句的翻译方案，翻译下列表达式：46 if (a=b & c=d | e=f) x =

23、 147 if (a=b | c=d | e=f) x = 148 if (a=b | c=d & e=f) x = 1解答if (a=b & c=d | e=f) x = 1 ifFalse a=b goto L3 if c=d goto L2L3: ifFalse e=f goto L1L2: x = 1L1:if (a=b | c=d | e=f) x = 1 if a=b goto L2 if c=d goto L2 ifFalse e=f goto L1L2: x=1L1:if (a=b | c=d & e=f) x = 1 if a=b goto L2 ifFalse c=d go

24、to L1 ifFalse e=f goto L1L2: x=1L1:6.6.5基于图 6-36 和图 6-37 中给出的语法制导定义，给出一个翻译方案。6.6.6使用类似于图 6-39 和图 6-40 中的规则，修改图 6-36 和图 6-37 的语义规则，使之允许控制流穿越。解答仅补充完毕书中未解答部分Production Syntax RuleS - if(B) S1 else S2 B.true = fall B.false = newlabel() S1.next = S.next S2.next = S.next S.code = B.code | S1.code | gen(go

25、to S1.next) | label(B.false) | S2.codeS - while(B) S1 begin = newlabel() B.true = fall B.false = S.next S1.next = begin S.code = label(begin) | B.code | S1.code | gen(goto begin)S - S1 S2 S1.next = fall S2.next = S.next S.code = S1.code | S2.codeB - B1 & B2 B1.true = fall B1.false = if B.false = fal

26、l then newlabel() else B.false B2.true = B.true B2.false = B.false B.code = if B.false = fall then B1.code | B2.code | label(B1.false) else B1.code | B2.code6.6.7！练习 6.6.6 中的语义规则产生了一些不必要的标号。修改图 6-36 中语句的规则，使之只创建必要的标号。你可以使用特殊符号 deferred 来表示还没有创建的一个标号。你的语义规则必须能生成类似于例 6.21 的代码。6.6.8！6.6.5 节中讨论了如何使用穿越代码

27、来尽可能减少生成的中间代码中跳转指令的数据。然而，它并没有充分考虑将一个条件替换为它的补的方法，例如将 if a = b goto L2; goto L1。给出语法制导定义，它在需要时可以利用这种替换方法。6.7 节的练习6.7.1使用图 6-43 中的翻译方案翻译下列表达式。给出每个子表达式的 truelist 和 falselist。你可以假设第一条被生成的指令的地址是 100.49 a=b & (c=d | e=f)50 (a=b | c=d) | e=f51 (a=b & c=d) & e=f解答a=b & (c=d | e=f)6.7.2解答52 E3.false = i153 S2

28、.next = i754 E4.false = i755 S1.next = i356 E2.true = i36.7.3当使用图 6-46 中的翻译方案对图 6-47 进行翻译时，我们为每条语句创建 S.next 列表。一开始是赋值语句 S1, S2, S3，然后逐步处理越来越大的 if 语句，if-else 语句，while 语句和语句块。在图 6-47 中有 5 个这种类型的结构语句： S4: while (E3) S1 S5: if(E4) S2 S6: 包含 S5 和 S3 的语句块 S7: if(E2) S4 else S6 S8: 整个程序对于这些结构语句，我们可以通过一个规则用其他的 Sj.next 列表以及程序中的表达式的列表 Ek.true 和 Ek.false 构造出 Si.next。给出计算下列 next 列表的规则：57 S4.next58 S5.next59 S6.next60 S7.next61 S8.next解答(该题解答不是很肯定)62 S4.next = S3.next63 S5.next = S2.next64 S6.next = S3.next65 S7.next = S3.next66 S8.next = E1.false