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

资源描述

《编译原理(龙书)习题(5,6,7,8)章.ppt》由会员分享，可在线阅读，更多相关《编译原理(龙书)习题(5,6,7,8)章.ppt（37页珍藏版）》请在三一办公上搜索。

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+C.i不满足S属性定义，不满足L

2、属性定义,5.2.4 这个文法生成了含“小数点”的二进制：设计一个L属性的SDD来计算S.val，即输入串的十进制数值。比如，串101.11应该被翻译为十进制数5.635。提示：使用一个继承属性L.side来指明一个二进制位在小数点的哪一边。,为了求小数部分的值，引入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.b*2;L B L.val=B.val;L.b=2;B 0 B.val=0;B 1 B.val=1

3、;,5.3.1 下面是涉及运算符+和整数或浮点运算分量的表达式的文法。区分浮点数的方法是看它有无小数点。1）给出一个SDD来确定每个项T和表达式E的类型。2）扩展(1)中得到的SDD，使得它可以把表达式转换成为后缀表达式。使用一个单目运算符intToFloat把一个整数转换为相等的浮点数。,（）设code 为综合属性，代表各非终结符的代码属性 type为综合属性，代表各非终结符的类型属性 inttoreal把整型值转换为相等的实型值 vtochar将数值转换为字符串,5.3.3 给出一个SDD对x*(3*x+x*x)这样的表达式求微分。表达式中涉及运算符+和*，变量x和常量。假设不进行任何简化

4、，也就是说，比如3*x将被翻译为3*1+0*x。exp 为原表达式的字符串，s 为求导后的字符串。|为串联接符。,5.4.3 下面的SDT计算了一个由0和1组成的串的值。它把输入的符号串当作按照正二进制数来解释。改写这个SDT，使得基础文法不再是左递归的，但仍然可以计算出整个输入串的相同的B.val的值。,非终结符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）

5、三元式序列4）间接三元式序列,1）抽象语法树：,2）四元式序列：3）三元式序列：4）间接三元式序列：,6.4.1 向图6-19的翻译方案中加入对应于下列产生式的规则：1）2）,在增量方式中，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.6.1

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

8、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 在一个通过引用传递参数的语言中，有一个函数f(x,y)完成下面的计算：x=x+1;y=y+2;return x+y

9、;如果将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,R1,8.2.2 假设a和b是元素为4字节值的数组，为下面的三地址语句序列生成代码。2）三个语句序列 x=ai y=bi z=x*y,LD R1,iMUL R1,R1,4LD R2,a(R1)ST x,R2LD R3,iMUL R3,R3,4LD R4,b(R3)ST y,R4LD R5,xLD R6,

10、yMUL R5,R5,R6ST z,R5,8.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,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总代价：8,8.3.3

11、假设使用栈式分配，且假设a和b都是元素大小为4字节的数组，为下面的三地址语句生成代码。2）三个语句序列 x=ai y=bi z=x*y,LD R1,iMUL R1,R1,4ADD R1,R1,SPLD R2,a(R1)ST x(SP),R2LD R3,iMUL 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),R5,8.5.1 为下面的基本块构造DAG。d=b*c e=a+b b=b*c a=e-d,1)只有a在基本块的出口处活跃：d=b*c e=a+b a=e-d,2)a,

12、b,c在基本块的出口处活跃：e=a+b b=b*c a=e-b,8.5.8 假设一个基本块由下面的C语言赋值语句生成：x=a+b+c+d+e+f;y=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=t7,2)假设x和y都在基本块的出口处活跃，利用加法的结合律和交换律来修改这个基本块，使得指令个数最少。把原始的赋值语句进行调整：x=a+c+e+b+d+f y=a+c+e 对应的三地址语句序列：,t1=a+ct2=t1+et3=t2+bt4=t3+dt5=t

13、4+fx=t5t6=a+ct7=t6+ey=t7,DAG,优化后的三地址语句序列：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,R1,8.6.1 为下面的每个C语言赋值语句生成三地址代码1）x=a+b*c;t1=b*c t2=a+t1 x=t23)x=ai+1 t1=ai t2=t1+1 x=t2,LD R1,bLD R2,cMUL R1,R1,R2LD R3,aADD R1,R1,R3ST x,R1,LD R1,iMUL R1,R1,4LD R2,a(R1)ADD R2,R2,1ST x,R2,假设数组元素宽度为4,

展开阅读全文