编译原理(龙书)习题(5,6,7,8)章

1、第5章 语法制导的翻译5.2.3 假设我们有一个产生式 。A，B，C，D这四个非终结符号都有两个属性：s是一个综合属性，而i是一个继承属性。对于下面的每组规则，指出(i)这些规则是否满足S属性定义的要求。(ii)这些规则是否满足L属性定义的要求。(iii)是否存在和这些规则一致的求值过程？1）A.s = B.i + C.s不满足S属性定义，满足L属性定义2）A.s = B.i + C.s 和 D.i = A.i + B.s不满足S属性定义，满足L属性定义 3）A.s = B.s + D.s满足S属性定义，满足L属性定义4）A.s=D.i，B.i=A.s+C.s，C.i=B.s和D.i=B.i+

2、C.i不满足S属性定义，不满足L属性定义 BCDA5.2.4 这个文法生成了含“小数点”的二进制： 设计一个L属性的SDD来计算S.val，即输入串的十进制数值。比如，串101.11应该被翻译为十进制数5.635。提示：使用一个继承属性L.side来指明一个二进制位在小数点的哪一边。1 |0|.BBLBLLLLS为了求小数部分的值，引入L的综合属性b记录2的L的位数次幂值(2 length of L)S L1.L2 S.val = L1.val +L2.val / L2.b;S L S.val = L.val;L L1 B L.val = L1.val *2 + B.val; L.b = L1

3、.b*2;L B L.val = B.val; L.b = 2;B 0 B.val = 0;B 1 B.val = 1;5.3.1 下面是涉及运算符+和整数或浮点运算分量的表达式的文法。区分浮点数的方法是看它有无小数点。 1）给出一个SDD来确定每个项T和表达式E的类型。2）扩展(1)中得到的SDD，使得它可以把表达式转换成为后缀表达式。使用一个单目运算符intToFloat把一个整数转换为相等的浮点数。numnumnumTTTEE|.|（）设code 为综合属性，代表各非终结符的代码属性 type为综合属性，代表各非终结符的类型属性 inttoreal把整型值转换为相等的实型值 vtocha

4、r将数值转换为字符串 5.3.3 给出一个SDD对x*(3*x+x*x)这样的表达式求微分。表达式中涉及运算符+和*，变量x和常量。假设不进行任何简化，也就是说，比如3*x将被翻译为3*1+0*x。 exp 为原表达式的字符串，s 为求导后的字符串。 | 为串联接符。5.4.3 下面的SDT计算了一个由0和1组成的串的值。它把输入的符号串当作按照正二进制数来解释。 改写这个SDT，使得基础文法不再是左递归的，但仍然可以计算出整个输入串的相同的B.val的值。1. 1 | 1.2. 1 | .2. 01111valBvalBvalBBvalBvalBBB0. ; 0. | 1. ;.21. 1

5、| 1. ;. 0.21. 111.1111.1bDvalDbDbDvalDvalDDbDbDvalDvalDDDvalDvalBDBbDbD非终结符D的综合属性b表示二进制数的位数，val表示对应的十进制数的数值。消除左递归后如下：第6章 中间代码生成6.1.1 为下面的表达式构造DAG (x+y)-(x+y)*(x-y)+(x+y)*(x-y)6.2.1 将算术表达式 a+-(b+c) 翻译成1）抽象语法树2）四元式序列3）三元式序列4）间接三元式序列1）抽象语法树：2）四元式序列：3）三元式序列：4）间接三元式序列：6.4.1 向图6-19的翻译方案中加入对应于下列产生式的规则：1）2）

6、)(*121单目加EEEEE6.4.2 使用图6-20中的增量式翻译方案重复练习6.4.1在增量方式中，gen不仅要构造出一个新的三地址指令，还要将它添加到至今为止已生成的指令序列之后。6.4.3 使用使用图6-22所示的翻译方案来翻译下列赋值语句：2） x = aij + bij假设w1为数组a的第一维的宽度，w2为数组b的第一维的宽度，整数的宽度为w。 t1 = i * w1; t6 = j * w; t2 = j * w; t7 = t5 + t6; t3 = t1 + t2; t8 = bt7; t4 = at3; t9 = t4 + t8; t5 = i * w2; x = t9;6

7、.6.1 在图6-30的语法制导定义中添加处理下列控制流构造的规则：1）一个repeat语句，repeat S while B2）一个for循环语句，for (S1 ; B ; S2) S3S-repeat S1 while Bbegin=newlabel()S1.next=newlabel()B.true=beginB.false = S.nextS.code=label(begin)| S1.code| label(S1.next)| B.codeS-for ( S1; B; S2 ) S3S1.next=newlabel()B.true=newlabel()begin=newlabel(

8、)B.fale=S.nextS2.next =S1.nextS3.next=beginS.code=S1.code|label(S1.next)| B.code|label(begin)| S2.code| gen(goto S1.next)| label(B.true)|S3.code| gen(goto begin)6.7.7 使用图6-37中的翻译方案翻译下列表达式。给出每个子表达式的truelist和falselist。你可以假设第一条被生成的指令的地址是100。1）a=b&(c=d|e=f)100: if a=b goto 102101: goto _ 102: if c=d

9、 goto _103: goto 104104: if e=f goto _105: goto _第7章 运行时环境7.2.3 图7-9中是递归计算Fiabonacci数列的C语言代码。假设f的活动记录按顺序包含下列元素：（返回值，参数n，局部变量s，局部变量t）。通常在活动记录中还会有其他元素。下面的问题假设初始调用是f(5)。int f(int n) int t,s; if (n2) return 1; s = f(n-1); t = f(n-2); return s+t;图7-9活动树活动树第1个f(1)调用即将返回第5个f(1)调用即将返回7.2.5 在一个通过引用传递参数的语言中，有

10、一个函数f(x,y)完成下面的计算： x = x + 1; y = y + 2; return x + y; 如果将a赋值为3，然后调用f(a,a)，那么返回值是什么？ 函数返回值为：12 此时a的值为：6第8章 代码生成8.2.1 假设所有的变量都存放在内存中，为下面的三地址语句生成代码： 1） x = 1 LD R1 , 1 ST x , R1 3) x = a + 1 LD R1 , a ADD R1 , R1 , 1 ST x , R18.2.2 假设a和b是元素为4字节值的数组，为下面的三地址语句序列生成代码。2）三个语句序列 x = ai y = bi z = x * yLD R1

11、 , iMUL R1 , R1 , 4LD R2 , a(R1)ST x , R2LD R3 , iMUL R3 , R3 ,4LD R4 , b(R3)ST y , R4LD R5 , xLD R6 , yMUL R5 , R5 , R6ST z , R58.2.4 假设x,y和z存放在内存位置中，为下面的语句序列生成代码： if x y goto L1 z = 0 goto L2L1:z = 1 LD R1 , x LD R2 , y SUB R1 , R1 , R2 BLTZ R1 , L1 LD R3 , 0 ST z , R3 JMP L2L1:LD R4 , 1 ST z , R4

12、8.2.6 确定下列指令序列的代价。1） LD R0 , y 2 LD R1 , z 2 ADD R0 , R0 , R1 1 ST x , R0 2 总代价：73） LD R0 , c 2 LD R1 , i 2 MUL R1 , R2 , 8 2 ST a(R1) , R0 2总代价：88.3.3 假设使用栈式分配，且假设a和b都是元素大小为4字节的数组，为下面的三地址语句生成代码。2）三个语句序列 x = ai y = bi z = x*yLD R1 , iMUL R1 , R1 , 4ADD R1 , R1 , SPLD R2 , a(R1)ST x(SP) , R2LD R3 , i

13、MUL R3 , R3 , 4ADD R3 , R3 , SPLD R4 , b(R3)ST y(SP) , R4LD R5 , x(SP)LD R6 , y(SP)MUL R5 , R5 , R6ST z(SP) ,R58.5.1 为下面的基本块构造DAG。 d = b*c e = a+b b = b*c a = e-d1)只有a在基本块的出口处活跃： d = b * c e = a + b a = e - d2)a,b,c在基本块的出口处活跃： e = a + b b = b * c a = e - b8.5.8 假设一个基本块由下面的C语言赋值语句生成：x = a+b+c+d+e+f;y

14、 = a+c+e;1)给出这个基本块的三地址语句（每个语句只做一次加法）。 t1 = a + b t2 = t1 + c t3 = t2 + d t4 = t3 + e t5 = t4 + f x = t5 t6 = a + c t7 = t6 + e y = t72)假设x和y都在基本块的出口处活跃，利用加法的结合律和交换律来修改这个基本块，使得指令个数最少。 把原始的赋值语句进行调整： x = a+c+e+b+d+f y = a+c+e 对应的三地址语句序列：t1 = a + ct2 = t1 + et3 = t2 + bt4 = t3 + dt5 = t4 + fx = t5t6 = a + ct7 = t6 + ey = t7DAG优化后的三地址语句序列： t1 = a + c y = t1 + e t3 = y + b t4 = t3 + d x = t4 + f优化后的目标代码序列： LD R1 , a LD R2 , c ADD R1 , R1 , R2 LD R2 , e ADD R1 , R1 , R2 ST y , R1 LD R2 , b ADD R1 , R1 , R2 LD R2 , d ADD R1 , R1 , R2 LD R2 , f ADD R1 , R1 , R2 ST x , R18.6.1 为下面的每个C语言赋