5编译原理,陈意云 ,课后答案5

编译原理,陈意云 ,课后答案

编译原理习题课(5) 编译原理习题课(5)栾 俊 luanj@http://www.77cn.com.cn 3/28/2011

编译原理,陈意云 ,课后答案

7.1 把算术表达式 –(a+b)*(c+d)+(a+b-c) 翻译成： (a) 语法树 (b) 有向无环图 (c) 后缀表示 (d) 三地址代码

2011-3-28

luanj@http://www.77cn.com.cn

编译原理,陈意云 ,课后答案

7.1 (续) (续 (a) 语法树+ + + -

(b) 有向无环图+ +

* + + a

c b +

*

+

a

b c

d

a

b

c

d3

2011-3-28

luanj@http://www.77cn.com.cn

编译原理,陈意云 ,课后答案

7.1 (续) (续 (c) 后缀表示 ab+cd+*-ab+c++ (d) 三地址代码 t1 := a + b t2 := c + d t3 := t1 * t2 t4 := -t3 t5 := t1 + c t6 := t4 + t52011-3-28 luanj@http://www.77cn.com.cn 4

编译原理,陈意云 ,课后答案

7.2 把C程序 main(){ int i; int a[10]; while(i <= 10) a[i] = 0; } 的可执行语句翻译成： (a) 语法树 (b) 后缀表示 (c) 三地址代码2011-3-28 luanj@http://www.77cn.com.cn 5

编译原理,陈意云 ,课后答案

7.2 (续) (续 (a) (b) 语法树 后缀表示<= while

= 10 array a i

i 10 <= a i array 0 = whilei 0

2011-3-28

luanj@http://www.77cn.com.cn

编译原理,陈意云 ,课后答案

7.2 (续) (续 (c) 三地址代码 1: if i <= 10 goto 3 2: goto 5 3: a[i] := 0; 4: goto 1 5: return 0

2011-3-28

luanj@http://www.77cn.com.cn

编译原理,陈意云 ,课后答案

7.4 修改图7.4中计算声明的类型和相对地址的翻译方案，允 许名字表而不是单个名字出现在形式为D->id: T的声明中。P -> DS D -> D;D D -> id:T T -> integer T -> real T -> array[num]of T1 T -> ↑T1 { offset = 0; } { enter(http://www.77cn.com.cn, T.type, offset); offset += T.width; } { T.type = integer; T.width = 4; } { T.type = real; T.width = 8; } { T.type = array(num.val, T1.type); T.width = num.val * T1.width; } { T.type = pointer(T1.type); T.width = 4; }

2011-3-28

luanj@http://www.77cn.com.cn

编译原理,陈意云 ,课后答案

7.4 (续) (续 D -> ID_LIST:T ID_LIST -> ID_LIST,ID_LIST|id D -> { Init(idtable) } ID_LIST:T { for each name in idtable do enter(name, T.type, offset); offset := offset + T.width; end; } ID_LIST -> { Init(idtable1); Init(idtable2) } ID_LIST1,ID_LIST2 { merge(idtable1, idtable2, idtable) } ID_LIST -> id { add(idtable, http://www.77cn.com.cn); }

2011-3-28

luanj@http://www.77cn.com.cn

编译原理,陈意云 ,课后答案

7.5 算符θ作用于表达式e1,e2,...,ek的前缀形式 是θp1p2...pk,其中pi是ei的前缀形式。 (a) 写出a*-(b+c)的前缀形式。 (c) 给出把表达式翻成前缀形式的语法制导 定义。

2011-3-28

luanj@http://www.77cn.com.cn

编译原理,陈意云 ,课后答案

7.5 (续) (续 (a) *a-+bc (c) 表达式翻成前缀形式的语法制导定义E -> E+T | T T -> T*F | F F -> -F | (E) | id L -> En { printf(E.string); } E -> E1 + T { E.string = “+” + E1.string + T.string; } E -> T { E.string = T.string; } T -> T1*F { T.string = “*” + T1.string + F.string; } T -> F { T.string = F.string; } F -> -F1 { F.string = “-” + F1.string; } F -> (E) { F.string = E.string; } F -> id { F.string = id.value; }2011-3-28 luanj@http://www.77cn.com.cn 11

编译原理,陈意云 ,课后答案

7.7 修改图7.11的语法制导定义，为栈机器产生代码。E → E1 or E2 E → not E1 E → ( E1 ) E → id1 relop id2 E → E1 and E2 { E.place := newtemp; emit (E.place, ‘:=’, E1.place, ‘or’, E2.place) } { E.place := newtemp;

emit (E.place, ‘:=’, E1.place, ‘and’, E2.place) } { E.place := E1.place } { E.place := newtemp; emit (E.place, ‘:=’, ‘not’, E1.place) } { E.place := newtemp; emit (‘if’, id1.place, relop.op, id2.place,‘goto’, nextstat+3 ); emit (E.place, ‘:=’, ‘0’ ); emit (‘goto’, nextstat + 2 ); emit (E.place, ‘:=’, ‘1’ ) } { E.place := newtemp; emit (E.place, ‘:=’, ‘1’ ) } { E.place := newtemp; emit (E.place, ‘:=’, ‘0’ ) }

E → true E → false

2011-3-28

luanj@http://www.77cn.com.cn

编译原理,陈意云 ,课后答案

7.7 (续) (续 E → E1 or E2 E → E1 and E2 E → not E1 E → ( E1 ) E → id1 relop id2 { emit (‘or’) } { emit (‘and’) } { emit (‘not’) } {} { emit(‘push ‘ || http://www.77cn.com.cn); emit(‘push ’ || http://www.77cn.com.cn); emit (‘relop ’ || relop.op) } { emit ( ‘1’ ) } { emit ( ‘0’ ) }

E → true E → false 指令解释 指令解释: or: 将栈顶和次栈顶值取出 进行或操作 将结果压栈 将栈顶和次栈顶值取出, 进行或操作,将结果压栈 and: 将栈顶和次栈顶值取出 进行与操作 将结果压栈 将栈顶和次栈顶值取出, 进行与操作,将结果压栈 not: 将栈顶值取出 进行非操作 将结果压栈 将栈顶值取出, 进行非操作,将结果压栈 push name: 将name的值压栈 的值压栈 relop op:将栈顶和次栈顶值取出 判断他们的 关系 将结果压栈 将栈顶和次栈顶值取出, 关系,将结果压栈 将栈顶和次栈顶值取出 判断他们的op关系2011-3-28 luanj@http://www.77cn.com.cn 13

编译原理,陈意云 ,课后答案

7.8 表7.4的语法制导定义把E-> id1< id2翻译成 一对语句 if id1<id2 goto ... goto ... 可以用一个语句 if id1>=id2 goto... 来代替，当E是真时执行后继代码。修改表 7.4的语法制导定义，使之产生这种性质的 代码。2011-3-28 luanj@http://www.77cn.com.cn 14

编译原理,陈意云 ,课后答案

7.6 假转方式 产生式E → E1 or E2

语义规则E1.true := E.true; E1.false := newlabel; E2.true := E.true; E2.false := E.false; E.code := E1.code [增加 || gen(‘goto’, E1.true)] || 增加: 增加 gen(E1.false, ‘:’) || E2.code E1.true := newlabel; E1.false := E.false; E2.true := E.true; E2.false := E.false; E.code := E1.code [删去 || gen(E1.true, ‘:’)] || E2.code 删去: 删去luanj@http://www.77cn.com.cn 15

E → E1 and E2

2011-3-28

编译原理,陈意云 ,课后答案

7.6 (续) 续表 (续E → not E1 E1.true := E.false; E1.false := E.true; E.code := E1.code E1.true := E.true; E1.false := E.false; E.code := E1.code E.code := gen(‘if’, id1.place, relop.op, id2.place, ‘goto’, E.true) || gen(‘goto’, E.false) [修改为 E.code := gen('if', id1.place, not(relop.op) , 修改为: 修改为 id2.place, 'goto', E.false))] E.code := gen(‘goto’, E.true) E.code := gen(‘goto’, E.false) E → (E1 )

E → id1 relop id2

E → true E → false

2011-3-28

luanj@http://www.77cn.com.cn