编译原理作业集 第六章 属性文法和语法制导翻译
当识别出X后，并不能计算出X的继承属性，因而，也就无法计算有关X的其他属性。只好把X的源表示或中间表示作为继承传给R，继续沿R传下去，然后再作为综合属性传回来。直到能计算出X.i,再对X的成分进行翻译。Y1,Y2,Y3的翻译思想和X类似，具体的翻译模式省略。
14. 对于带有继承属性的自底向上的分析和翻译，使用标记非终结符号来保存继承属性的值于分析栈中可预定的位置上。如果这样的值放在与分析栈分开的栈中，就可能需要较少的标记非终绪符号。
已知数学格式语言EQN的所有继承属性都由复写规则赋值的属性文法如下： 产生式 S?LB L?? B?B1MB2 B?B1subNB2 语义规则 B.ps:=L.s S.ht:=B.ht L.s:=10 B1.ps:=B.ps M.i:=B.ps B2.ps:=M.s B.ht:=max(B1.ht,B2.ht) B1.ps:=B.ps N.i:=B.ps B2.ps:=N.s B2.ht:=disp(B1.ht,B2.ht) B.ht:=text.h*B1.ps M.s:=M.i N.s:=shrink(N.i) B?text M?? N??
（1）把上表中的语法制导定义转化为翻译模式。
（2）修改（1）中的翻译模式，使继承属性ps的值出现在分开的栈中。在处理过程中消除标记非终结符号M。
14.答案：(1) 把上表中的语法制导定义改写成下面的翻译模式：
S → L {B.ps:=L.s} B {S.ht:=B.ht}
西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:06 AM
- 21 -
编译原理作业集 第六章 属性文法和语法制导翻译
L → ε {L.s:=10}
B → {B1.ps:=B.ps} B1 {M.i:=B.ps} M {B2.ps:=M.s} B2 {B.ht:=max(B1.ht,B2.ht)} M → ε { M.s:=M.i}
B → {B1.ps:=B.ps} B1 sub {N.i:=B.ps} N {B2.ps:=N.s} B2 {B.ht:=disp(B1.ht,B2.ht)} B → text {B.ht:=text.h*B.ps} N → ε {N.s:=shrink(N.i)}
(2) 设一个栈ps，管理继承属性B.ps的值。栈的三个操作为push(ps,值),pop(ps),top(ps).翻译模式如下：
S → L {B.ps:=top(ps)} B {S.ht:=B.ht} L → ε {push(ps,10)}
B → {B1.ps:=top(ps)} B1 {B2.ps:=top(ps)} Bsub>2 {B.ht:=max(B1.ht,B2.ht)} B → {B1.ps:=top(ps)} B1 sub N (B2.ps:=top(ps)} Bsub>2 {B.ht:=disp(B1.ht,B2.ht); pop(ps)} B → text {B.ht:=text.h*B.ps} N → ε {push(ps,shrink(top(ps)))}
15. 文法G的产生式如下： S → (L) | a L → L , S | S
(1)试写出一个语法制导定义，它输出配对括号个数;
(2)写一个翻译方案，打印每个a的嵌套深度。如((a),a),打印2,1。 【解】解题思路 本题包括两部分，第1部分要求写语法制导定义，第2部分要求写翻译方案。语法制导定义（或属性文法）可以看作是关于语言翻译的高级规范说明，其中隐去实现细节，使用户从明确说明翻译顺序的工作中解脱出来。翻译方案（也称翻译模式）给出了使用语义规则进行计算的次序，把某些实现细节表示出来。读者从下面解答中可体会两者的区别。 解答
为S、L引入属性h,代表配对括号个数。语法制导定义如下：
产生式 语义规则
S.h:=L.h+1 S → (L)
S.h:=0 S → a
L → L1 , S L.h:=L1.h+S.h
L.h:=S.h L → S
print(S.h) S’→S
(2)为S、L引入d，代表a的嵌套深度。翻译方案如下： S’→｛S.d:=0;｝S
S →‘(’{L.d:=S.d+1;} L ‘)’ S →a{print(S.d);} L → {L1.d:=L.d;} L1
{S.d:=L.d;} S
西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:06 AM
- 22 -
编译原理作业集 第六章 属性文法和语法制导翻译
L → {S.d:=L.d} S
16. 由下列文法 S→E E→E:=E | E+E | (E) | id
产生的表达式，其语义如C语言，包含赋值运算。就是说，b:=c是一个表达式，把c的值赋给b；该表达式的右值为c的右值。进而，a:=(b:=c)先把c的值赋给b，然后再赋给a。 (1) 试建立一个属性文法，用非终结符E的继承属性side表示由E生成的表达式出现在赋值运算的左边还是右边，检查表达式的左部是一个左值。 (2) 扩充（1）中的属性文法，产生某种形式的中间代码 解：
（1）语法制导定义如下
S → E { E.side = right; }
E → E1 := E2 { if (E.side == left) error;
else { E1.side = left; E2.side = right; }}
E → E1 + E2 { if (E.side == left) error;
else { E1.side = E2.side = right; }}
E → ( E1 ) { if (E.side == left) error;
else { E1.side = right; }}
E → id
（2）扩充 （1）中语法制导定义，使得在检查同时将表达式翻译为抽象堆栈机代码 解：语法制导定义如下，其中，valcode 表示取表达式右值的代码 S → E { E.side = right; S.code = E.code; } E → E1 := E2 { if (E.side == left) error;
else { E1.side = left; E2.side = right; }
E.code = E1.code || E2.code || ':=' || E1.valcode; }
E → E1 + E2 { if (E.side == left) error;
else { E1.side = E2.side = right; } E.code = E1.code || E2.code || '+'; }
西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:06 AM - 23 -
编译原理作业集 第六章 属性文法和语法制导翻译
E → ( E1 ) { if (E.side == left) error;
else { E1.side = right; } E.code = E1.code; }
E → id{ E.code = 'lvalue' id.lexeme; E.valcode = 'rvalue' id.lexeme; }
西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:06 AM - 24 -