表达式的类型检查
复习
- 类型系统：用规则约束合法操作
- 语法树与抽象语法树：程序结构的表示
- 递归：遍历树
TL;DR
- 类型检查沿语法树自底向上进行
- 每个节点根据子节点的类型，推出自己的类型
- 类型不匹配就报错
- 它是编译器在编译期抓住错误的关键一步
正文
有了类型系统，具体怎么检查？最自然的做法，就是沿着语法树递归地走一遍。
自底向上推类型
一个表达式树的叶子是变量和常量，它们各自有明确的类型；内部节点是运算，比如加、乘。检查时：
- 先算出子节点的类型
- 再看当前这个运算，是否允许这些类型的操作数
- 允许，就得出当前节点的结果类型；不允许，就报类型错误
因为要先知道孩子的类型，才能判断自己，所以这个过程是自底向上的。用递归来实现，非常自然。
举个例子，检查 a + b：
- 查出
a是整数，b也是整数 - 加法规则：整数 + 整数 = 整数，成立
- 于是整个表达式是整数
不匹配就当场报错
如果换成 1 + "x"：
- 左边是整数，右边是字符串
- 加法规则里没有“整数 + 字符串”这一条
- 于是编译器当场报类型错误，指出这一处不合法
这就是静态类型检查的价值：程序还没运行，编译器就已经发现这行代码“讲不通”。 用户不必等到程序真跑到这里、崩在运行时，才意识到写错了。
它依赖前面所有成果
类型检查看起来只是在树上走一遍，其实它站在前面许多工作的肩膀上：
- 要有语法树，才知道结构
- 要有符号表和名字解析，才知道每个变量是什么类型
- 要有类型系统的规则，才知道哪些组合合法
可以说，类型检查是语义分析的核心动作，把前面几章的铺垫都用上了。而表达式只是开始——函数调用、控制流同样要检查。下一章继续。
思考题 1
类型检查为什么适合沿语法树“自底向上”进行？
思考题 2
表达式
1 + "x"在类型检查阶段会怎样？
小结
知识点
- 类型检查沿语法树递归进行
- 根据子节点类型推断当前节点类型
- 规则不允许则报告类型错误
- 它依赖语法树、符号表与类型规则
参考资料
- Wikipedia(zh)：类型检查：验证程序是否符合类型规则
- Wikipedia(zh)：类型系统：类型检查依据的规则
思考题答案（仅供参考）
思考题 1
因为判断一个运算节点是否合法，必须先知道它各个子节点的类型。也就是说，孩子的结果要先算出来，才能算父亲，这与自底向上的顺序一致，用递归遍历语法树即可实现。
思考题 2
检查会发现左边是整数、右边是字符串，而“整数与字符串相加”不在允许的规则里，因此编译器会报告一个类型错误，指出该表达式不合法。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪