第4章符号表与名字解析

符号表与名字解析：编译器的“通讯录”

说实话，符号表这东西，我第一次接触时觉得它就是个“变量名→地址”的映射表。后来在做一个自研脚本语言时，被一个作用域泄漏的bug折磨了三天，才真正明白——符号表是编译器的中枢神经系统。它连接着前端解析和后端代码生成，设计得好，编译效率翻倍；设计得烂，查个变量名都能卡半天。

符号表的核心设计：哈希表 vs 树结构

符号表到底用什么数据结构？我个人的经验是：没有银弹。你得根据语言特性来选。

哈希表方案

大多数通用语言（C、Java、Python）的编译器都用哈希表。为什么？因为快。平均O(1)的查找时间，对于频繁的名字解析来说太香了。

哈希表的核心设计要点：

哈希函数：要均匀分布，避免冲突。我见过有人直接用字符串长度做哈希，结果一堆同名不同作用域的变量全撞在一起，惨不忍睹。
冲突解决：链地址法最常见。但要注意，链太长会退化成O(n)。
动态扩容：符号表会随着编译过程不断插入新符号。负载因子超过0.75就该扩容了，否则性能雪崩。

// 一个简化的哈希表符号表实现（C风格伪代码）
typedef struct Symbol {
    char* name;
    int type;
    int scope_level;
    struct Symbol* next;  // 链地址法
} Symbol;

typedef struct {
    Symbol** buckets;
    int size;
    int count;
} SymbolTable;

Symbol* lookup(SymbolTable* st, const char* name) {
    int idx = hash(name) % st->size;
    Symbol* cur = st->buckets[idx];
    while (cur) {
        if (strcmp(cur->name, name) == 0) {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;  // 没找到
}

我的小技巧：哈希表的大小选质数，能显著减少冲突。比如选1021而不是1024。这是我在一次性能调优时发现的，效果立竿见影。

树结构方案

树结构（特别是二叉搜索树或平衡树）在符号表里用得少一些，但某些场景下它比哈希表更合适。

有序遍历：如果你需要按名字顺序输出符号表（比如调试信息），树结构天然支持。
范围查询：某些语言支持“查询某个前缀的所有符号”，树结构可以高效实现。
内存紧凑：哈希表有额外的桶数组和链表指针，树结构相对更省内存。

但说实话，我很少用纯树结构做符号表。因为大多数编译场景下，我们不需要有序性，哈希表的性能优势太明显了。除非你在做某种特殊语言——比如我参与过一个数据库查询语言的编译器，需要频繁做“查找所有以‘tmp_’开头的临时变量”，这时候树结构就派上用场了。

作用域与可见性：变量不是你想见就能见

作用域，说白了就是一个名字在多大范围内有效。你想想看，如果全局变量和局部变量都叫i，编译器怎么知道你说的是哪个？

静态作用域（词法作用域）

大多数语言都用静态作用域。什么意思？就是在编译时就能确定一个名字绑定到哪个声明，不需要等到运行时。

int x = 10;  // 全局作用域

void foo() {
    int x = 20;  // 局部作用域，遮蔽了全局的x
    printf("%d", x);  // 输出20
}

这里有个关键点：作用域嵌套。内层作用域可以访问外层作用域的变量，但反过来不行。我在项目中遇到过一个问题：一个实习生在内层作用域里声明了一个和外层同名的变量，然后在外层想用这个变量，结果编译报错。嗯，这就是作用域遮蔽（shadowing）的典型坑。

我曾经踩过的坑：在实现C语言编译器时，我忘了处理“块作用域”（比如if语句里的大括号）。结果用户写if (1) { int a = 5; } printf("%d", a);，编译器居然没报错。后来查了半天，发现是符号表在退出块作用域时没有正确弹出作用域栈。从那以后，我每次实现作用域都会画一个栈的示意图。

动态作用域

有些语言（比如早期的Lisp、Bash）用动态作用域。名字的绑定在运行时由调用链决定。这听起来很灵活，但实际用起来容易让人抓狂。

// 伪代码：动态作用域示例
x = 1;
function foo() { print(x); }
function bar() { x = 2; foo(); }
bar();  // 输出2，而不是1！

为什么会这样？因为foo里的x不是在定义时绑定的，而是在调用时沿着调用栈往上找。我个人不太喜欢动态作用域——它让代码的静态分析变得几乎不可能，调试起来也像在迷宫里转。

编译时名字解析 vs 运行时动态查找

这是编译器设计里一个非常核心的权衡：能编译时做的事，绝不拖到运行时。

编译时名字解析

对于静态作用域的语言，大部分名字解析在编译时就完成了。编译器遍历AST，遇到一个名字就查符号表，找到对应的声明，然后记录下它的地址或偏移量。

优点：快！运行时不需要任何查找开销。
缺点：不够灵活。不支持动态加载、热更新等特性。

运行时动态查找

动态语言（Python、JavaScript、Ruby）的名字解析很多是在运行时做的。比如Python里的eval()、getattr()，或者JavaScript里的with语句。

# Python运行时动态查找
class Dynamic:
    def __getattr__(self, name):
        if name == "magic":
            return 42
        raise AttributeError

obj = Dynamic()
print(obj.magic)  # 运行时才决定返回42

这种灵活性是有代价的——每次访问属性都要做一次查找。我记得有一次优化一个Python项目，发现__getattr__被调用了上百万次，性能直接崩了。后来改成在初始化时把所有属性绑定好，速度提升了10倍。

我的建议：在设计编译器时，尽量把名字解析往编译时推。如果一定要支持运行时动态查找，那就加一个缓存层。比如JavaScript引擎的“内联缓存”（Inline Cache）技术，就是用来加速运行时属性查找的。

知识体系总览

下面这张图是我自己整理的符号表与名字解析的知识结构，你可以把它当作本章的“地图”：

总结一下

符号表设计没有标准答案，但有几个原则我建议你记住：

哈希表是默认选择，除非你有特殊需求（有序遍历、范围查询）。
作用域用栈管理，进入新作用域压栈，退出时弹栈。注意处理遮蔽和嵌套。
编译时解析优先，运行时动态查找作为补充。如果必须用动态查找，加缓存。
别忘了错误处理——符号未定义、重复定义、作用域越界，这些都要给出清晰的错误信息。

嗯，符号表这块内容其实挺深的。我当年第一次实现时，觉得不就是个查表吗？结果被作用域嵌套、函数重载、模板实例化这些特性搞得焦头烂额。但正是这些坑，让我真正理解了编译器设计的精妙之处。

📚 课程目录

符号表与名字解析：编译器的“通讯录”

符号表的核心设计：哈希表 vs 树结构

哈希表方案

树结构方案

作用域与可见性：变量不是你想见就能见

静态作用域（词法作用域）

动态作用域

编译时名字解析 vs 运行时动态查找

编译时名字解析

运行时动态查找

知识体系总览

总结一下