语法制导的语义计算基础¶

1 概述¶

1.1 基本思想¶

编译程序中的"前端"(Front End) 过程：

字符流形式的源程序 → 词法分析 → 单词流形式的源程序 → 语法分析 → 语法树 → 语义分析 → 中间代码

同时伴随 符号表管理（Symbol Table）。

1.2 本讲导引¶

语法制导的（Syntax-Directed）语义计算：

• 以语法定义（上下文无关文法）为基础
• 用于各种语义分析与翻译过程：静态语义检查，中间代码（甚至目标代码）生成等
• 用于语义计算规则及计算过程的定义
• 用于自动构造工具的设计（如 Yacc）

原理与方法：

• 属性文法（Attribute Grammar）：侧重于语义计算 规则 的定义
• 翻译模式（Translation Scheme）：侧重于语义计算 过程 的定义

1.3 属性文法举例¶

识别语言 \(L = \{ a^n b^n c^n \mid n \geq 1 \}\)¶

识别语言 \(L = \{ a^i b^j c^k \mid i,j,k \geq 1 \}\)（不含限定条件，但显示 \(a^n b^n c^n\) 是合法的）¶

另一种设计（含继承属性）¶

1.4 翻译模式举例¶

2 属性文法¶

2.1 概念¶

2.2 两种属性：综合属性和继承属性¶

2.3 属性文法举例¶

仅含综合属性的例子（开始符号 S）¶

注：d.lexval 是词法分析程序确定的属性值。

表达式 3*(5+4) 的分析树（综合属性代表自下而上传递的信息）：

含继承属性的例子（开始符号 S）¶

其中 A.num，B.num 和 C.num 是 综合属性，而 B.in_num 和 C.in_num 是 继承属性。

更复杂的例子（开始符号 N，二进制无符号小数转十进制）¶

3 基于属性文法的语义计算¶

3.1 计算方法¶

计算方法分两类：

• 树遍历方法：通过遍历分析树进行属性计算
• 单遍的方法：语法分析遍的同时进行属性计算

3.2 基于树遍历方法的语义计算¶

for 分析树中每一个结点 n do
    for 结点 n 所用产生式的每个语义规则中涉及的每一个属性 a do
        为 a 在依赖图中建立一个结点;
    for 结点 n 所用产生式中每个形如 f(c1,c2,...ck) 的语义规则 do
        为该规则在依赖图中也建立一个结点（称为虚结点）;
for 分析树中每一个结点 n do
    for 结点 n 所用产生式对应的每个语义规则 b:=f(c1,c2,...ck) do
        这里可以只是：f(c1,c2,...ck)，b 对应虚节点）
        for i := 1 to k do
            从 ci 结点到 b 结点构造一条有向边

3.3 基于树遍历的计算方法举例¶

设有如下属性文法（二进制小数转十进制），考虑输入串 10.01 的语义计算过程。

步骤一： 构造输入串 10.01 的语法分析树

步骤二： 为分析树中所有结点的每个属性建立依赖图中的结点，并给定标记序号

步骤三： 根据语义动作，建立依赖图中的有向边

步骤四： 依赖图无圈，存在拓扑排序。一种可能的计算次序：

步骤五： 依计算次序，根据语义动作求出各结点对应的属性值

3.4 带标注的语法分析树¶

语法分析树中各结点属性值的计算过程被称为对语法分析树的 标注（annotating）或 修饰（decorating），用带标注的语法分析树表示属性值的计算结果：

3.5 单遍的方法¶

语法分析遍的同时进行属性计算：

• 自下而上方法
• 自上而下方法

只适用于特定的属性文法，本课程讨论如下两类：

3.6 S-属性文法的语义计算¶

S-属性文法通常采用 自下而上 的方式进行。若采用 LR 分析技术，可以通过扩充分析栈中的域，形成 语义栈 来存放综合属性的值，计算相应产生式左部文法符号的综合属性值刚好发生在每一步归约之前的时刻。

语义动作中的综合属性可以通过存在于当前语义栈栈顶部分的属性进行计算。例如，假设有相应于产生式 \(A \to XYZ\) 的语义规则 A.a := f(X.x, Y.y, Z.z)，在 \(XYZ\) 归约为 \(A\) 之前，Z.z、Y.y 和 X.x 分别存放于语义栈的 top、top-1 和 top-2 的相应域中，因此 A.a 可以顺利求出。归约后，X.x、Y.y、Z.z 被弹出，而在栈顶 top 的位置上存放 A.a。

用 LR 分析技术进行 S-属性文法的语义计算举例¶

通过下列 S-属性文法 G'[S] 为常量表达式求值：

文法 G'[S] 的 LR 分析表：

LR 分析过程伴随常量 2 + 3 * 5 的求值：

3.7 L-属性文法的语义计算¶

采用自上而下的方式可以较方便地进行，可以采用下列 基于深度优先后序遍历 的算法：

procedure dfvisit(n: node);
begin
    for n 的每一孩子 m, 从左到右 do
    begin
        计算 m 的继承属性值;
        dfvisit(m)
    end;
    计算 n 的综合属性值
end

该算法与自上而下预测分析过程对应。因此，基于 LL(1) 文法的 L-属性文法可以采用这种方法进行语义计算。

采用深度优先后序遍历算法进行 L-属性文法的语义计算举例¶

考虑对于下列 L-属性文法，输入串为 .101 时的计算过程：

4 基于翻译模式的语义计算¶

4.1 翻译模式概念¶

4.2 受限的翻译模式¶

在设计翻译模式时，必须作某些限制，以确保每个属性值在被访问到的时候已经存在。本讲仅讨论两类受限的翻译模式：

4.3 翻译模式举例（定点二进制小数转十进制）¶

4.4 基于翻译模式的语义计算¶

仅考虑 单遍的方法：

• 自上而下的语义计算：借助于自上而下的预测分析技术
• 自下而上的语义计算：借助于自下而上的移进-归约分析技术

仅考虑上述受限的翻译模式。

4.5 基于翻译模式的自上而下语义计算¶

对适合于自上而下预测技术的翻译模式，语法制导的语义计算程序可以如下思路构造：

• 对每个非终结符 \(A\)，构造一个函数，以 \(A\) 的每个继承属性为形参，以 \(A\) 的综合属性为返回值。如同预测分析程序的构造，该函数代码的流程是根据当前的输入符号来决定调用哪个产生式
• 与每个产生式相关的代码根据其右端的结构来构造：
  • 对终结符 \(X\)，保存其综合属性 \(x\) 的值至专为 X.x 而声明的变量；然后调用匹配终结符（match_token）和取下一输入符号（next_token）的函数
  • 对非终结符 \(B\)，利用相应于 \(B\) 的函数 ParseB 产生赋值语句 c := B(b1, b2, ..., bk)，其中变量 \(b_1, b_2, \ldots, b_k\) 对应 \(B\) 的各继承属性，变量 \(c\) 对应 \(B\) 的综合属性
  • 对语义规则集，直接复制其中每一语义规则来产生代码，只是将对属性的访问替换为对相应变量的访问

自上而下语义计算举例¶

构造下列翻译模式的自上而下递归下降（预测）翻译程序（可以验证其基础文法为 LL(1) 文法）：

N → . { S.f := 1 } S { print(S.v) }
S → { B.f := S.f } B { S1.f := S.f + 1 } S1 { S.v := S1.v + B.v }
S → ε { S.v := 0 }
B → 0 { B.v := 0 }
B → 1 { B.v := 2^(-B.f) }

对非终结符 \(N\)，构造如下函数：

void ParseN() {
    MatchToken('.');      // 匹配 '.'
    Sf = 1;               // 变量 Sf 对应属性 S.f
    Sv = ParseS(Sf);      // 变量 Sv 对应属性 S.v
    print(Sv);
}

对非终结符 \(S\)，构造如下函数：

float ParseS(int f) {
    if (lookahead == '0' || lookahead == '1') {
        Bf = f;  Bv = ParseB(Bf);  S1f = f + 1;
        S1v = ParseS(S1f);  Sv = S1v + Bv;
    }
    else if (lookahead == '#')  Sv = 0;
    else { printf("syntax error\n"); exit(0); }
    return Sv;
}

对非终结符 \(B\)，构造如下函数：

float ParseB(int f) {
    if (lookahead == '0') { MatchToken('0'); Bv = 0; }
    else if (lookahead == '1') {
        MatchToken('1');  Bv = pow(2, -f);
    }
    else { printf("syntax error\n"); exit(0); }
    return Bv;
}

4.6 消除翻译模式中左递归的一种变换方法¶

如下是常量表达式求值的翻译模式，但含有左递归，因而不能用 LL(1) 方法：

S → E    { print(E.val) }
E → E1 + T  { E.val := E1.val + T.val }
E → T    { E.val := T.val }
T → T1 * F  { T.val := T1.val × F.val }
T → F    { T.val := F.val }
F → (E)  { F.val := E.val }
F → d    { F.val := d.lexval }

变换前后代表两种不同的计算方式（左递归 vs 右递归），但计算结果等价：

消除左递归举例¶

4.7 基于翻译模式的自下而上语义计算¶

扩展前述的关于 S-属性文法的自下而上计算技术（即在分析栈中增加存放属性值的域）。翻译模式中综合属性的求值采用前述的计算方法。

对于前述受限的翻译模式，核心问题实际上是 L-翻译模式的自下而上计算，本节仅涉及如下 3 个方面的简介：

1. 翻译模式中去掉嵌在产生式中间的语义动作
2. 分析栈中继承属性的访问及继承属性的模拟求值
3. 用综合属性代替继承属性

4.7.1 从翻译模式中去掉嵌在产生式中间的语义规则集¶

• 若语义规则集中 未关联任何属性，引入新的非终结符 \(N\) 和产生式 \(N \to \varepsilon\)，把嵌入在产生式中间的动作用非终结符 \(N\) 代替，并把该语义规则集放在产生式后面
• 若语义规则集中 有关联的属性，引入新的非终结符 \(N\) 和产生式 \(N \to \varepsilon\)，以及把该语义规则集放在产生式后面的同时，需要在适当的地方增加复写规则

4.7.2 分析栈中继承属性的访问¶

自下而上语义计算程序根据产生式 \(A \to XY\) 的归约过程中，假设 \(X\) 的综合属性 X.s 已经出现在语义栈上。因为在 \(Y\) 以下子树的任何归约之前，X.s 的值一直存在，因此它可以被 \(Y\) 继承。如果用复写规则 Y.i := X.s 来定义 \(Y\) 的继承属性 Y.i，则在需要 Y.i 时，可以使用 X.s。

4.7.3 分析栈中继承属性的访问举例¶

翻译模式：

D → T { L.in := T.type } L
T → int   { T.type := integer }
T → real  { T.type := real }
L → { L1.in := L.in } L1, v  { addtype(v.entry, L.in) }
L → v     { addtype(v.entry, L.in) }

（分析栈 val 存放文法符号的综合属性，top 为栈顶指针）

4.7.4 继承属性的模拟求值¶

分析栈中继承属性的访问是通过栈中已有文法符号的综合属性值间接进行的，因此设计翻译模式时需要做到的一点就是要保证 继承属性总可以通过某个文法符号的综合属性体现出来。必要时，通过增加新的文法符号以及相应的复写规则常常可以达到上述目的。

4.7.5 继承属性的模拟求值举例（较复杂的例子）¶

4.7.6 用综合属性代替继承属性¶

有时，改变基础文法可能避免继承属性。如下列文法可能用来描述 Pascal 式的说明语句：

D → L : T
T → int | real
L → L, v | v

因变量标识符由 \(L\) 产生而类型不在 \(L\) 的子树中，所以不能仅仅使用综合属性就把 type 与标识符联系起来。从第一个产生式来看，似乎 \(L\) 可以从它的右边 \(T\) 中继承 type，但所得到的属性文法就不是 L-属性的。

若将上例中的基础文法变为：

D → v L
L → , v L
L → : T
T → int | real

这样，类型可以通过综合属性 L.type 进行传递，当通过 \(L\) 产生每个变量标识符时，它的类型就可以填入到符号表中。