编译原理作业集 第六章 属性文法和语法制导翻译
（1）若b是A的一个属性，且c1，c2，…，ck是产生式右边文法符号的属性，则称b是A的综合属性；
（2）若b是产生式右边某个文法符号的一个继承属性，且c1，c2，…，ck是A或者产生式右边任何文法符号的属性，则称若b是该文法符号的继承属性。
2. 基于属性文法的处理过程，首先对单词符号进行语法分析，构造语法分析树，然后根据需要遍历语法树并在语法树的各结点处按语义规则进行计算。这种由源程序的语法结构所驱动的翻译方法称语法制导翻译法。
3. 把一棵语法树中的结点的继承属性和综合属性之间的相互依赖关系用一个有向图来描述，这个有向图称为属性依赖图。
4. 仅仅使用综合属性的属性文法称为S－属性文法。 如果一个属性文法，其每个语义规则中文法符号的每个属性，或者是综合属性，或者是一个仅依赖于该文法符号左边符号（包括箭头左边的那个非终结符）的继承属性，则称该熟悉该属性文法是L－属性文法。
5. 对于一个上下文无关文法的产生式，把和文法符号相关的属性和语义规则，用花括号｛｝括起来插入到产生式右部的合适位置上，从而得到语法制导翻译的另一种描述形式，称为翻译模式。
五、简答题：
1. 一般情况下，为什么语义分析部分仅产生中间代码？
2. 什么是语法制导翻译？为什么把这种方法叫语法制导翻译？ 3. 给定一个L－属性文法，建立翻译模式要满足哪些条件？ 4. 什么叫基于属性文法的处理方法？
5. 如何从翻译模式中去掉嵌入在产生式中间的动作？
五．答案：
1. 一般情况下，语义分析部分仅产生中间代码，其原因是： （1）可使难点分解，分别解决；
（2）可对语义分析产生的中间代码进行优化，以产生高效率的目标代码；
（3）语义分析通常与机器无关，目标代码往往与机器有关。把语义分析与目标代码生成分开，可让一个语义分析程序适用于多个目标代码生成程序。
2. 所谓语法制导翻译，是指在语法规则的指导下，通过语义规则，完成对输入符号串的翻译。 由于使用属性文法时把语法规则和语义规则分开，但在使用语法规则进行推导或归约的同时又使用这些语义规则来指导翻译与最终产生目标代码，所以称为语法制导翻译。
3. 当只需要综合属性的时候，为每一个语义规则建立一个包含赋值的动作，并把这个动作放在相应的产生式右边的末尾。
如果既有综合属性又有继承属性，在建立翻译模式时要满足三个条件：
（1）产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来； （2）一个动作不能引用这个动作右边的符号的综合属性； （3）产生式左边非终结符的综合属性只有在它所引用的所有属性都计算出来以后才能计算，
西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:06 AM
- 6 -
编译原理作业集 第六章 属性文法和语法制导翻译
计算这种属性的动作通常放在产生式右端的末尾。
六、应用题：
1. 欲打印表达式(4*7+1)*2的值。写出属性文法，根据该属性文法建立一棵带注释的分析树，并在该分析树上用箭头标出属性计算次序。 答案：1. 产生式 L?En E ?T T ?T1*F T?F F?(E) F?digit
E?E1+T 语义规则 print(E.Val) E.Val=E1.Val+T.Val E.Val=T.Val T.Val=T1.Val+F.Val T.Val=F.Val F.Val=E.Val F.Val=digit.lexVal
2. 已知上下文无关文法： E→E+T E→E-T E→T T→(E) T→id T→num
已知表达式((a)+(b))。不对文法进行修改，写出为表达式建立抽象语法树的属性文法；并画
西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:06 AM
- 7 -
编译原理作业集 第六章 属性文法和语法制导翻译
出带注释的语法分析树来描绘抽象语法树的构造。 2. 答案： 产生式 E?E1+T E ? E1-T E ? T T ?(E) T ? id T ? num
根据该语法制导定义建立表达式((a)+(b))的分析树和抽象语法树：
语义规则 E.nptr:=mknode(?+?，E1.nptr，T.nptr) E.nptr :=mknode(?-?，E1.nptr，T.nptr) E.nptr :=T.nptr T.nptr :=E.nptr T.nptr :=mkleaf(id，id.entry) T.nptr :=mkleaf(num，num.val)
3. 已知上下文无关文法： E→E+T E→E-T E→T T→(E) T→id T→num
已知表达式((a)+(b))。采用自顶向下的翻译模式，写出构造抽象语法树的、消除了左递归的翻译模式，并画出带注释的语法分析树来描绘抽象语法树的构造。 3. 答案：翻译文法
西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:06 AM - 8 -
编译原理作业集 第六章 属性文法和语法制导翻译
E?E1+T {E.val:=E1.val+T.val} E?E1-T ｛E.val:=E1.val-T.val｝ E?T {E.val:=T.val} T?(E) ｛T.val:=E.val｝ T?num ｛T.val:=num.val} 消除左递归的翻译文法： E→T {R.i:=T.val} R {E.val:=R.s｝ R→＋ T｛R1.i:=R.i+T.val} R1{R.s:=R1.s} R→- T｛R1.i:=R.i-T.val} R1{R.s:=R1.s} R→ε{R.s:=R.i} T→（ E ）{T.val:=E.val} T→num{T.val:=num.val}
4. 试给出把中缀表达式转换成没有多余括号的中缀表达式的语法制导定义。例如，由于+和*都是左结合的，((a*(b+c))*(d))可以写成a*(b+c)*d。 4. 答案；
设置下面的函数和属性：
expr1||expr2：把表达式expr2拼写在表达式expr1后面。
- 9 -
西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:06 AM
编译原理作业集 第六章 属性文法和语法制导翻译
deletp(expr)：去掉表达式expr左端的?（?和右端的?)?。
E.expr，T.expr，F.expr：属性变量，分别表示E，T，F的表达式。 E.add，T.add，F.add：属性变量，若为true，则表示其表达式中外层有?＋?号，否则无?＋?号。
E.pmark，T.pmark，F.pmark：属性变量，若为true，表示E，T，F的表达式中左端为?（?，右端是?）?。
语法制导定义如下： 产生式 语义规则
E → E1 +T if(T.pmark==true)
THEN E.expr=E1.expr||'+'||deletep(T.expr) ELSE E.expr:=E1.expr||'+'||T.expr; E.add:=true; E.pmark:=false;
E → T if(T.pmark==true)
THEN E.expr:=deletep(T.expr) ELSE E.expr:=T.expr; E.add:=T.add; E.pmark:=false;
T → T1*F T.expr:=T1.expr||'*'||F.expr;
T.add:=false; T.pmark:=false;
T → F T.expr:=F.expr;
T.add:=F.add;
T.pmark:=F.pmark;
F → (E) if(E.add==false)
THEN BEGIN F.expr:=E.expr; F.add:=false; F.pmark:=false; END
ELSE BEGIN
F.expr:='('||E.expr||')'; F.add:=true; F.pmark:=true; END;
F → id F.expr:=id.lexval;
F.add:=false; F.pmark:=false;
5. 下面文法产生的表达式是对整型和实型常数应用算符+形成的。当两个整数相加时,结果为整数，否则为实数。 E→E+T | T
T→num.num | num
西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:06 AM
- 10 -