《编译原理 龙书 第二版 第5、6章》由会员分享，可在线阅读，更多相关《编译原理 龙书 第二版 第5、6章（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 表示右边使用继
2、承属性 m 记录 B 的幂次非终结符号 L 和 L具有继承属性 inh、side、m 和综合属性 syn产生式 语义规则1)S-L S.val=L.syn; L.side=2;L.m=1;L.inh=02)S-L1.L2 L1.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-BL L.m=L.m*L.m;L.side=L.sideL.inh=L.inh*L.side+B*L.mL.syn=L.syn4)L-BL1 L1.m=L.m*L.m;L1.side=L.sideL1.inh=L.inh
3、*L.side+B*L1.mL.syn=L1.syn5)L- L.syn=L.inh6)B-0 B.val=07)B-1 B.val=1练习 5.3.1：下面是涉及运算符+和整数或浮点运算分量的表达式文法。区分浮点数的方法是看它有无小数点。E-E+T|T T-num.num|num1）给出一个 SDD 来确定每个项 T 和表达式 E 的类型2）扩展（1）中得到的 SDD，使得它可以把表达式转换成为后缀表达式。使用一个单目运算符 intToFloat 把一个整数转换为相等的浮点数答：(1)产生式 语义规则1)E-E1+T If E1.type =T.type then E.type=E1.typ
4、eelse E.type=float2)E-T E.type=T.type3)T-num T.type=integer4)T-num.num T.type=float(2)产生式 语义规则1)E-E1+T If 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.va
5、l T.val +2)E-T E.type=T.type ; E.val=T.val3)T-num T.type=integer; T.val=num4)T-num.num T.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|请注意，列表中的任何语句都可以包
6、含一条从它的内部跳转到下一个语句的跳转指令，因此简单地为各个语句按序生成代码是不够的。答：产生式 语义规则1) S-if (C) S1 else S2 C.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=beg
7、inS.code=Lable(begin)|S1.code| Lable(C.true) | gen(gotobegin)3) S- 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 如下练习 6.2.1：将算术表达式 a+ - (b+c)翻译成X Y+*-+1） 抽象语法树2） 四元式序列3） 三元式序列4） 间接三元式序列答：(1)抽象语法树(2) 四元式序列t1=b+ct2=minus t
8、1t3=a+t2op Arg1 Arg2 result0 + b c T11 minus T1 T22 + a T2 T3(3)三元式序列op Arg1 Arg20 + b c1 minus (0)2 + a (1)(4)间接三元式序列instruction练习 6.4.3：使用图 6-22 中的翻译方案，来翻译下列赋值语句x=aij+bij 答：假定数组 a,b 均为 2*3 规模的整型数组，且一个整数的宽度为 4x=aij+bij的注释语法分析树如下10 (0)11 (1)12 (2)op Arg1 Arg20 + b c1 minus (0)2 + a (1)+a minus+b cx=
9、aij+bij被翻译成的三地址代码如下如下练习 6.6.4：使用图 6.6.5 节中介绍的避免 goto 语句的翻译方案，来翻译下列表达式：If （a=b & c=d | e=f） x=1;答：练习 6.7.1：使用图 6-43 中的翻译方案翻译下列表达式。给出每个子表达式的 truelistE.addr=t9E.addr=t4 + E.addr=t8L.addr=t3L.array=aL.type=integerL.addr=t7L.array=bL.type=integerL.addr=t1L.type=array(3,integer)L.array=a E.addr=j E.addr=i
10、 a.type=array(2,array(3,integer)L.addr=t5L.array=bL.type=array(3,integer)b.type=array(2,array(3,integer) E.addr= i j i i E.addr= j j SX =T1=i*12 T5=i*12T2=j*4 t6=j*4T3=t1+t1 t7=t5+t6T4=at3 t8=bt7T9=t4+t8X=t9If e=f goto L2ifFalse a=b goto L1ifFalse c=d goto L1L2: x=1L1:和 falselist。你可以假设第一条被生成的指令地址是 1
11、00.a=b & (c=d | e=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 记录了 nextinstr 的值，该
12、值为 1045) 按 B-E1 rel E2 将 e=f 归约为 B 时语义动作相应的指令如下104: if e=f goto 105: goto 6) 按照产生式 B-B1 | M B2 进行归约7) 按照产生式 B-（B1 ）进行归约8) 按照产生式 B-B1 & M B2 进行归约9) 各子表达式的 truelist 和 falselist 在上图中已标出B.t=102,104B.f=101,105B.t=100B.f=101& M.i=102 B.t=102,104B.f=105a = bB.t=102,104B.f=105( )B.t=102B.f=103B.t=104B.f=105| M.i=104c = d e = f&
