1 语法制导的定义

给分析树中每种文法符号 $X$ 一个属性 $a$，$X.a$ 是这种属性的值。

某个节点的属性，通过这个节点采用的产生式的语义规则来定义。

语法制导定义形式

一个文法产生式：$A\to \alpha$，这个产生式包含的文法符号的属性是 $b,c_1,...,c_m$

这个文法产生式的语法制导定义是一组形如 $$ b=f(c_1,c_2,...,c_m) $$ 的语义规则，$f$ 表示函数关系。

综合属性：$b$ 是 $A$ 的属性，$c_1,...,c_m$ 是产生式右部文法符号的属性或者 $A$ 的其他属性，则称 $b$ 是 $A$ 的综合属性。

继承属性：$b$ 是产生式右部 $\alpha$ 的某个文法符号 $X$ 的属性，$c_1,...,c_m$ 是产生式右部文法符号的属性或者 $A$ 的属性，则称 $b$ 是 $X$ 的继承属性。

上面两种情况都说属性 $b$ 依赖于 $c_1,...,c_m$。

• 分析树上一个节点的综合属性通过其子节点的诸属性值来计算
• 分析树上一个结点的继承属性通过其兄弟节点、父节点和自己的属性值来计算

终结符没有继承属性，只有综合属性，并且是字面值（由词法分析器提供），语法制导定义的语义规则不计算终结符的属性值。

只使用综合属性的语法制导定义称为 $S$ 属性定义，对于这种定义，各节点属性值的计算可以自下而上完成。

继承属性

考虑下面的文法及定义： $$ \begin{array}{|l|l|} \hline \text { 产 生 式 } & \text { 语 义 规 则 } \ \hline T \rightarrow T_1 * F & \text { T.val }=\text{T}_1 \text{.val * F.val} \ \hline T \rightarrow F & \text { T.val }=\text { F.val } \ \hline F \rightarrow \text { digit } & \text { F.val = digit.lexval } \ \hline \end{array} $$ 此文法存在左递归，如果对消除左递归后的文法想要写出语义规则： $$ \begin{array}{|l|c|} \hline \text { 产 生 式 } & \text { 语 义 规 则 } \ \hline T \rightarrow F W & \text { T.val }=\text { F.val } ? \ \hline W \rightarrow * F W_1 & \text { W.val }=? * \text { F.val } \ \hline W \rightarrow \varepsilon & \ \hline F \rightarrow \text { digit } & \text { F.val }=\text { digit.lexval } \ \hline \end{array} $$ 存在两个问题：

• $T$ 对应的项中，第 1 个运算分量是 $F$，而运算符 * 和其第 2 个运算分量在 $W$ 的子结构中
• $W \rightarrow * F W_1$：在分析 $W$ 期间，* 的左运算分量不在 $W$ 的子结构中

解决办法：

• 为 $W$ 引继承属性 $i$，继承运算符 * 的左运算分量的属性
• 为 $W$ 引入综合属性 $s$，它表示截至到该符号的计算结果

$$\begin{array}{|l|l|} \hline \text { 产 生 式 } & {\text { 语 义 规 则 }} \\ \hline T \rightarrow F W & W . i=F . v a l ; \quad T . v a l=W . s \\ \hline W \rightarrow * F W_1 & W_1 . i=W . i * F . v a l ; \quad W . s=W_1 . s \\ \hline W \rightarrow \varepsilon & W_{. }s=W . i \\ \hline \ldots & \ldots \\ \hline \end{array}$$

属性依赖图

由于继承属性导致不能自下而上计算，所以使用属性依赖图的方法确定计算次序：

• 若 $b$ 依赖 $c_1,...,c_m$，则有 $c_1,...,c_m$ 指向 $b$ 的 $m$ 条有向边
• 使用拓扑排序确定计算次序

S 属性定义

S 属性定义只允许出现综合属性，可以用后序遍历访问每个节点，以对语法分析树每个节点求值。

def post_order(N):
    for (child in N.child_list):
        post_order(child)
    N.求值

S 属性定义可以在自底向上语法分析过程中实现，因为一次自底向上语法分析过程对应于一次后序遍历。

L 属性定义

L 属性定义允许出现继承属性，但是这种继承属性只能是自左向右流动的信息。定义如下：

如果每个产生式 $A \rightarrow X_1 \ldots X_{j-1} X_j \ldots X_n$ 的每条语义规则计算的属性是 $A$ 的综合属性，或者是 $X_j$ 的继承属性，但它仅依赖： - 该产生式中 $X_j$ 左边符号 $X_1, X_2, \ldots, X_{j-1}$ 的属性 - $A$ 的继承属性

这种情况下可以按边分析边翻译的方式计算继承属性。

本文阅读量