符号表
复习
- 语法树与抽象语法树：程序结构的表示
- 哈希与映射：以键索引值的抽象
- 变量与类型：名字代表数据
TL;DR
- 符号表记录程序里每个名字及其属性
- 它把名字映射到类型、种类、位置等信息
- 进入作用域时插入，离开时移除或标记
- 它是语义分析的基础设施
正文
语法分析之后，我们得到了一棵语法树。可树上的变量名，对编译器来说还只是一串字符。x 到底是整数还是字符串？是局部变量还是函数？编译器得先弄清楚这些，才能判断程序有没有意义。
用来管这些信息的“账本”，就是符号表（symbol table）。
一本名字与属性的账
符号表做的事，本质上是把名字映射到它的属性：
- 名字叫什么
- 它是什么种类（变量、函数、类型……）
- 它的类型是什么
- 它存放在哪里（内存位置等）
随着编译器扫过程序，每遇到一个名字的定义，就往表里记一笔；之后遇到这个名字的使用，就去表里查出它的属性。
你会发现，这正是一个映射（map）的典型应用：用名字当键，用属性当值。所以符号表在实现上，常常就用哈希表或树来做——正是我们在数据结构那部分学过的工具。编译器自己，也是数据结构的用武之地。
它为什么要动态变化
符号表不是一次性建好的，而是随着分析的推进不断变化：
- 进入一个作用域，往里加入该作用域里的名字
- 离开这个作用域，把它里面的名字移除（或让它们失效）
这样才能正确表达“这些名字只在这一小块代码里有效”。符号表的这种“进出”行为，和下一章的作用域紧密相关。
可以说，符号表是语义分析的第一块基石：后面所有的类型检查、名字解析，都要先有它，才能知道每个名字到底是什么。
思考题 1
符号表为什么是语义分析的基础？
思考题 2
符号表通常用什么数据结构实现？为什么？
小结
知识点
- 符号表把名字映射到类型、种类、位置等属性
- 定义时插入，使用时查询
- 它随作用域的进入与离开而动态变化
- 常用哈希表或树实现
参考资料
- Wikipedia(zh)：符号表：编译器用来记录名字属性的数据结构
- Wikipedia(zh)：哈希表：符号表的常见实现
思考题答案（仅供参考）
思考题 1
因为语义分析和类型检查必须先知道“每个名字是什么”。符号表记录了名字的种类、类型、位置等属性，后续判断名字使用是否合法、类型是否匹配，都要依赖它提供的信息，所以它是语义分析的基础。
思考题 2
常用哈希表（或树）。因为符号表的核心是“用名字快速查到属性”，这正是映射的操作；哈希表平均 O(1) 的查找很适合，需要有序时也可用树。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪