第8章：编译正确性与实验

分阶段验证

扫描器可核对 token 与位置，解析器可核对 AST 结构，语义检查可验证错误程序是否被拒绝，IR 变换可检查支配和类型等不变量，最终代码则需要与源语义比较。

“能汇编并运行”只说明目标程序语法合法且一次执行未失败，不证明翻译正确。优化编译器尤其需要验证边界输入、控制流合流、别名和异常。

一个小语言可以先实现解释器作为语义基准，再把同一程序编译运行，比较结果和可见输出。随机生成程序时要控制终止性，或设置明确资源限制，并排除未定义行为，避免把语言未作保证的现象误报为编译错误。

例如测试整数加法时，明确使用数学整数、模 $2^w$ 整数，还是可能溢出的有符号类型。参考解释器与目标必须采用同一种规则。

对常量折叠 3+4→7，证明主要是运算语义一致。对死存储删除，需要证明该写入在所有相关执行中都不会被观察。对循环向量化，还需证明跨迭代依赖、边界和异常处理满足条件。

翻译验证在每次编译后检查具体输入输出是否保持语义，与证明整个编译器实现对所有输入正确不同。二者可互补，但各有可验证的范围和成本。

实现支持整数、变量、if、while 和函数调用的小语言：先明确整数与调用规则，再完成扫描、解析、绑定和类型检查；生成可解释的三地址 IR；最后加入一种目标代码生成。

在未优化版本正确后加入常量传播和死代码删除。每个变换前后运行同一组程序，覆盖循环零次执行、嵌套分支、变量遮蔽、跨调用存活值和溢出边界。

性能实验应固定输入并验证输出。报告编译时间、代码大小和运行时间，避免只用一个循环得出普遍优化结论。