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

第五章

练习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’具有继承属性inh、side、m和综合属性syn

产生式 1)S->L 2)S->L1.L2 3)L->BL’ 语义规则 S.val=L.syn; L.side=2;L.m=1;L.inh=0 L1.side=2;L2.side=1; L1.inh=0;L1.m=1;L2.m=1/2;L2.inh=0 S.val=L1.syn+L2.syn; L’.m=L.m*L.m;L’.side=L.side L’.inh=L.inh*L.side+B*L.m L.syn=L’.syn L1’.m=L’.m*L’.m;L1’.side=L’.side L1’.inh=L’.inh*L’.side+B*L1’.m L’.syn=L1’.syn L’.syn=L’.inh B.val=0 B.val=1 4)L’->BL1’ 5)L’->ε 6)B->0 7)B->1

练习5.3.1：下面是涉及运算符+和整数或浮点运算分量的表达式文法。区分浮点数的方法是看它有无小数点。

E-〉E+T|T T-〉num.num|num

1）给出一个SDD来确定每个项T和表达式E的类型

2）扩展（1）中得到的SDD，使得它可以把表达式转换成为后缀表达式。使用一个单目运算符intToFloat把一个整数转换为相等的浮点数 答： (1) 产生式 1)E->E1+T 2)E->T 3)T->num 4)T->num.num (2) 产生式 1)E->E1+T 语义规则 If E1.type ==T.type then E.type=E1.type Else begin E.type=float If(E1.type==integer and T.type==float) then E1=intToFloat(E1) Else if(T.type==integer and E1.type==float) then T=intToFloat(T) END E.val = E1.val T.val + E.type=T.type ; E.val=T.val T.type=integer; T.val=num T.type=float ; T.val=num.num 语义规则 If E1.type ==T.type then E.type=E1.type else E.type=float E.type=T.type T.type=integer T.type=float 2)E->T 3)T->num 4)T->num.num

练习5.4.4：为下面的产生式写出一个和例5.10类似的L属性SDD。这里的每个产生式表

示一个常见的C语言中的那样的控制流结构。你可能需要生成一个三地址语句来跳转到某个标号L，此时你可以生成语句goto L 1）S->if (C) S1 else S2 2）S->do S1 while (C)

3）S->’{’ L ‘}’; L -> LS|ε

请注意，列表中的任何语句都可以包含一条从它的内部跳转到下一个语句的跳转指令，因此简单地为各个语句按序生成代码是不够的。 答： 产生式 1) S->if (C) S1 else S2 语义规则 C.false=NewLable();C.true=NewLable() S1.next=S2.next=S.next S.code=C.code || Lable(C.true) || S1.code || gen(‘goto’ S.next) || Lable(C.false)|| S2.code Begin=NewLable() C.false=NewLable(); C.true=NewLable() S1.next=begin S.code=Lable(begin)||S1.code || Lable(C.true) || gen(‘goto’begin) S.syn=L.syn; S.inh=L1.syn; L.syn=S.syn L.inh=L.syn 2) S->do S1 while (C) 3) S->’{’ L ‘}’; L -> L1S L->ε

第六章

练习6.1.1：为下面的表达式构造DAG （（x+y）-（（x+y）*（x-y）））+（（x+y）*（x-y）） 答：DAG如下 + - * + - X Y 练习6.2.1：将算术表达式a+ - (b+c)翻译成 1） 抽象语法树 2） 四元式序列 3） 三元式序列

4） 间接三元式序列 答：(1)抽象语法树 + a b (2) 四元式序列

t1=b+c

t2=minus t1 t3=a+t2

0 1 2 (3)三元式序列 0 1 2 op + minus + op + minus + minus + c Arg1 b T1 a Arg1 b (0) a Arg2 c T2 Arg2 c (1) result T1 T2 T3 (4)间接三元式序列

instruction

10 11 12 (0) (1) (2)

0 1 2 op + minus + Arg1 b (0) a Arg2 c (1)

练习6.4.3：使用图6-22中的翻译方案，来翻译下列赋值语句

x=a[i][j]+b[i][j]

答：

假定数组a,b均为2*3规模的整型数组，且一个整数的宽度为4 x=a[i][j]+b[i][j]的注释语法分析树如下

S X = E.addr=t9 E.addr=t4 L.addr=t3 L.array=a L.type=integer L.addr=t1 L.type=array(3,integer) L.array=a a.type =array(2,array(3,integer)) + E.addr=t8 L.addr=t7 L.array=b L.type=integer L.addr=t5 [ E.addr= j ] L.array=b L.type=array(3,integer) j [ E.addr=j ] j [ E.addr=i ] i b.type =array(2,array(3,integer)) [ E.addr= i ] i x=a[i][j]+b[i][j]被翻译成的三地址代码如下如下 T1=i*12 T5=i*12 T2=j*4 t6=j*4 T3=t1+t1 t7=t5+t6 T4=a[t3] t8=b[t7] T9=t4+t8 X=t9

练习6.6.4：使用图6.6.5节中介绍的避免goto语句的翻译方案，来翻译下列表达式：

If （a==b && c==d || e==f） x==1;

答： If e==f goto L2 ifFalse a==b goto L1 ifFalse c==d goto L1 L2: x==1 L1: 练习6.7.1：使用图6-43中的翻译方案翻译下列表达式。给出每个子表达式的truelist

和falselist。你可以假设第一条被生成的指令地址是100. a==b && (c==d || e==f)

答：

构造表达式的注释语法分析树如下 B.t={102,104} B.f={101,105} && M.i={102} B.t={100} B.f={101} ε ( & a == b || B.t={102} B.f={103} B.t={102,104} B.f={105} B.t={102,104} ) B.f={105} M.i={104} ε& B.t={104} B.f={105} 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的值，该值为102 3) 按B->E1 rel E2 将c==d 归约为B时语义动作相应的指令如下

102: if c==d goto – 103: goto – 4) 产生式 B->B1 || M B2中的标记非终结符号M记录了nextinstr的值，该值为104 5) 按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在上图中已标出

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库编译原理5、6章作业答案在线全文阅读。