编译原理龙书习题5678章.ppt
- 文档编号:10654222
- 上传时间:2023-05-27
- 格式:PPT
- 页数:38
- 大小:859.50KB
编译原理龙书习题5678章.ppt
《编译原理龙书习题5678章.ppt》由会员分享,可在线阅读,更多相关《编译原理龙书习题5678章.ppt(38页珍藏版)》请在冰点文库上搜索。
第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属性定义,5.2.4这个文法生成了含“小数点”的二进制:
设计一个L属性的SDD来计算S.val,即输入串的十进制数值。
比如,串101.11应该被翻译为十进制数5.635。
提示:
使用一个继承属性L.side来指明一个二进制位在小数点的哪一边。
为了求小数部分的值,引入L的综合属性b记录2的L的位数次幂值(2lengthofL)SL1.L2S.val=L1.val+L2.val/L2.b;SLS.val=L.val;LL1BL.val=L1.val*2+B.val;L.b=L1.b*2;LBL.val=B.val;L.b=2;B0B.val=0;B1B.val=1;,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和常量。
假设不进行任何简化,也就是说,比如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)三元式序列4)间接三元式序列,1)抽象语法树:
2)四元式序列:
3)三元式序列:
4)间接三元式序列:
6.4.1向图6-19的翻译方案中加入对应于下列产生式的规则:
1)2),6.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.6.1在图6-30的语法制导定义中添加处理下列控制流构造的规则:
1)一个repeat语句,repeatSwhileB2)一个for循环语句,for(S1;B;S2)S3,S-repeatS1whileBbegin=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.next=S1.nextS3.next=beginS.code=S1.code|label(S1.next)|B.code|label(begin)|S2.code|gen(gotoS1.next)|label(B.true)|S3.code|gen(gotobegin),6.7.7使用图6-37中的翻译方案翻译下列表达式。
给出每个子表达式的truelist和falselist。
你可以假设第一条被生成的指令的地址是100。
1)a=b&(c=d|e=f),100:
ifa=bgoto102101:
goto_102:
ifc=dgoto_103:
goto104104:
ife=fgoto_105:
goto_,第7章运行时环境,7.2.3图7-9中是递归计算Fiabonacci数列的C语言代码。
假设f的活动记录按顺序包含下列元素:
(返回值,参数n,局部变量s,局部变量t)。
通常在活动记录中还会有其他元素。
下面的问题假设初始调用是f(5)。
intf(intn)intt,s;if(n2)return1;s=f(n-1);t=f(n-2);returns+t;,图7-9,活动树,第1个f
(1)调用即将返回,第5个f
(1)调用即将返回,7.2.5在一个通过引用传递参数的语言中,有一个函数f(x,y)完成下面的计算:
x=x+1;y=y+2;returnx+y;如果将a赋值为3,然后调用f(a,a),那么返回值是什么?
函数返回值为:
12此时a的值为:
6,第8章代码生成,8.2.1假设所有的变量都存放在内存中,为下面的三地址语句生成代码:
1)x=1LDR1,1STx,R13)x=a+1LDR1,aADDR1,R1,1STx,R1,8.2.2假设a和b是元素为4字节值的数组,为下面的三地址语句序列生成代码。
2)三个语句序列x=aiy=biz=x*y,LDR1,iMULR1,R1,4LDR2,a(R1)STx,R2LDR3,iMULR3,R3,4LDR4,b(R3)STy,R4LDR5,xLDR6,yMULR5,R5,R6STz,R5,8.2.4假设x,y和z存放在内存位置中,为下面的语句序列生成代码:
ifxygotoL1z=0gotoL2L1:
z=1,LDR1,xLDR2,ySUBR1,R1,R2BLTZR1,L1LDR3,0STz,R3JMPL2L1:
LDR4,1STz,R4,8.2.6确定下列指令序列的代价。
1)LDR0,y2LDR1,z2ADDR0,R0,R11STx,R02总代价:
73)LDR0,c2LDR1,i2MULR1,R2,82STa(R1),R02总代价:
8,8.3.3假设使用栈式分配,且假设a和b都是元素大小为4字节的数组,为下面的三地址语句生成代码。
2)三个语句序列x=aiy=biz=x*y,LDR1,iMULR1,R1,4ADDR1,R1,SPLDR2,a(R1)STx(SP),R2LDR3,iMULR3,R3,4ADDR3,R3,SPLDR4,b(R3)STy(SP),R4LDR5,x(SP)LDR6,y(SP)MULR5,R5,R6STz(SP),R5,8.5.1为下面的基本块构造DAG。
d=b*ce=a+bb=b*ca=e-d,1)只有a在基本块的出口处活跃:
d=b*ce=a+ba=e-d,2)a,b,c在基本块的出口处活跃:
e=a+bb=b*ca=e-b,8.5.8假设一个基本块由下面的C语言赋值语句生成:
x=a+b+c+d+e+f;y=a+c+e;1)给出这个基本块的三地址语句(每个语句只做一次加法)。
t1=a+bt2=t1+ct3=t2+dt4=t3+et5=t4+fx=t5t6=a+ct7=t6+ey=t7,2)假设x和y都在基本块的出口处活跃,利用加法的结合律和交换律来修改这个基本块,使得指令个数最少。
把原始的赋值语句进行调整:
x=a+c+e+b+d+fy=a+c+e对应的三地址语句序列:
t1=a+ct2=t1+et3=t2+bt4=t3+dt5=t4+fx=t5t6=a+ct7=t6+ey=t7,DAG,优化后的三地址语句序列:
t1=a+cy=t1+et3=y+bt4=t3+dx=t4+f,优化后的目标代码序列:
LDR1,aLDR2,cADDR1,R1,R2LDR2,eADDR1,R1,R2STy,R1LDR2,bADDR1,R1,R2LDR2,dADDR1,R1,R2LDR2,fADDR1,R1,R2STx,R1,8.6.1为下面的每个C语言赋值语句生成三地址代码1)x=a+b*c;t1=b*ct2=a+t1x=t23)x=ai+1t1=ait2=t1+1x=t2,LDR1,bLDR2,cMULR1,R1,R2LDR3,aADDR1,R1,R3STx,R1,LDR1,iMULR1,R1,4LDR2,a(R1)ADDR2,R2,1STx,R2,假设数组元素宽度为4,谢谢观看!
2020,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 习题 5678