符号表与作用域

编译器的"联系人":把每个标识符关联到它的定义——从词法作用域的栈式查找到闭包捕获标记、从模块导入到泛型单态化,所有语义分析都从这张表开始。

概述

语义分析的第一件事不是类型检查,是名字解析(name resolution)——把源码里的每个标识符(变量名、函数名、类型名)关联到它的定义。符号表(symbol table)是做这件事的数据结构。它看着简单(存名字→信息的映射),但作用域规则(scope rules)加进来后,符号表的设计直接影响编译器的正确性和效率——闭包捕获、模块导入、泛型特化、重载解析,每一项都在符号表上施加不同的操作要求。

符号表的基本操作

任何符号表必须高效支持两个核心操作:

此外还有:

• enter_scope() / exit_scope():进入/离开一个词法作用域
• lookup_current(name):只在当前作用域查(用于检测重复定义)

复杂度极其关键:insert 和 lookup 在编译器的名字解析阶段被调用海量次,必须是 O(1) 或近 O(1)。

栈式符号表:词法作用域的原生映射

源码的作用域天然是嵌套的(大括号套大括号),用栈式符号表直接对应:

struct Scope {
    symbols: HashMap<String, SymbolInfo>,   ← 本作用域的名字
    parent: u32,                            ← 外层作用域索引
}

symbol_table: Vec<Scope>   ← 栈, 当前作用域在栈顶

enter_scope():  push 新 Scope {parent: 当前栈顶索引}
exit_scope():   pop

lookup(name):
    scope = 栈顶
    while scope != nil:
        if name in scope.symbols:
            return scope.symbols[name]
        scope = scope.parent              ← 沿 parent 链向外找
    return NOT_FOUND

• insert:只往当前作用域(栈顶)写。
• lookup:从栈顶沿 parent 链往外,第一次命中就是最近的定义(符合"内层覆盖外层"的词法作用域规则)。
• 复杂度:insert O(1); lookup O(depth), depth 通常是常数(嵌套不会太深)。

这就是绝大多数编译器的实现方式——Clang、Rust 的部分 pass、C/C++ 编译器都在用这个模式。

为什么不用单个全局哈希表

单个哈希表 HashMap<String, Vec<SymbolInfo>> 也可以,但 exit_scope() 时要遍历删除本作用域的所有插入——不如栈式直接 pop 一个 Scope 干净。

模块与命名空间:二级查找

当语言有模块/命名空间时("引入另一个文件里的名字"),符号表需要跨越"当前文件→当前模块→导入的模块"做查找:

lookup(name, current_module):
    result = lookup_local(name)                   ← 1. 当前作用域链
    if result: return result
    result = lookup_imported(name, current_module) ← 2. 导入的其他模块的公开符号
    if result: return result
    return lookup_global(name)                    ← 3. 全局(如内置类型/函数)

模块系统在符号表上引入了可见性(visibility):

• public:该名字对导入方可见
• private:只在当前模块内可见

符号表在处理模块导入时,只把被导入模块的 public 符号插入当前作用域链(或单独维护一个"导入符号"列表)。Rust 编译器在 resolve 阶段就是把 use 语句的导入符号展开到符号表里。

闭包捕获:从作用域链到"逃逸"的名字

当语言有闭包(closure)时,闭包体可能引用了外部作用域的变量——这些变量在外部作用域 exit_scope() 后仍然需要被访问:

fn outer():
    x = 10
    return fn inner():       ← inner 捕获了 x
        return x + 1         ← x 在 outer 的作用域里, 但 inner 作为返回值逃逸

符号表处理闭包捕获的过程:

1. 进入 inner 作用域时,lookup("x") 沿作用域链找到了 outer 里的 x。
2. 标记 x 为"被闭包捕获"——这是一个关键语义标记,后续代码生成时 x 不能分配在栈上(否则 outer 返回后栈被回收),必须堆分配或用 upvalue 机制⁠。
3. 在闭包的符号信息里记录捕获列表:[(x, by_ref_or_by_value)]。

Rust 编译器在符号解析阶段区分 Fn/FnMut/FnOnce 的捕获方式(共享引用/可变引用/转移所有权)——这些决策全部来源于符号表的捕获分析。

重载解析:lookup 不再是返回单个值

有函数重载的语言(C++、Java),同一名字在一个作用域里可能有多个定义⁠(不同参数类型)。此时 lookup 返回的不是单个符号,而是一个 overload set:

lookup("foo") → [
    foo(int, int) → int,
    foo(float, float) → float,
    foo(string, string) → string,
]

选择哪个,取决于调用时的参数类型——这已经是类型检查的范畴(在 类型系统 里讲)。符号表的职责是维护 overload set,而不是选择。

泛型与单态化:名字的多重"化身"

泛型函数 fn identity<T>(x: T) -> T 在 Rust/C++ 里会被单态化(monomorphization)——每种类型参数 T 的实际值(如 i32、String)生成一份独立的机器码。这对符号表意味着:

• 泛型定义本身是一条符号,附带类型参数列表。
• 每次实例化(identity::<i32>)产生一个新的符号表条目——但它的引用信息(捕获、依赖)从泛型模板复制。
• 符号表需要支持"实例化模板"——复制泛型定义的符号信息,替换其中的类型参数为实际类型。

Rust 编译器在 MIR 层做单态化(不是 AST 层),所以符号表在 AST→HIR→MIR 的不同阶段承载不同的粒度。

权衡与失败模式

• 单层全局表⁠:不区分作用域 → 内层名字覆盖外层无效,lookup 总返回第一个插入的同名符号 → 必须栈式。
• lookup 不走完整链⁠:某些实现为性能跳过 parent 链,直接查全局缓存 → 作用域遮蔽(shadowing)失效。
• 闭包捕获标记遗漏⁠:符号表发现捕获但没标记 → 代码生成给捕获变量分配栈空间 → 闭包调用时 use-after-free。
• 循环模块导入⁠:A 导入 B,B 导入 A → 符号表解析时死循环 → 解析阶段需要维护"正在解析的模块"集合,检测循环并报错。
• 同名不同类型⁠:函数和变量在有些语言里可以同名(不同名字空间,如 C 的 struct foo vs foo 变量) → 符号表需要分名字空间(tag namespace、object namespace、label namespace),每个名字空间独立栈式查找。

参考

• Dragon Book: Chapter 2 (symbol table) & Chapter 6 (type checking via symbol table)
• Cooper/Torczon: "Engineering a Compiler", Chapter 4 (symbol tables & scoping)
• Rust compiler source: compiler/rustc_resolve/src/ — 名字解析的工业级实现,含模块/闭包捕获/宏展开

Keywords: symbol table, stack-based symbol table, scope, name resolution, lexical scope, shadowing, module, namespace, visibility, public/private, closure capture, upvalue, overload set, overload resolution, monomorphization, generic instantiation, cyclic import, name space