编译原理5、6章作业答案

1、第五章练习5.1.1：对于图5-1中的SDD，给出下列表达式对应的注释语法分析树：1）（3+4）*（5+6）n练习5.2.4：这个文法生成了含“小数点”的二进制数：S-L.L|L L-LB|B B-0|1设计一个L属性的SDD来计算S.val，即输入串的十进制数值。比如，串101.101应该被翻译为十进制的5.625。提示：使用一个继承属性L.side来指明一个二进制位在小数点的哪一边。答：元文法消除左递归后可得到文法：S-L.L|L L-BL L-BL| B-0|1使用继承属性L.side指明一个二进制位数在小数点的哪一边,2表示左边，1表示右边使用继承属性m记录B的幂次非终结符号L和L具有

2、继承属性inh、side、m和综合属性syn产生式语义规则1)S-LS.val=L.syn; L.side=2;L.m=1;L.inh=02)S-L1.L2L1.side=2;L2.side=1; L1.inh=0;L1.m=1;L2.m=1/2;L2.inh=0S.val=L1.syn+L2.syn; 3)L-BLL.m=L.m*L.m;L.side=L.sideL.inh=L.inh*L.side+B*L.mL.syn=L.syn4)L-BL1L1.m=L.m*L.m;L1.side=L.sideL1.inh=L.inh*L.side+B*L1.mL.syn=L1.syn5)L-L.syn

3、=L.inh6)B-0B.val=07)B-1B.val=1练习5.3.1：下面是涉及运算符+和整数或浮点运算分量的表达式文法。区分浮点数的方法是看它有无小数点。E-E+T|T T-num.num|num1）给出一个SDD来确定每个项T和表达式E的类型2）扩展（1）中得到的SDD，使得它可以把表达式转换成为后缀表达式。使用一个单目运算符intToFloat把一个整数转换为相等的浮点数答：(1)产生式语义规则1)E-E1+TIf E1.type =T.type then E.type=E1.typeelse E.type=float2)E-TE.type=T.type3)T-numT.type=

4、integer4)T-num.numT.type=float(2)产生式语义规则1)E-E1+TIf E1.type =T.type then E.type=E1.typeElse beginE.type=floatIf(E1.type=integer and T.type=float) then E1=intToFloat(E1)Else if(T.type=integer and E1.type=float) then T=intToFloat(T)ENDE.val = E1.val T.val +2)E-TE.type=T.type ; E.val=T.val3)T-numT.type=

5、integer; T.val=num4)T-num.numT.type=float ; T.val=num.num练习5.4.4：为下面的产生式写出一个和例5.10类似的L属性SDD。这里的每个产生式表示一个常见的C语言中的那样的控制流结构。你可能需要生成一个三地址语句来跳转到某个标号L，此时你可以生成语句goto L1）S-if (C) S1 else S22）S-do S1 while (C)3）S- L ; L - LS|请注意，列表中的任何语句都可以包含一条从它的内部跳转到下一个语句的跳转指令，因此简单地为各个语句按序生成代码是不够的。答：产生式语义规则1) S-if (C) S1 e

6、lse S2C.false=NewLable();C.true=NewLable()S1.next=S2.next=S.nextS.code=C.code | Lable(C.true) | S1.code | gen(goto S.next) | Lable(C.false)| S2.code2) S-do S1 while (C)Begin=NewLable()C.false=NewLable(); C.true=NewLable()S1.next=beginS.code=Lable(begin)|S1.code | Lable(C.true) | gen(gotobegin)3) S-

7、L ;L - L1SL-S.syn=L.syn;S.inh=L1.syn; L.syn=S.synL.inh=L.syn第六章练习6.1.1：为下面的表达式构造DAG（x+y）-（x+y）*（x-y）+（x+y）*（x-y）答：DAG如下*+-+YX练习6.2.1：将算术表达式a+ - (b+c)翻译成1） 抽象语法树2） 四元式序列3） 三元式序列4） 间接三元式序列答：(1)抽象语法树cb+minusa(2) 四元式序列t1=b+ct2=minus t1t3=a+t2opArg1Arg2result0+bcT11minusT1T22+aT2T3(3)三元式序列opArg1Arg20+bc1

8、minus(0)2+a(1)(4)间接三元式序列 10(0)11(1)12(2)opArg1Arg20+bc1minus(0)2+a(1) instruction 练习6.4.3：使用图6-22中的翻译方案，来翻译下列赋值语句x=aij+bij 答：假定数组a,b均为2*3规模的整型数组，且一个整数的宽度为4x=aij+bij的注释语法分析树如下SXE.addr=t8E.addr=t4E.addr=t9=+L.addr=t7L.array=bL.type=integerL.addr=t3L.array=aL.type=integerL.addr=t5L.array=bL.type=array(

9、3,integer)L.addr=t1L.type=array(3,integer)L.array=a E.addr= j E.addr=j j a.type=array(2,array(3,integer) E.addr=i b.type=array(2,array(3,integer) E.addr= i i j i x=aij+bij被翻译成的三地址代码如下如下T1=i*12T5=i*12T2=j*4t6=j*4T3=t1+t1t7=t5+t6T4=at3t8=bt7T9=t4+t8X=t9练习6.6.4：使用图6.6.5节中介绍的避免goto语句的翻译方案，来翻译下列表达式：If （a

10、=b & c=d | e=f） x=1;答：If e=f goto L2ifFalse a=b goto L1ifFalse c=d goto L1L2: x=1L1:练习6.7.1：使用图6-43中的翻译方案翻译下列表达式。给出每个子表达式的truelist和falselist。你可以假设第一条被生成的指令地址是100.a=b & (c=d | e=f)答：构造表达式的注释语法分析树如下 B.t=102,104B.f=101,105M.i=102)(B.t=102,104B.f=105B.t=102,104B.f=105&B.t=100B.f=101a = bM.i=104|B.t=102B.f=103B.t=104B.f=105&c = de = f各产生式进行归约时产生的语义动作的相应指令如下1) 按B-E1 rel E2 将a=b 归约为B时语义动作相应的指令如下100: if a=b goto 101: goto 2) 产生式 B-B1 & M B2中的标记非终结符号M记录了nextinstr的值，该值为1023) 按B-E1 rel E2 将c=d 归约为B时语义动作相应的指令如下102: if c=d goto 103: goto 4) 产生式 B-B1 | M B2中的标记非终结符号M记录了nextinst