第5章语法制导翻译

导读

语法制导翻译（Syntax-Directed Translation, SDT）是将语法分析与语义处理紧密结合的一种编译技术。在前面的章节中，我们已经初步接触了这个概念——在语法分析的过程中，当我们识别出某个语法结构时，就执行相应的语义动作。本章将系统地深入地探讨这一技术。

语法制导翻译的核心思想是：将语义规则"绑定"到文法的产生式上。当语法分析器识别出某个产生式时，就自动执行与之关联的语义动作。这些语义动作可以包括：类型检查、中间代码生成、符号表操作、错误报告等。

本章将介绍两种主要的语法制导翻译形式：属性文法（Attribute Grammar）和翻译方案（Translation Scheme）。我们将学习如何定义属性、如何计算属性值、如何将翻译方案嵌入到语法分析过程中，以及如何处理属性的依赖关系。

通过本章的学习，你将理解编译器是如何在分析语法结构的同时完成语义处理的，你将掌握设计语法制导翻译方案的方法，你也将了解属性计算中的依赖分析和求值顺序问题。

核心概念详解

5.1 属性文法

属性文法（Attribute Grammar）是上下文无关文法的扩展。它为文法的每个符号（终结符和非终结符）关联一组属性，并为每个产生式关联一组属性计算规则。

属性的分类：

综合属性（Synthesized Attribute）：

- 节点的综合属性值由其子节点的属性值计算得出

- 信息从子节点流向父节点（自底向上）

- 例如：表达式节点的 type 属性由其操作数的类型决定

继承属性（Inherited Attribute）：

- 节点的继承属性值由其父节点或兄弟节点的属性值计算得出

- 信息从父节点或兄弟节点流向当前节点（自顶向下或横向）

- 例如：声明中变量的类型信息从类型说明符传递给变量名

形式化定义：

一个属性文法 AG = (G, A, R) 包括：

G：基础文法（上下文无关文法）
A：属性集合。对每个文法符号 X，有 A(X) = {a₁, a₂, ...}
R：规则集合。对每个产生式 p: A → XYZ，有一组规则计算 A, X, Y, Z 的属性

示例：表达式求值的属性文法

文法:
E → E + T | T
T → T * F | F
F → ( E ) | num

属性:
E.val, T.val, F.val, num.val (都是综合属性)

规则:
E → E₁ + T    { E.val = E₁.val + T.val }
E → T         { E.val = T.val }
T → T₁ * F    { T.val = T₁.val * F.val }
T → F         { T.val = F.val }
F → ( E )     { F.val = E.val }
F → num       { F.val = num.val }

5.2 S-属性文法与L-属性文法

S-属性文法（S-Attributed Grammar）：只包含综合属性的属性文法。

S-属性文法的优点：

属性计算可以在自底向上的语法分析过程中完成
不需要关心属性的依赖顺序（综合属性总是自底向上计算）
实现简单，适合LR分析器

L-属性文法（L-Attributed Grammar）：允许继承属性，但限制继承属性的依赖方向。

对于产生式 A → X₁X₂...Xₙ，Xⱼ 的继承属性只能依赖于：

A 的继承属性

X₁, X₂, ..., Xⱼ₋₁ 的属性（即左边符号的属性）

Xⱼ 本身的综合属性（不能依赖右边符号的属性）

"L"代表"Left-to-right"，表示属性信息只能从左向右传递。

L-属性文法的优点：

可以在自顶向下或自底向上的分析过程中计算
比S-属性文法更灵活，可以描述更多的语义
大多数实际语言的语义可以用L-属性文法描述

5.3 依赖图

依赖图（Dependency Graph）描述了属性之间的计算依赖关系。

对于给定的语法树和属性文法，依赖图的构造如下：

节点：语法树中每个节点的每个属性
边：如果属性b的值依赖于属性c的值，则有一条从c到b的有向边

依赖图的作用：

确定属性的计算顺序（拓扑排序）

检测循环依赖（如果依赖图有环，则属性无法计算）

示例：

对于表达式 3 + 5 * 6，语法树为：

E(val=33)
     / | \
  E(3) + T(30)
          / | \
       T(5) * F(6)

依赖图：

F.val → T.val → E.val (右子树)
E₁.val → E.val (左子树到根)

5.4 属性计算顺序

属性的计算顺序由依赖图的拓扑排序决定。

拓扑排序算法：

function topological_sort(dependency_graph):
    in_degree = 计算每个节点的入度
    queue = 所有入度为0的节点
    
    while queue 不为空:
        node = queue.dequeue()
        output node
        
        for each neighbor of node:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.enqueue(neighbor)
    
    if output 包含所有节点:
        return output  // 拓扑排序成功
    else:
        return "存在循环依赖"  // 依赖图有环

S-属性文法的计算顺序：

对于S-属性文法，由于只有综合属性，依赖图总是无环的。计算顺序就是语法树的后序遍历（先计算子节点的属性，再计算父节点的属性）。

L-属性文法的计算顺序：

L-属性文法允许继承属性，但通过限制依赖方向来保证无环性。在自顶向下的分析过程中，可以在访问每个节点时计算其继承属性；在自底向上的分析过程中，需要更复杂的策略。

5.5 翻译方案

翻译方案（Translation Scheme）是语法制导翻译的实现形式。它将语义动作嵌入到产生式的右部，指明何时执行这些动作。

翻译方案的表示：

产生式 → { 语义动作 }

例如：

E → E + T { print("+") }
E → T
T → T * F { print("*") }
T → F
F → ( E )
F → num { print(num.value) }

对于输入 3 + 5 * 6，输出为 3 5 6 * +（后缀表示）。

5.6 翻译方案的设计

设计翻译方案时需要考虑以下问题：

1. 动作的位置

语义动作可以放在产生式右部的任何位置。动作的执行时机取决于它在产生式右部的位置：

A → X { action₁ } Y { action₂ } Z { action₃ }

action₁ 在X被识别后、Y被识别前执行
action₂ 在Y被识别后、Z被识别前执行
action₃ 在Z被识别后执行（即A被归约时）

2. 动作中引用的值

语义动作可以引用：

产生式右部符号的属性：如 X.attr
产生式左部符号的属性：如 A.attr
全局变量（如符号表）

3. 副作用

语义动作可以有副作用，如：

修改符号表
生成中间代码
输出错误信息
打印结果

5.7 将翻译方案嵌入递归下降分析

对于LL文法，可以将翻译方案直接嵌入到递归下降分析器中。

示例：简单计算器的递归下降实现

python

class Calculator:
    def __init__(self, text):
        self.lexer = Lexer(text)
        self.current_token = self.lexer.get_next_token()

    def eat(self, token_type):
        if self.current_token.type == token_type:
            self.current_token = self.lexer.get_next_token()
        else:
            raise Exception('语法错误')

    def factor(self):
        if self.current_token.type == 'NUM':
            value = self.current_token.value
            self.eat('NUM')
            return value
        elif self.current_token.type == 'LPAREN':
            self.eat('LPAREN')
            value = self.expr()
            self.eat('RPAREN')
            return value

    def term(self):
        result = self.factor()
        while self.current_token.type in ('TIMES', 'DIV'):
            if self.current_token.type == 'TIMES':
                self.eat('TIMES')
                result *= self.factor()
            elif self.current_token.type == 'DIV':
                self.eat('DIV')
                result /= self.factor()
        return result

    def expr(self):
        result = self.term()
        while self.current_token.type in ('PLUS', 'MINUS'):
            if self.current_token.type == 'PLUS':
                self.eat('PLUS')
                result += self.term()
            elif self.current_token.type == 'MINUS':
                self.eat('MINUS')
                result -= self.term()
        return result

5.8 将翻译方案嵌入LR分析

对于LR文法，翻译方案的嵌入更加复杂，因为LR分析是自底向上的。

S-属性文法的LR实现：

对于S-属性文法，综合属性的计算可以在归约时完成。在LR分析器的栈中，每个状态都关联着对应符号的属性值。

栈状态:  ... s₀ s₁ s₂ s₃
栈符号:  ... E  +  T
属性值:  ... E.val + T.val

当归约 E → E + T 时:
E.val = E₁.val + T.val

L-属性文法的LR实现：

L-属性文法在LR分析中的实现更复杂，因为继承属性需要在归约之前计算。常用的方法包括：

预测归约（Predictive Reduction）：在移入时计算继承属性

转换翻译方案：将L-属性文法转换为等价的S-属性文法

使用标记非终结符：在产生式中插入标记来延迟计算

5.9 抽象语法树的构建

语法制导翻译的一个重要应用是构建抽象语法树（AST）。

AST构建的翻译方案：

E → E₁ + T    { E.node = new Node('+', E₁.node, T.node) }
E → T         { E.node = T.node }
T → T₁ * F    { T.node = new Node('*', T₁.node, F.node) }
T → F         { T.node = F.node }
F → ( E )     { F.node = E.node }
F → num       { F.node = new Leaf(num, num.value) }

这里 node 是综合属性，表示对应子树的根节点。

AST节点的定义：

python

class ASTNode:
    pass

class BinOpNode(ASTNode):
    def __init__(self, op, left, right):
        self.op = op
        self.left = left
        self.right = right

class NumNode(ASTNode):
    def __init__(self, value):
        self.value = value

重要知识点

5.10 类型检查的语法制导翻译

类型检查是语法制导翻译的典型应用。

简单类型检查的翻译方案：

声明:
D → T id          { add_type(id.entry, T.type);
                     D.type = T.type }
T → int           { T.type = integer }
T → float         { T.type = float }
T → array num of T₁ { T.type = array(T₁.type);
                       T.width = T₁.width * num.value }
T → ^ T₁          { T.type = pointer(T₁.type);
                     T.width = 8 }

表达式:
E → id            { E.type = lookup(id.entry);
                     E.addr = id.entry }
E → num           { E.type = integer;
                     E.addr = num.value }
E → E₁ + E₂       { if E₁.type == integer and E₂.type == integer:
                       E.type = integer
                     elif E₁.type == float or E₂.type == float:
                       E.type = float
                     else:
                       error("类型不匹配") }

5.11 中间代码生成的语法制导翻译

语法制导翻译也用于生成中间代码（如三地址码）。

三地址码生成的翻译方案：

E → E₁ + T    { E.addr = newtemp();
                 gen(E.addr '=' E₁.addr '+' T.addr) }
E → T         { E.addr = T.addr }
T → T₁ * F    { T.addr = newtemp();
                 gen(T.addr '=' T₁.addr '*' F.addr) }
T → F         { T.addr = F.addr }
F → ( E )     { F.addr = E.addr }
F → id        { F.addr = id.entry }
F → num       { F.addr = num.value }

对于表达式 a + b * c，生成的三地址码：

t1 = b * c
t2 = a + t1

5.12 自顶向下翻译中的继承属性

在自顶向下翻译（如递归下降）中，继承属性可以自然地通过参数传递来实现。

示例：声明处理中的继承属性

D → T id ; D    { T.type 是继承属性，传递给 id }

递归下降实现:
def parse_D(inherited_type):
    # 处理 T id ;
    name = consume_id()
    symbol_table.add(name, inherited_type)
    consume(';')
    # 处理 D（如果有）
    if lookahead_is_declaration():
        next_type = parse_T()
        parse_D(next_type)

这里 inherited_type 是从父节点传递下来的继承属性。

5.13 翻译方案的消除左递归

对于自顶向下的分析方法，需要消除文法的左递归。但消除左递归后，翻译方案中的动作位置可能需要调整。

原始左递归文法：

E → E + T { print("+") }
E → T

消除左递归后：

E → T E'
E' → + T E' { print("+") }
E' → ε

注意：动作的位置从 E + T 之后移到了 + T E' 之后，以保证输出顺序不变。

常见误区

误区一：综合属性和继承属性可以随意使用

综合属性和继承属性不能随意混合使用。如果同时使用两者，可能导致循环依赖。L-属性文法通过限制继承属性的依赖方向来避免这个问题。

误区二：语法制导翻译只能在语法分析时完成

虽然语法制导翻译通常在语法分析过程中执行，但也可以分阶段进行。例如，先构建AST，然后在AST遍历过程中执行语义处理。这种方式更灵活，但需要额外的遍历开销。

误区三：所有语义都可以用语法制导翻译描述

语法制导翻译适合描述上下文无关的语义（如类型检查、代码生成）。但对于上下文敏感的语义（如变量声明后使用、数组边界检查），需要结合符号表等机制。

误区四：翻译方案的动作可以放在任何位置

语义动作的位置不是任意的。它必须在所有依赖的属性都已计算之后执行。对于综合属性，动作通常在归约时执行；对于继承属性，动作通常在展开时执行。

实践应用

5.14 实际应用中的语法制导翻译

类型系统实现：

Java编译器使用语法制导翻译进行类型检查
Haskell编译器的类型推断基于属性文法
TypeScript的类型系统可以用属性文法描述

代码生成：

GCC的中间代码生成使用语法制导翻译
LLVM IR的生成也基于类似技术
JVM字节码的生成使用翻译方案

文档处理：

LaTeX的宏展开可以看作语法制导翻译
Markdown到HTML的转换
模板引擎的处理

查询语言：

SQL查询的语义检查和优化
XPath表达式的求值
JSONPath的处理

5.15 属性文法的自动推导

现代编译器研究中，属性文法的自动推导是一个活跃的研究方向：

属性依赖分析：自动分析属性之间的依赖关系

属性求值顺序优化：寻找最优的属性计算顺序

增量属性求值：当输入变化时，只重新计算受影响的属性

属性文法的并行求值：利用依赖关系进行并行计算

本章小结

本章系统地介绍了语法制导翻译的理论和实践。核心内容包括：

属性文法：为文法符号关联属性，用规则描述属性计算。分为综合属性和继承属性两类。

S-属性文法与L-属性文法：S-属性文法只有综合属性，适合自底向上分析；L-属性文法允许继承属性，但限制依赖方向。

依赖图与计算顺序：属性的计算顺序由依赖图的拓扑排序决定，必须保证无环。

翻译方案：将语义动作嵌入产生式，指明动作的执行时机。可以嵌入到递归下降或LR分析器中。

实际应用：类型检查、中间代码生成、AST构建等都是语法制导翻译的典型应用。

语法制导翻译是连接语法分析和语义处理的桥梁，是编译器设计中不可或缺的技术。

第5章 语法制导翻译

导读