《编译原理》课后习题答案第八章
附加题
问题 1：
请将下列语句
while (AD) then X:=Y+Z
翻译成四元式
答案： 假定翻译的四元式序列从（100）开
始： （100） （101） （102） （103） （104） （105） （106） （107）
if A
if C goto （100） 问题 2： 对于输入的表达式(4*7+1)*2，根据下表的语法制导定义建立一棵带注释的分析树。 val:表示非终结符的整数值,综合属性,lexval 是单词 digit 的属性 语法制导定义 产生式 L →E E →E+T 1语义规则 print(E.val) E.val:=E.val+T.val 1E →T T →T*F 1E.val:=T.val T.val:=T.val*F.val 1T →F T.val:=F.val F.val:=E.val F.val:=digit.lexval F →(E) F →digit 盛威网（www.snwei.com）专业的计算机学习网站 11 《编译原理》课后习题答案第八章 答案： L E.val=58 T.val=58 T.val=29 ( E.val=29 ) T.val=1 F.val=1 F.val=7 digit.lexval=1 * F.val=2 digit.lexval=2 n E.val=28 + T.val=28 T.val=4 F.val=4 digit.lexval=4 * digit.lexval=7 盛威网（www.snwei.com）专业的计算机学习网站 12 《编译原理》课后习题答案第八章 问题 3： 请按语法制导的定义，将后缀表达式翻译成中缀表达式。注意，不允许出现冗余括号， 后续表达式的文法如下： E→EE+ E→EE* E→id 答案： 语法制导定义 S→E E→E1E2+ E→E1E2* E 一>id 产生式 语义规则 print E.code E.code=E1.code||'+'||E2.code; E.op='+' IF E1.op='+' AND E2.op='+' THEN E.code=\1.code||')'||'*'||'('||E2.code||')'; ELSE IF E1.op='+'THEN E.code=\1.code||')'||'*'||E2.code; ELSE IF E2.op='+'THEN E.code=E1.code||'*'||'('||E2.code||')'; ELSE E.code=E1.code||'*'||E2.code||; E.code:=id.lexeme; 问题 4： 有文法： S →(L)|a L→L,S|S 给此文法配上语义动作子程序(或者说为此文法写一个语法制导定义)，它输出配对括号 的个数。如对于句子(a,(a,a))，输出是 2。（中国科学院计算所 1994） 答案： 加入新开始符号 S'和产生式 S'→S，设 num 为综合属性，代表值属性，则语法制导定义 如下： 产生式 S'→S S→(L) S→a L→L1,S L→S 语义规则 print(S.num) S.num:=L.num+1 S.num:=0 L.num:=L1.num+S.num L.num:=S.num 盛威网（www.snwei.com）专业的计算机学习网站 13 《编译原理》课后习题答案第八章 问题 5： 文法 G 的产生式如下： S→(L)|a L→L,S|S ①试写出一个语法制导定义，它输出配对括号个数； ②写一个翻译方案，打印每个 a 的嵌套深度。如((a),a),打印 2,1。（中国科学院软件所 1999） 答案： ①为 S,L 引入综合属性 num，代表配对括号个数； 语法制导定义 产生式 S'→S S→(L) S→a L→L1,S L→S ②引入继承属性 f,代表嵌套深度 S'→ S→'(' ')' S→a {print(S.f);} L→{L1.f:=L.f;} L1, {S.f:=L.f} S L→{S.f:＝L．f;} S {S.f:=0} S {L.f:=S.f+1;} L 语义动作 print(S.num) S.num:=L.num+1 S.num:=0 L.num:=L1.num+S.num L.num:=S.num 盛威网（www.snwei.com）专业的计算机学习网站 14 《编译原理》课后习题答案第八章 问题 6： 对下面的文法，只利用综合属性获得类型信息。 D?L,id | L L?T id T?int | real 答案： 语法制导定义 产生式 D?L,id D?L L?T id T?int T?real 语义规则 D.type:=L.type addtype(id.entry,L.type) D.type:=L.type L.type:=T.type addtype(id.entry,T.type) T.type:=integer T.type:=real 盛威网（www.snwei.com）专业的计算机学习网站 15