第 6 章 属性文法

6.1. 属性文法

6.1.1. 定义

属性文法也称属性翻译文法，是以上下文无关文法为基础的。

定义 6.1 对文法中的每一个符号（终结符和非终结符）指派若干表达语义的“值”，这些值就称为属性。它代表与文法符号相关的信息，如类型、值、代码序列、符号表等相关内容。

定义 6.2 同一条产生式规则中，符号的属性之间的计算法则，称为语义规则。对于文法的每一个产生式都配备了一组属性的语义规则，对属性进行计算和传递。

如对产生式规则 $E \to T + F$，从语义角度看，就是将表达式 $\displaystyle{ T }$ 和 $\displaystyle{ F }$ 的值相加，结果作为 $\displaystyle{ E }$ 的值。这启发我们

1. 给这三个符号配备一个属性 v，用于表示表达式的值
2. 从语义的角度来看，三个符号的语义处理规则是 $E . \text{v} = T . \text{v} + F . \text{v}$

定义 6.3 在上下文无关文法中配置上语义规则，这样的文法称为属性文法。

定义 6.4 设有一条产生式规则 $A \to X_1 X_2 \cdots X_n$，相应的语义规则是 $b=f(a_1, a_2,\cdots,a_k)$，如果 $\displaystyle{ b }$ 是 $\displaystyle{ A }$ 的一个属性，则称 $\displaystyle{ b }$ 是 $\displaystyle{ A }$ 的综合属性。如果 $\displaystyle{ b }$ 是右部某个 $\displaystyle{ X _{ i } }$ 的属性，则称 $\displaystyle{ b }$ 是 $\displaystyle{ X _{ i } }$ 的继承属性。

继承属性主要用于自上而下地传递语义信息。

例 6.1 判断下列 $E . \text{v}$ 和 $L . \text{in}$ 是什么属性

1. $E \to T \ast F$，语义规则是 $E . \text{v} = T . \text{v} \ast F . \text{v}$
2. $D \to T L$，语义规则是 $L . \text{in} = T . \text{type}$

例 6.2 设有一个文法 $\displaystyle{ G \left[ L \right] }$

$\text{n}$ 表示输入的是换行符

由于是表达式求值，从语义角度上看，每一个符号都应该有一个表达式的值，所以指派属性 val

终结符的综合属性是由词法分析程序提供的，作为已知的值（相当于初始值非终结符可能既有综合属性，又有继承属性

6.1.2. 综合属性

综合属性用于自下而上的传递信息。

从语法规则的角度看，对于产生式规则 $E \to T + F$，有语义规则 $E . \text{val} := T . \text{val} + F . \text{val}$，即用右部的属性来计算左部被定义的符号的综合属性。

从语法树角度来看，是根据子节点属性和父节点自身属性计算父节点的综合属性。从算术表达式 $\displaystyle{ 3 \cdot 5 + 4 }$ 可以得到以下的语法树。

定义 6.5 在语法分析树中标记出各个节点的属性值，这种语法分析树被称为注释分析树。

根据自底向上的语法分析，按照从左到右、从叶到根的计算次序，在语法分析的同时，可以将所有的属性值全都计算出来。

6.1.3. 继承属性

继承属性主要用于自上而下地传递语义信息。

主要反映的情形：在语法分析树中，一个节点的继承属性值由其父节点的属性值或兄弟节点的属性值来确定。主要用于表达上下文的依赖性。

第一条含义： $\displaystyle{ L }$ 的继承属性 in 存放 $\displaystyle{ T }$ 的综合属性 type。因为 $T . \text{type}$ 存有变量定义的数据类型信息。这个上下文信息要通过 $L . \text{in}$第四条含义：$\displaystyle{ L _{ 1 } }$ 的继承属性由左边 $\displaystyle{ L }$ 的继承属性得到，即向下传递。addType 函数会在符号表中找到 id 的入口，并将类型信息设置为 $L. \text{in}$。

考虑变量声明语句 int i1, i2, i3，有下面的语法分析树

6.1.3* 补充

属性依赖

对应于每个产生式 $A \to \alpha$ 都有一套与之相关联的语义规则，每条规则的形式为（$\displaystyle{ f }$ 是一个函数）

那么我们说，属性 $\displaystyle{ b }$ 依赖于属性 $c_1, c_2, \cdots, c_k$，有两种情况

• $\displaystyle{ b }$ 是 $\displaystyle{ A }$ 的一个综合属性并且 $c_1, c_2, \cdots, c_k$ 是产生式右边文法符号的属性（例如算术表达式中的加法）
• $\displaystyle{ b }$ 是产生式右边某个文法符号的一个继承属性，并且 $c_1, c_2, \cdots, c_k$ 是 $\displaystyle{ A }$ 或产生式右边任何文法符号的属性（例如 $D \to TL$ 和 $L \to \text{id}$）

终结符没有子节点，只有综合属性，由词法分析器提供，例如 $F \to \text{digit}$ 中，digit 的属性 lexval 由词法分析器提供。

非终结符既可有综合属性也可有继承属性，文法开始符号的所有继承属性作为属性计算前的初始值（例 6.2）。

语义规则

对于出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个计算规则。属性计算规则中只能使用相应产生式中的文法符号的属性。例如

• $E \to T + F$，$E . \text{val} := T . \text{val} + F . \text{val}$（产生式左边的综合属性）
• $D \to TL$，$L . \text{in} = T . \text{type}$（产生式右边的继承属性）

出现在产生式左边的继承属性和出现在产生式右边的综合属性 不由 所给的产生式的属性计算规则进行计算，而是由其他产生式的属性规则计算或由属性计算器的参数提供。

• $L \to \text{id}$，$\text{addType(id.entry},L \text{.in)}$（$\displaystyle{ L }$ 的继承属性依赖于它的兄弟节点和父节点，$\displaystyle{ L }$ 是由 $D \to TL$ 算得的）

语义规则所描述的工作可以包括属性计算、静态语义检查、符号表操作、代码生成等。

选择题 考虑非终结符 $\displaystyle{ A , B , C }$，其中，$\displaystyle{ A }$ 有继承属性 a 和综合属性 b，$\displaystyle{ B }$ 有综合属性 c，$\displaystyle{ C }$ 有继承属性 d。产生式 $A \to BC$ 不可能有规则（？）

1. $C . \text{d}=B . \text{c} + 1$
2. $A . \text{b} = B . \text{c} + C . \text{d}$
3. $B . \text{c} = A . \text{a}$

6.1.4. 属性计算

语义规则的计算所完成的任务

• 产生代码
• 在符号表中存放信息
• 给出错误信息
• 执行任何其他动作

对输入串的翻译就是根据语义规则进行计算

由源程序的语法结构所驱动的处理办法就是语法制导翻译法

• 输入串 → 语法树 → 按照语义规则计算属性

依赖图

在一颗语法树中的节点的继承属性和综合属性之间的相互依赖关系，可由依赖图来描述。

为每一个包含过程调用的语义规则引入一个虚拟综合属性 b，这样把每一个语义规则都写成

这样就统一了语义规则的形式。

依赖图中为每一个属性设置一个节点，如果有属性 b 依赖于属性 c，则有一条有向边为 $c \to b$，若有 $A . \text{b} = f(X . \text{x}, Y . \text{y})$，则有 $X . \text{x} \to A . \text{b}$ 和 $Y . \text{y} \to A . \text{b}$ 两条边。

例 对算术表达式文法进行分析

对变量声明语句进行分析

一个依赖图的任何拓扑排序都给出一个语法树中节点语义规则计算的有效顺序。

6.1.5. 属性文法的计算顺序

• 基础文法用于建立输入符号串的语法分析树
• 根据语义规则建立依赖图
• 根据依赖图的拓扑排序，得到计算语义规则的顺序

输入串 → 语法树 → 依赖图 → 语义规则计算次序

例 对变量声明语句进行分析

• $T . \text{type}$ 的值为 int
• 由 $L . \text{in} = T . \text{type}$ 得到 $L . \text{in} = \text{int}$
• 由 $L \to L_1, \text{id}$，观察⑤子树
  • ⑥的 in 属性值依赖于⑤的属性值，因此⑥的 in 值为 int
  • ⑦需要引用⑤和⑥，addType 在符号表中，找到 id3 的入口，填上属性值 int
• ……

最终有

树遍历的属性计算方法

通过树遍历的方法计算属性的值

• 假设语法树已经建立，且书中已带有开始符号的继承属性和终结符的综合属性
• 以某种次序遍历语法树，直至计算出所有属性
• 深度优先，从左到右的遍历

计算思维的典型方法：递归

while (!allComputed()) {  // 如果还有未被计算的属性
    calNode(S)  // S 是开始符号
}

function calNode(n: Node) {
    // n 是一个非终结符
    if (nonTerminators.includes(n)) {
        // 假设其产生式为 N → X1 X2...Xm
        for (let i = 0; i < m; i++) {
            // Xi 是一个非终结符
            if (nonTerminators.includes(X[i])) {
                // 计算 Xi 的所有能够计算的继承属性
                calInherit(X[i])
                // 递归调用，访问子树
                calNode(X[i])
            }
        }
        // 计算 n 的所有能够计算的综合属性
        calComprehensive(n)
    }
}

while (!allComputed()) {  // 如果还有未被计算的属性
    calNode(S)  // S 是开始符号
}

function calNode(n: Node) {
    // n 是一个非终结符
    if (nonTerminators.includes(n)) {
        // 假设其产生式为 N → X1 X2...Xm
        for (let i = 0; i < m; i++) {
            // Xi 是一个非终结符
            if (nonTerminators.includes(X[i])) {
                // 计算 Xi 的所有能够计算的继承属性
                calInherit(X[i])
                // 递归调用，访问子树
                calNode(X[i])
            }
        }
        // 计算 n 的所有能够计算的综合属性
        calComprehensive(n)
    }
}

这样可能需要执行许多次。树遍历方法计算属性值最坏情况下是 $\displaystyle{ O \left( n ^{ 2 } \right) }$， 实际应用中希望语法分析的同时计算属性值，不希望构造语法分析数之后再去计算属性值，因为一遍扫描时性能最好。

一遍扫描的处理办法

在语法分析的同时计算属性值

• 与所采用的语法分析方法相关，将属性计算穿插在分析过程中

所谓语法制导翻译法，直观上说就是为文法中每个产生式配上一组语义规则，并且在语法分析的同时执行这些语义规则。

语义规则被计算的时机

• 自上而下分析，一个产生式匹配输入串成功时，执行相应的语义规则
• 自下而上分析，一个产生式被用于进行归约时，执行相应的语义规则

例 建立抽象语法树的语义规则

对于算术表达式 $\displaystyle{ a - 4 + c }$，进行一遍扫描

6.2. S-属性定义及其自底向上的计算

S-属性文法只含有综合属性，该方法在自下而上的分析器分析输入符号串的同时计算综合属性

• 分析栈中保存语法符号和有关的综合属性值
• 每当进行归约时，新的语法符号的属性值就由栈中正在归约的产生式有变符号的属性值来计算

在分析栈中增加附加域存放综合属性值

假设产生式 $A \to XYZ$ 对应的语义规则为 $A \text{.a}:=f(X \text{.x},Y \text{.y}, Z \text{.z})$

例6.5 用 SLR(1) 分析器实现算术表达式的 S-属性定义

对于给定句子 $\#3 \ast 5 + 4 \text{ n} \#$，有 SLR(1) 制导的语义翻译过程表

6.3. L-属性定义及其自顶向下的计算

按照深度优先遍历语法树，计算其所有的属性值。与 LL(1) 自上而下分析法结合

• 深度优先建立语法树
• 按照语义规则计算属性

一个属性文法称为 L-属性文法，则有：如果对以每个产生式 $A \to X_1X_2\cdots X_n$ 其每个语义规则中的每个属性，有两种情况

• 是综合属性且仅依赖于产生式中 $\displaystyle{ X _{ i } }$ 左边符号 $X_1, X_2,\cdots,X_{i-1}$ 的属性
• 是 $\displaystyle{ X _{ i } }$ 的一个继承属性且这个继承属性仅依赖于 $\displaystyle{ A }$ 的继承属性

S-属性文法一定是 L-属性文法。

翻译方案

定义 6.8 将语义动作（语义规则中的某种实现代码）放在 {} 内，并插入在文法规则右部的任何合适位置，这样的文法称为翻译方案。

例 6.7 中缀表达式翻译为后缀表达式的翻译方案

对于输入串 $\displaystyle{ 1 - 2 + 3 }$ 有

输出有 $\displaystyle{ 1 \, 2 - 3 + }$

建立翻译方案

设计翻译模式时，必须保证当某个动作引用一个属性时，它必须是有定义的

• L-属性文法本身就能保证每个动作不会引用尚未计算出来的属性

当只需要综合属性时：为每个语义规则建立一个包含赋值的动作，并把这个动作放在相应产生式右边的末尾

如果既有综合属性又有继承属性，在建立翻译模式时就必须保证：

设有文法的翻译方案

此时对句子 $\displaystyle{ ab }$ 有分析树

现在对它进行改进

此时是一个合法的翻译

消除左递归

语义动作是在相同位置上的符号被展开（匹配成功）时执行的。为了构造不带回溯的自顶向下语法分析，必须消除文法中的左递归。

当消除一个翻译模式的基本文法的左递归时同时考虑属性计算（适合带综合属性的翻译模式）

例 对加减法文法消除左递归，构造新的翻译模式

其中 $R \text{.i}$ 表示 $\displaystyle{ R }$ 前面表达式的值（继承属性），$R \text{.s}$ 表示分析完 $\displaystyle{ R }$ 时子表达式的值（综合属性）

递归下降翻译器的设计

• 对每个非终结符 $\displaystyle{ A }$ 构造一个函数过程
• $\displaystyle{ A }$ 的属性实现为参数和变量
  • 继承属性：对 $\displaystyle{ A }$ 的每个继承属性设置为函数的一个形式参数
  • 综合属性：实现为函数的返回值
    • 若有多个综合属性，打包成作为结构或记录返回
    • 为了简单，我们假设每个非终结符只有一个综合属性
  • $\displaystyle{ A }$ 的产生式中每个文法符号的每一个属性：实现为 $\displaystyle{ A }$ 对应函数过程中的局部变量
• 按照产生式右部从左到右，对于单词符号（终结符）、非终结符、语义动作，分别实现
  • 对于带有综合属性 x 的终结符 $\displaystyle{ X }$，把 x 的值存入为 $X\text{.x}$ 设置的变量中。然后产生一个匹配 $\displaystyle{ X }$ 的调用，并继续读入下一个符号
  • 对于每个非终结符 $\displaystyle{ B }$，产生式右部带有函数调用的赋值语句 $\text{c} = B({\text{b}_1, \text{b}_2, \cdots, \text{b}_k})$，其中 $\text{b}_i$ 为 $\displaystyle{ B }$ 的继承属性设置的变量，$\text{c}$ 是 $\displaystyle{ B }$ 的综合属性设置的变量
  • 对于语义动作，把动作的代码抄进分析器中，用代表属性的变量来代替对属性的每一次引用

6.4. 自底向上计算继承属性

6.4.1. 删除翻译方案中嵌入的动作

在自顶向下语法分析时，需要消除左递归。语义动作不同的执行时机给语法分析器带来了困难。

对于加减法的文法，消除左递归后有翻译，但是其执行时机没有统一。print('+') 和 print('-') 发生在 T 归约后，R 归约前，而 print(num.val) 发生在 T 归约后最后，它们的时机不统一。

于是我们需要把所有的语义动作都放在产生式的末尾，使得语义动作的执行时机统一。

转换方法

• 加入新产生式 $M \to \varepsilon$
• 把嵌入在产生式中的每个语义动作不同的非终结符 $\displaystyle{ M }$ 代替，并把这个动作放在产生式 $M \to \varepsilon$ 末尾

6.4.2. 分析栈中的继承属性

更一般的情况下，并不都能通过 6.4.1 的方法完成继承属性的计算。

对于翻译方案

给定句子 int a,b,c 如果使用 SLR(1) 进行自底向上的分析

第 5 行当用 $L \to \text{id}$ 对第 4 行内容进行归约前，要归约的规则左部符号 $\displaystyle{ L }$ 未在分析栈中，分析栈中的语义动作就已经要引用 $\displaystyle{ L }$ 的继承属性 in 了，这就是问题所在。继承属性总是在符号之前先被计算，归约动作是在继承属性计算之后才会发生。只有发生归约，符号才会进栈。因此，符号还没进栈就需要使用它在属性栈中的继承属性。

为此，我们不能指望在对应符号 $\displaystyle{ L }$ 的属性栈中保存 L.in 这个继承属性。而事实上，对应符号 $\displaystyle{ L }$ 的属性栈中存放的是 $\displaystyle{ L }$ 的综合属性，而不是继承属性。

由于在自底向上的分析法中，所有属性都只能通过属性栈访问，因而问题变为：虽然 $\displaystyle{ L }$ 没有进栈，但属性栈中哪个符号的综合属性与 L.in 保持相等？

定义 6.9 设 $Y \text{.y}$ 是继承属性，$X \text{.s}$ 是综合属性，且有 $Y \text{.y} = X \text{.s}$（将后者赋值给前者），则称 $Y \text{.y} = X \text{.s}$ 为复写规则。

$X \text{.s}$ 是已经计算出来的综合属性，放在属性栈中，依据此规则，可在需要 $Y \text{.y}$ 处引用 $X \text{.s}$

对于上表，由于有 $L \text{.in} = T \text{.type}$，可以在需要 $L \text{.in}$ 处引用 $T \text{.type}$，只要能够正确找出综合属性 $T \text{.type}$ 每次归约时在属性栈中的位置即可。

翻译方案在 SLR(1) 中的实现代码

6.4.3. 模拟继承属性的计算

上述继承属性是复写规则型，而且属性栈中综合属性的位置在每次归约时都是固定的。如每次使用产生式规则 $L \to \text{id}$ 归约时，综合属性位置总是固定在 val[top-1] 处。而每次使用产生式规则 $L \to L_1, \text{id}$ 时，综合属性的位置固定在 val[top-3] 处。

但综合属性的位置不可能总是这样固定的，因此需要改造文法，使得综合属性的位置固定。

例 设有文法 $\displaystyle{ G }$

继承属性 C.i 通过复写规则继承综合属性 A.s 的值。当用 $C \to c$ 归约时，C.i 值对应的 A.s 可能在 val[top-1]（按 $S \to aAC$ 推导），也可能在 val[top-2]（按 $S \to bABC$ 推导）

文法改造为

M.i 继承属性是复写规则型继承 A.s，每次用 $M \to \varepsilon$ 归约时，M.i 中对应的 A.s 总是处于 val[top-1] 处（$M \to \varepsilon$ 右部是空的，归约之前 top 指向 B），这样 $\displaystyle{ M }$ 的综合属性 M.s 通过 M.i 这个继承属性间接的得到了 A.s 的值（M.s=M.i）

除了位置不固定的情形外，还有可能继承属性不是复写规则型

如对 $S \to aAC$ 的语义规则 $C \text{.i} = f(A \text{.s})$，其继承属性 C.i 不是复写型，而是对 A.s 计算后再赋值，这时必须将计算部分改造成综合属性方式来计算：

这样当用 $N \to \varepsilon$ 归约时，继承属性 N.i 对应综合属性 A.s 总是处于 val[top] 处（$N \to \varepsilon$ 右部为空，归约之前 top 指向 A）。当用 $C \to c$ 归约时，C.i 对应的综合属性 N.s 总在 val[top-1] 处。