编译原理作业集－第七章 语义分析和中间代码产生
}
翻译为：(1)一棵语法树， (2)后缀式， (3)三地址代码。
6.答案：（1）
（2） 后缀式为： i 10 <= a i [] 0 = while
从理论上可以说 while ( i <= 10 ) a[i] = 0; 的后缀式如上面表示。但若这样表示，在执行while操作时，赋值语句已经执行，这显然与语义不符，因此改为：
i 10 <= <下一个语句开始地址> BM a i [] 0 = <本语句始址>BRL
其中BM操作为当表达式为假时转向<下一个语句开始地址>，BRL是一个一目运算，无条件转向<本语句始址>。 （3） 三地址代码序列为： 100 if i <= 10 goto 102 101 goto 106 102 t1 := 4 * i 103 t2 := a 104 t2[t1] := 0 105 goto 100 106
7. 已知布尔表达式翻译成三地址代码的翻译模式如下： E→E1 or E2 { E.place:=newtemp; emit(E.place ':=' E1.place 'or' E2.place) } E→E1 and E2 { E.place:=newtemp; emit(E.place ':=' E1.place 'and' E2.place) } E→not E1 { E.place:=newtemp; emit(E.place ':=' 'not' E1.place) } E→(E1) { E.place:= E1.place } E→id1 relop id2 { 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→id1 { E.place:=id.place }
试编写一个递归下降程序，用来该属性文法。
西安理工大学计算机科学与工程学院，张发存编写 2013-5-20，9:37:18
- 11 - - -
编译原理作业集－第七章 语义分析和中间代码产生
7. 答案：
首先消除该翻译模式的左递归：
（注：'{','}'为元语言符号。） 递归预测翻译程序如下：
TYPE link = 表类型; PROCEDURE E ; VAR E.truelist, E.falselist, T.truelist, T.falselist: link; BEGIN { E.truelist, E,falselist } := T; WHILE ( lookahead == 'or ' ) DO BEGIN match(or); M.quad := nextquad; { T.truelist, T.falselist } := T; backpatch(E.falselist, M.quad); E.truelist := merge(E.truelist, T.truelist); E.falselsit := T.falselist END; return({E.truelist, E.falselist}) END;
PROCEDURE T; VAR T.truelist, T.falselist, F.truelsit, F.falselist: link;
西安理工大学计算机科学与工程学院，张发存编写 2013-5-20，9:37:18
- 12 - - -
编译原理作业集－第七章 语义分析和中间代码产生
BEGIN { T.truelist, T,falselist } := F; WHILE ( lookahead == 'and ' ) DO BEGIN match(and); M.quad := nextquad; { F.truelist, F.falselist } := F; backpatch(T.truelist, F.truelist); T.truelist := F.truelist; T.falselist := merge(T.falselist, F.falselist) END; return({T.truelist, T.falselist}) END;
PROCEDURE F; VAR F.truelist, F.falselist, E.truelsit, E.falselist: link; BEGIN CASE ( lookahead ) OF 'not' :BEGIN match(not); { E.truelist, E.falselist } := F; F.truelist := E.falselist; F.falselist := E.truelist END; '( ' : BEGIN match((); { E.truelist, E.falselist ) := E; match()); F.truelist := E.truelist; F.falselist := E.falselist END; 'id' : BEGIN match(id); match(relop); match(id); F.truelist := makelist(nextquad); F.falselist := makelist(nextquad+1); emit('if' id1.place relop id２.place 'goto-'); emit('goto-') END； 'true': BEGIN match(true); F.truelist := makelist(nextquad);
西安理工大学计算机科学与工程学院，张发存编写 2013-5-20，9:37:18
- 13 - - -
编译原理作业集－第七章 语义分析和中间代码产生
F.falselist := null; emit('goto-') END; 'false':BEGIN match(false); F.truelist := makelist(nextquad); F.falselist := null; emit('goto-') END otherwise : error END of CASE return({F.truelist, F.falselist}) END;
8. 试编写翻译模式，用来实现do-while语句的回填算法。 8.答案：
do-while语句的三地址代码结构如下：
从do-while语句的三地址代码结构可以知道，开始，要记录下L.code的开始地址，以填写E.truelist。 生成E.code之前，要记录下E.code的开始地址，用它填写L.nextlist。为此，在规则相应处添加标记非终结符，以完成相应的语义动作。翻译模式如下：
9. Pascal语言中，语句
for v：＝initial to final do stmt
西安理工大学计算机科学与工程学院，张发存编写 2013-5-20，9:37:18
- 14 - - -
编译原理作业集－第七章 语义分析和中间代码产生
与下列代码序列有相同含义
begin t1:=initial; t2:=final; if t1<=t2 then begin v:=t1; stmt while v<>t2 do begin v：=succ（v)； stmt end end end
(1)试考虑下述Pascal程序
program forloop(input, output); var i,initial,final: integer; begin read(initial, final); for i:= initial to final do write(i) end
对于initial=MAXINT-5和final= MAXINT，问此程序将做些什么？其中MAXINT为目标机器允许的最大整数。
(2)试构造一个翻译pascal的for语句为三地址代码的语法制导定义。 9.
（1）显示如下六个整数： MAXINT -5 MAXINT -4 MAXINT -3 MAXINT -2 MAXINT -1 MAXINT
（2）为简单起见，for语句的三地址代码如下：
t1 := initial t2 := final
if t1 > t2 goto S.next v := t1 stmt.code S.begin:
if v > t2 goto S.next v := succ(v) stmt.code goto S.begin
语法制导定义如下：
西安理工大学计算机科学与工程学院，张发存编写 2013-5-20，9:37:18
- 15 - - -