语法制导翻译——语法制导定义

在这一部分，我们将主要介绍两种语法制导翻译的方法：语法制导定义和翻译方案。

语法制导定义通过为语法分析树的结点引入属性，并在翻译过程中计算属性值来执行翻译； 而翻译方案通过直接在产生式中嵌入语义动作来执行翻译。 语法制导定义通俗易懂，但效率较低，因此适合用来描述翻译过程； 而翻译方案效率高，通常用于翻译器的实现之中。

本部分中我们将先研究语法制导定义，给出如何计算各种属性的方法，然后研究用翻译方案和语法分析过程实现语法制导定义。 最简单、最通用的方法当然是先构造语法分析树，然后在树上进行计算，但是这样费时费力，因为需要先扫描一遍代码，再扫描一遍（甚至多遍）分析树。 本部分在此基础上主要研究两个特殊的情况：L（Left-to-right）属性翻译和S（Synthesis）属性翻译，这两者都不需要生成分析树就能计算所有属性。 其中L属性翻译可用在所有语法分析过程中。

语法制导定义

语法制导定义（Syntax-Directed Definition, SDD）是一个上下文无关文法、属性和规则的集合。 属性和一个文法符号（终结或非终结均可）相关，而规则和产生式相关。 这个如果文法符号X带有属性a，那么我们可把它记为X.a。 实现时可以把属性看作表示文法符号的记录（结构体）的数据字段或对象的成员变量。 这个变量可能有多种类型，诸如数字、（表示类型的）类型，引用或字符串等，这样的字符串可能很长，以用来表示中间代码。

继承属性和综合属性

文法符号对应的属性分为两种：

• 综合属性指由其本身为头的产生式上的规则决定的属性，在语法分析树上只由其本身和子节点的属性决定；
• 继承属性指由其父节点为头的产生式上的规则决定的属性，这种产生式必须包括此节点代表的文法符号，在语法分析树上只由其父节点、本身和兄弟节点的属性决定。

我们不允许结点上的继承属性通过子节点的属性来定义，但是我们允许综合属性通过其本身的继承属性计算，尽管这要求先计算继承属性，从而使综合属性依赖于子节点以外的结点。

原则上我们可以把某个结点的所有子节点的属性拷贝到这个结点中，这样允许该节点的继承属性使用子节点的属性进行计算，而不仅仅限于其父节点、本身和兄弟节点。 实践中很少需要这种继承属性。

我们先研究只有继承属性的SDD（称为S-属性的SDD），且假设没有属性求值副作用，即不打印字符、不修改符号表等。

利用语法分析树求值

直接在语法分析树上求值有助于我们理解语法制导翻译，但是翻译器通常并不直接构造这样一棵树。 我们称在结点上标注了所有属性的值的语法分析树为注释语法分析树。

如果要求出某个结点的属性值，我们必须先求出它所依赖的所有属性。 如果一个SDD是S-属性的，那么求值还是非常简单的，只需要按自底向上的方式逐一求值即可，这可由后序遍历实现。 对于同时具有继承和综合属性的SDD，求解求值顺序是一个相对困难的问题，甚至完全可能存在循环依赖而无法求值的情况。 不幸的是，产生式对应的语法分析树和表达式对应的抽象语法树之间存在很大差别时，使用继承属性几乎是不可避免的。

考虑下面这个语法制导定义： \(\begin{aligned} & T \to F T^\prime & T^\prime.inh = F.val, \; T.val = T^\prime.syn \\ & T^\prime \to * F T_1^\prime & T_1^\prime.inh = T^\prime.inh \times F.val, \; T^\prime.syn = T_1^\prime.syn \\ & T^\prime \to \epsilon & T^\prime.syn = T^\prime.inh \\ & F \to \mathbf{digit} & F.val = \mathbf{digit}.lexval \end{aligned}\) 这个翻译方案是典型的$T \to F * F$的左递归消除后的版本。 由于其产生的语法分析树和抽象语法树相差较大，不得不使用继承属性。 这里我们在检测到乘号，即利用第二个产生式时，继承左侧结点的值并用来计算乘法。

我们接下来仔细研究属性的求值顺序。

SDD的求值顺序

利用依赖图确定求值顺序

虽然如果只给出SDD，求解其求值顺序是困难的，但如果已经构造出了语法分析树，那么利用依赖图和拓扑排序可以确定树各个属性的求值顺序。

我们规定依赖图是这样一张有向图： 对每个语法分析树的结点，属于它的每个属性都有一个结点； 如果我们需要用某个结点$A$的属性来确定另一个结点$B$的属性，那么就从$A$到$B$连接一条有向边。

如果已经构造了语法分析树和依赖图，那么只需要使用拓扑排序就可以确定表达式的求值顺序了。 如果在拓扑排序中发现了环，那么就说明不存在可以求出某些属性的方法。

S-属性和L-属性

对于某些特定的SDD，我们不需要构造语法分析树就可以直接求出属性值。 考虑到翻译时通常并不构造语法分析树，这种SDD对我们特别有吸引力。

我们此前已经见到过S属性的SDD了，这种SDD构造的任意语法分析树都可以用自底向上的方法求出所有属性值。 尤其重要的是，我们可以直接在LR语法分析（更一般地说，所有自底向上语法分析方法）中顺便求出所有的属性，因为自底向上的分析恰好对应对语法分析树的后序遍历。 在LR分析栈中存放额外的信息，即可在不构造语法分析树的情况下求出所有综合属性。 我们将在后面仔细介绍这一过程。

接下来我们主要介绍L属性的SDD，这种SDD也可以按特定的方法求出所有属性值，而且可用于绝大多数现有的语法。 如果一个SDD是L属性的，那么它的所有属性都必须满足以下性质：

• 要么这个属性是综合属性；
• 要么这个属性是继承属性，但是对它有以下要求： 如果存在一个产生式$A \to X_1 X_2 \dots X_n$，并且这个属性是产生式体中一个符号的属性，写作$X_i.a$，那么这个属性只能依赖于：
  1. 产生式头的继承属性；
  2. 位于$X_i$左侧的符号的继承或综合属性；
  3. $X_i$本身的继承或综合属性，且依赖图中不存在环。

这相当于要求每个继承属性只能依赖于其上面或左侧的结点的属性值。 举例来说，我们上面举的例子中的SDD就是一个L-属性的SDD。 而任何包含下列产生式和规则的SDD都不可能是L-属性的： \(\begin{aligned} A \to B C \quad & A.s = B.b \\ & B.i = f(C.c,A.s) \end{aligned}\) 因为在第二条语义规则中我们使用了$B$右侧的文法符号的属性值。

具有受控的副作用的语义规则

在实践中，语义规则可能产生一些副作用，比如打印输出或修改符号表，但我们此前并不考虑这些。 实际上，SDD在属性计算和翻译方案间找到一个平衡点。 对前者，我们说其没有副作用，并可以按任何和依赖图一致的顺序进行翻译； 对后者，其可以含有任何代码，但必须严格按从左至右的方式求值并执行。

我们用两种方法在SDD中执行带有副作用的动作：

1. 要求副作用不会对属性求值产生约束，即任何按照拓扑序进行的求值，在考虑到其可能的副作用的情况下，都能产生期望的结果；
2. 约束可能的求值顺序，使在剩下的顺序中，副作用不对求值产生影响。

应用语法制导定义

我们来研究语法制导定义的经典应用：构造抽象语法树。

构造抽象语法树

我们知道，相较于语法分析树，抽象语法树是更常见的中间表示形式，因为其更加简单地表述了程序的结构。 在抽象语法树中，其一个结点表示了一个程序构造，而子节点表示了这个构造的组成部分。 比如表示表达式$E_1 + E_2$的抽象语法树的根节点标号为+，而其分别有两个子节点E_1和E_2。

我们用一个对象（或记录、结构体等）表示抽象语法树的一个结点，它至少含有一个属性op，用来表示这个结点的标号。 视这个结点的类型不同，其还可能含有其他属性，比如指向子节点的指针、指向符号表条目的指针或是表示常数的数值。 我们用两个函数来构造叶子节点和内部节点：

• Leaf(op,val)表示构造一个标号为op，其有一个附加的属性用来储存器词法值，可以是常数或是符号表条目之类的；
• Node(op,c1,c2,...)表示构造一个标号为op的内部节点，其附加的属性数目和其子节点的数目相同，从左至右分别为c1,c2,...，这些属性通常是指向子节点的指针。

我们考虑一个简单的计算加减法的文法，其语义规则如下：

产生式	语义规则
$E \to E_1 + T$	E.node = new Node('+', E1.node, T.node)
$E \to E_1 - T$	E.node = new Node('-', E1.node, T.node)
$E \to T$	E.node = T.node
$T \to (E)$	T.node = E.node
$T \to \mathbf{id}$	T.node = new Leaf(id, id.entry)
$T \to \mathbf{num}$	T.node = new Leaf(num, num.val)

id.entry指向符号表的条目，而num.val表示这个数字的值。 我们在此处只指出如何在已经构造出语法分析树的情况下用语义规则构造抽象语法树，而将其构造和语法分析过程结合起来的技巧将在后文介绍。

如果要用于自顶向下分析，那么这个文法是不能使用的，因为其含有左递归。 下面这个文法和是上面的左递归消除版本，虽然其生成的语法分析树和上文的大不相同，但是仍可以产生相同的抽象语法树。 我们在介绍用翻译方案实现语法制导定义时会介绍左递归消除对翻译方案的影响。

产生式	语义规则
$E \to T E^\prime$	E.node = E'.syn, E'.inh = T.node
$E^\prime \to + T E_1$	E1'.inh = new Node('+', E'.inh, T.node), E'.syn = E1'.syn
$E^\prime \to - T E_1$	E1'.inh = new Node('-', E'.inh, T.node), E'.syn = E1'.syn
$E^\prime \to \epsilon$	E'.syn = E'.inh
$T \to (E)$	T.node = E.node
$T \to \mathbf{id}$	T.node = new Leaf(id, id.entry)
$T \to \mathbf{num}$	T.node = new Leaf(num, num.val)

上文所述SDD的基本想法就是把表达式左侧的部分作为$E^\prime$的继承属性传递，直到发现运算符时再构造整个表达式的结点。 这个属性，即inh，表示了至今为止已经构造的所有表达式的根节点。 而syn属性将这个根节点向上传递至E.node，这是通过在表达式末尾使用$E^\prime \to \epsilon$产生式实现的。

继承属性的用处

我们反复强调，继承属性在语法分析树和抽象语法树的结构不同时尤其有用，因为它可以把信息从语法分析树的一个子树传递到同一根的另一个子树中去。 如果语法分析树和抽象语法树结构相同，那么这种传递是很少见的，因为抽象语法树的一个子树对应语法分析树的一个子树。 而两者结构不同时，抽象语法树的子树可以横跨语法分析树的多个子树，因此需要使用继承属性。

如果要使用自顶向下分析方法，那么不能使用左递归的文法，这会使得语法分析树和抽象语法树的结构不同。 除此之外，即使不需要消除左递归，语法本身的特点也会要求使用继承属性，尽管语法分析树可能和抽象语法树相当相似。

考虑C/C++语言中的数组声明问题，加入我们用int [2][3]声明一个二维数组，那么我们实际上是声明了一个int [3]的数组，再把它扩张一维。 用表达式可以写成array(2, array(3, integer))。 在这种情况下，我们不得不把最开头的类型（int）用继承属性一直传递到最后一个方括号为止，然后逐层向上生成表示数组的抽象语法树结点。

下面这个语法制导定义解决了这个问题：

产生式	语义规则
$T \to B C$	T.t = C.t
$B \to \mathbf{int}$	B.t = integer
$C \to [\mathbf{num}] C_1$	C.t = array(num.val, C_1.t), C1.b = C.b
$C \to \epsilon$	C.t = C.b

我们可以注意到，正如前面所述，表示对表示数组声明的语法分析树结点（标号为$T$），右子树需要的一些信息（每个元素的类型）在左子树之中。