编译原理龙书习题5678章.ppt

《编译原理龙书习题5678章.ppt》由会员分享，可在线阅读，更多相关《编译原理龙书习题5678章.ppt（38页珍藏版）》请在三一文库上搜索。

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

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

4、1672021/6/1685.3.3 给出一个SDD对x*(3*x+x*x)这样的表达式求微分。表达式中涉及运算符+和*，变量x和常量。假设不进行任何简化，也就是说，比如3*x将被翻译为3*1+0*x。exp 为原表达式的字符串，s 为求导后的字符串。|为串联接符。2021/6/1692021/6/16102021/6/16115.4.3 下面的SDT计算了一个由0和1组成的串的值。它把输入的符号串当作按照正二进制数来解释。改写这个SDT，使得基础文法不再是左递归的，但仍然可以计算出整个输入串的相同的B.val的值。2021/6/1612非终结符D的综合属性b表示二进制数的位数，val表示对应

5、的十进制数的数值。消除左递归后如下：2021/6/1613第6章 中间代码生成6.1.1 为下面的表达式构造DAG (x+y)-(x+y)*(x-y)+(x+y)*(x-y)2021/6/16146.2.1 将算术表达式 a+-(b+c)翻译成1）抽象语法树2）四元式序列3）三元式序列4）间接三元式序列2021/6/16151）抽象语法树：2021/6/16162）四元式序列：3）三元式序列：4）间接三元式序列：2021/6/16176.4.1 向图6-19的翻译方案中加入对应于下列产生式的规则：1）2）2021/6/16186.4.2 使用图6-20中的增量式翻译方案重复练习6.4.1在增量

6、方式中，在增量方式中，gengen不仅要构造出一个新的三地址指令，还不仅要构造出一个新的三地址指令，还要将它添加到至今为止已生成的指令序列之后。要将它添加到至今为止已生成的指令序列之后。2021/6/16196.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;2021/6/16206.6.1 在图6-30的语法制导定义中添加处理下列控制

7、流构造的规则：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.code2021/6/1621S-for(S1;B;S2)S3S1.next=newlabel()B.true=newlabel()begin=newlabel()B.fale=S.nextS2.next=S1.nextS3.n

8、ext=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)2021/6/16226.7.7 使用图6-37中的翻译方案翻译下列表达式。给出每个子表达式的truelist和falselist。你可以假设第一条被生成的指令的地址是100。1）a=b&(c=d|e=f)2021/6/1623100:if a=b goto 100:if a=b goto 102102101:goto 101:goto _ _ 102:

9、if c=d goto _102:if c=d goto _103:goto 103:goto 104104104:if e=f goto _104:if e=f goto _105:goto _105:goto _2021/6/1624第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;

10、图图7-97-9活动树活动树活动树活动树2021/6/1625第第1 1个个f f(1 1)调调用用即即将将返返回回第第5 5个个f f(1 1)调调用用即即将将返返回回2021/6/16267.2.5 在一个通过引用传递参数的语言中，有一个函数f(x,y)完成下面的计算：x=x+1;y=y+2;return x+y;如果将a赋值为3，然后调用f(a,a)，那么返回值是什么？函数返回值为：12 此时a的值为：62021/6/1627第8章 代码生成8.2.1 假设所有的变量都存放在内存中，为下面的三地址语句生成代码：1）x=1 LD R1,1 ST x,R1 3)x=a+1 LD R1,a A

11、DD R1,R1,1 ST x,R12021/6/16288.2.2 假设a和b是元素为4字节值的数组，为下面的三地址语句序列生成代码。2）三个语句序列 x=ai y=bi z=x*yLD 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,yMUL R5,R5,R6ST z,R52021/6/16298.2.4 假设x,y和z存放在内存位置中，为下面的语句序列生成代码：if x y goto L1 z=0 goto L2L1:z=1 LD R1,x LD R2,y SUB R1,R

12、1,R2 BLTZ R1,L1 LD R3,0 ST z,R3 JMP L2L1:LD R4,1 ST z,R42021/6/16308.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总代价：82021/6/16318.3.3 假设使用栈式分配，且假设a和b都是元素大小为4字节的数组，为下面的三地址语句生成代码。2）三个语句序列 x=ai y=bi z=x*yLD R1,iMUL R1,R1,4ADD R1,

13、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),R52021/6/16328.5.1 为下面的基本块构造DAG。d=b*c e=a+b b=b*c a=e-d1)1)只有只有a a在基本块在基本块的出口处活跃：的出口处活跃：d=b*c d=b*c e=a+b e=a+b a=e-d a=e-d2)a,b,c2)a,b,c在基本块在基本块的出口处活跃：的出口处活跃：e=a+b e=a+b b=b*c b

14、b*c a=e-a=e-b b2021/6/16338.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=t72021/6/16342)假设x和y都在基本块的出口处活跃，利用加法的结合律和交换律来修改这个基本块，使得指令个数最少。把原始的赋值语句进行调整：x=a+c+e+b+d+f y=a+c+e 对应的三地址语句序列：t1=a+ct2=t1+et3=t2+bt4=t3+d

15、t5=t4+fx=t5t6=a+ct7=t6+ey=t7DAGDAG2021/6/1635优化后的三地址语句序列：t1=a+c y=t1+e t3=y+b t4=t3+d x=t4+f优化后的目标代码序列：优化后的目标代码序列：LD R1,a LD R1,a LD R2,c LD R2,c ADD R1,R1,R2 ADD R1,R1,R2 LD R2,e LD R2,e ADD R1,R1,R2 ADD R1,R1,R2 ST y,R1 ST y,R1 LD R2,b LD R2,b ADD R1,R1,R2 ADD R1,R1,R2 LD R2,d LD R2,d ADD R1,R1,R2

16、 ADD R1,R1,R2 LD R2,f LD R2,f ADD R1,R1,R2 ADD R1,R1,R2 ST x,R1 ST x,R12021/6/16368.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=t2LD R1,bLD R2,cMUL R1,R1,R2LD R3,aADD R1,R1,R3ST x,R1LD R1,iMUL R1,R1,4LD R2,a(R1)ADD R2,R2,1ST x,R2假设数组元素宽度为42021/6/1637 结结束束语语若有不当之处，请指正，谢谢！若有不当之处，请指正，谢谢！