编译原理与实践：两类特殊属性文法

前面已经对翻译过程的属性文法描述方法做了说明，这里将探讨这种翻译器的具体实现过程。众所周知，一个一般的属性文法翻译器可能是很难建立的，然而有一些属性文法的翻译器相对来说却很容易建立。本节考虑这样两类特殊的属性文法：S-属性文法和L-属性文法。

1.S-属性文法

从6.1.1节已经知道，S-属性文法仅含有综合属性，而且综合属性可以在分析输入符号串的同时由自下而上的分析器来计算。分析器可以保存与栈中文法符号有关的综合属性值，每当进行归约时，新的属性值就由栈中正在归约的产生式右边符号的属性值来计算。下面将介绍一种综合属性的计算方法，它通过扩充分析栈来存放综合属性值，从而使得对输入串进行语法分析的同时可以对属性进行计算。

在自下而上的语法分析中，曾使用一个栈来存放已经分析过的子树的信息，现在可以在分析栈中附加一个域来存放综合属性值。图6-5就是一个带有综合属性域的分析栈的例子，其中，栈是由一对数组state和value来实现的，栈顶指针用top表示。

图6-5　带有综合属性域的分析栈的工作过程

假设产生式A→XYZ的语义规则是A.a：=f（X.x，Y.y，Z.z），并且综合属性恰好是在每次规约前计算的。把文法符号和属性值放入栈中，当state[top]对应的符号为Z时，则value[top]中存放的就是与Z对应的属性值Z.z。类似的，Y放在state[top-1]中，Y.y则放在value[top-1]中；X放在state[top-2]中，X.x则放在value[top-2]中。如果一个符号没有综合属性，那么数组value中相应的元素就不定义。归约之后，top值减2，A存放在state[top]中（原来X的位置），综合属性A.a的值存放在value[top]中。

2.L-属性文法

通常，采用深度优先的方法对语法树进行遍历，从而计算属性文法的所有属性值。像LL（1）这种自上而下的分析过程，从概念上讲可以看成是深度优先建立语法树的过程。为了达到一次遍历就能计算出所有属性值的目的，这里将讨论一类属性文法，称作L-属性文法，它可以在自上而下语法分析的同时实现属性的计算。

一个属性文法称为L-属性文法，如果对于文法的每个产生式A→X1X2…Xn，其每个语义规则中的每个属性，或者是综合属性，或者是Xj（1≤j≤n）的一个继承属性，而且该继承属性仅依赖于：

（1）产生式Xj的左边符号X1，X2，…，Xj-1的属性；

（2）A的继承属性。

从定义可以看出，S-属性文法是L-属性文法的特例。

属性文法只是一种关于语言翻译的高级规范说明，并不含具体的实现细节。在进行语法制导翻译时，我们需要的是属性文法的另一种描述形式，即所谓的翻译模式（Translation Schemes）。翻译模式给出了使用语义规则进行计算的次序（也称为语义动作），用花括号“{”和“}”括起来，插入到产生式右部的合适位置上。

下面给出一个翻译模式的简单例子，其作用是把表达式的中缀形式翻译成相应的后缀形式。

E→TR

R→addop T{print(addop.lexeme)}R1|ε

T→num{print(num.val)}

其中，单词addop代表的是加号或减号，num则用来表示数字。图6-6给出了输入串9-5+2的语法树，并且把每个语义动作都作为相应产生式左部符号结点的子结点（用虚线表示），可以将这些语义动作看作是终结符号，表示将要执行的具体动作。当按深度优先次序执行图中的动作后，打印出的结果是95-2+。(www.xing528.com)

图6-6　带语义动作的9-5+2的语法树

翻译模式的设计必须保证当某个动作引用一个属性时，该属性是有定义的，而L-属性文法本身就能确保每个动作不会引用尚未计算出来的属性。当文法中仅含综合属性时，其翻译模式可以这样来建立：为每一个语义规则建立一个包含赋值的动作，并把该动作放在相应产生式右边的末尾；当文法中既含有综合属性，又含有继承属性时，其翻译模式的建立需满足如下要求：

（1）产生式右边符号的继承属性必须在这个符号以前的动作中计算出来。

（2）一个动作不能引用该动作右边符号的综合属性。

（3）产生式左边非终结符的综合属性只有在它引用的所有属性都计算出来之后才能计算，这种计算通常可以放在产生式右端的末尾。

例如，下面的翻译模式就不满足上述三个条件中的第一条：

S→A1A2 {A1.in:=1;A2.in:=2}

A→a {print(A.in)}

从图6-7中可以看出，按深度优先次序遍历输入串aa的语法树时，当要打印继承属性A1.in的值时，该属性尚未定义。也就是说，从S开始按深度优先遍历A1和A2子树之前，A1.in和A2.in均未赋值。但是，若将A1.in和A2.in的赋值动作嵌入在产生式S→A1A2的右部A1和A2之前的话，即：

图6-7　带语义动作的aa的语法树

S→{A1.in:=1;A2.in:=2}A1A2

那么A.in在每次执行print（A.in）时已有定义。

在了解了翻译模式相关概念之后，下面探讨如何利用翻译模式来实现L-属性文法的翻译工作。关于L-属性文法的翻译，可采用两种方法：一种是自上而下翻译，另一种是自下而上翻译，都属于一遍扫描的处理方法。

为了实现自上而下翻译，首先必须构建合适的翻译模式。在第4章中已经知道，为了构造不带回溯的自上而下语法分析，必须消除文法中的左递归。如果我们对消除左递归的算法进行扩充，在消除一个翻译模式的基本文法的左递归的同时考虑属性的计算问题，就会将仅含综合属性的翻译模式改造为既含有综合属性，又含有继承属性的翻译模式。于是，许多属性文法的翻译工作可以使用自上而下的方法来实现。对于这种方法，假设动作是在处于相同位置上的符号被展开（匹配成功）时执行的。

同样，实现自下而上翻译也需要构建合适的翻译模式，这种翻译模式要求把所有的语义动作都放在产生式的末尾，做法是：在基础文法中加入形如M→ε的新的产生式，其中M为新引入的一个标记非终结符；把嵌入在产生式中的每个语义动作用不同的M来代替，并把该动作放在产生式M→ε的末尾。转换前后的两个翻译模式中的文法接受相同的语言，动作的执行程序也是一样的。在转换后的翻译模式中，动作都在产生式右端的末尾，因此，可以在自下而上的分析过程中当产生式右部被归约的时候执行相应的动作。这种自下而上的翻译方法是S-属性文法自下而上翻译方法的一般化，不仅可以实现任何基于LL（1）文法的L-属性文法的翻译工作，还可以实现许多基于LR（1）文法的L-属性文法的翻译工作。