从零实现一个简单编译器的三步实践法

一、先界定“简单编译器”的范围

动手之前，必须先明确目标边界，否则很容易陷入无穷无尽的特性海洋。一个适合学习的“简单编译器”通常指：

• 支持一门主流系统级语言的核心子集：基本数据类型、变量、算术与逻辑表达式、条件与循环、函数定义与调用；
• 完整走通编译流水线：源码 → 词法单元流 → 抽象语法树 → 语义检查 → 目标代码（汇编或自定义虚拟机字节码）；
• 生成代码可以被现有工具链汇编链接，或直接在自研解释器上执行。

明确边界后，工程量就从“实现一门完整语言”收敛为“实现一条流水线”，排期与心理负担都会可控很多。

二、编译器的最小工作流水线

无论目标语言多复杂，编译器内部结构大同小异，可以拆成四个环节：

1. 词法分析：把字符流切分成一个个 token，例如关键字、标识符、数字字面量、运算符。这一层只关心“词”的形状，不关心含义。
2. 语法分析：按文法规则把 token 流组织成抽象语法树（AST），缺少分号、括号不匹配等结构错误都在这一层报出。
3. 语义分析：遍历 AST，维护符号表，检查变量是否先声明后使用、类型是否匹配、函数调用参数个数是否正确等。
4. 代码生成：把语义正确的 AST 翻译为目标代码。教学实现常见两种选择：生成文本汇编交给系统工具链，或生成栈式虚拟机字节码自行解释执行。后者可控性更强，前者更贴近真实编译器。

这四个环节通过清晰的数据结构（token、AST、符号表）解耦，任何一环都可以独立替换和测试——这也是后文“小步快跑”策略能够成立的结构基础。

三、三阶段推进策略

第一阶段：以最快速度解析最小样例

不要一上来就设计周全的架构，而是先选一段足够小、又覆盖基本要素的代码作为目标：

int main(int argc, char **argv) {
    int i;
    return 0;
}

要让编译器“吃下”这段代码，至少需要：能识别关键字与标识符的词法器；能处理函数定义、参数列表、局部变量声明和 return 语句的递归下降解析器；一个最简符号表。此时甚至可以跳过语义检查和真实代码生成，只把 AST 打印出来验证解析正确性。

这一阶段的意义在于：用最小的代码量把整条流水线的骨架搭起来，让“源码进、结构出”的闭环成立。经验上，几百行代码即可达成，通常一两天就能完成。

第二阶段：以最快速度看到 hello, world

骨架搭好后，第二个里程碑不是“支持更多语法”，而是尽快让编译器产出的程序真正跑起来，打印出 hello, world。为此需要补齐：

• 字符串字面量的词法识别与存储；
• 函数调用表达式（哪怕只支持调用运行时库的输出函数）；
• 表达式求值与代码生成的最小实现；
• 与运行环境的衔接：若生成汇编，需按目标平台的调用约定传参；若走虚拟机，需实现调用外部函数的桥接。

这个里程碑的战略价值极高：它打通了“源码 → 编译 → 运行 → 观察输出”的端到端反馈回路。从此每实现一个特性，都能立刻用真实程序验证，而不是对着中间数据猜对错。编译器开发最大的风险就是“写了很久却不知道对不对”，端到端回路正是对这种风险的对冲。

第三阶段：对照语言标准逐项实现特性

前两步完成后，编译器已经“能用”，接下来进入漫长的特性补齐期。推荐做法是：

1. 以官方语言标准为清单，按章节整理特性列表，例如类型系统、整型提升、运算符优先级与结合性、控制流、作用域规则、初始化规则等，逐项实现、逐项打勾；
2. 每个特性同步编写单元测试，测试用例尽量取自标准中的示例与约束条款，保证行为有据可依；
3. 保持回归：每次改动后重跑全部历史用例，防止新特性破坏旧能力。

由于前两个阶段已经积累了完整流水线的实现经验，这一阶段虽然绝对工作量不小，但本质上是在成熟骨架上做“填空”，节奏是可预期的。

四、各环节的关键技术要点

1. 词法分析：手写优先

教学规模下建议手写词法器：逐字符扫描加最长匹配，用一个关键字表区分标识符与关键字。手写实现直观、易调试，也便于后续扩展 Unicode 支持。

2. 语法分析：递归下降 + 优先级处理

递归下降是最容易理解和实现的解析方法：每条文法规则对应一个函数。需要注意两点：文法中的左递归必须改写为循环形式，否则会无限递归；表达式解析可采用优先级爬升法，或为每个优先级写一层函数，运算符的左结合、右结合要显式处理。

3. 语义分析：作用域栈与类型检查

符号表建议实现为栈式作用域：进入复合语句压入新作用域，退出时弹出，查找时自栈顶向下。类型检查则为每个表达式维护类型，依据语言规则做隐式转换判断与报错。

4. 代码生成：先简单后优化

第一版建议生成栈式虚拟机字节码或最直白的汇编：表达式求值压栈、运算弹栈，暂不考虑寄存器分配。等正确性充分验证后，再逐步引入寄存器分配、常量折叠、死代码消除等优化。正确性永远优先于性能。

五、实现过程中容易踩的坑

1. 类型双关与严格别名规则

编译器实现中经常需要观察一个对象的另一种类型表示，初学者常写出这样的代码：

float f = 1.5f;
int i = *(int *)&f;   /* 存在隐患 */

问题在于：主流编译工具链在开启较高优化级别时，会依据“严格别名规则”假设不同类型的对象不会指向同一块内存，从而做出激进优化，上述写法可能构成未定义行为，优化后结果与预期不符。

C 语言提供的规范做法是利用 union 或内存复制：

union { float f; int i; } u = { .f = 1.5f };
int i = u.i;

进一步地，可以把 union 包进复合字面量（C11 引入的特性），封装成参数化的转换宏，一行完成“取另一种表示”，且天然可复用：

#define REINTERPRET(s_t, d_t, v) \
    (union { s_t _s; d_t _d; }){ ._s = (v) }._d

这种写法语义明确、不依赖别名假设，在高优化级别下也是安全的。

2. 浮点比较的精度陷阱

词法器解析浮点字面量、测试用例构造循环边界时，都要警惕浮点误差。例如用 0.1f 做累减步长，终止条件可能因累积误差多算或少算一轮。规则是：避免用相等判断直接比较浮点数，应使用带容差的比较，或在整数域完成计数。

3. 源码编码与标识符

现代语言标准普遍允许标识符中出现 Unicode 字符，这意味着理论上可以写出全中文标识符的程序，例如 int 变量 = 1;。实现层面要注意：统一源码编码为 UTF-8；词法器按字节读取时需正确处理多字节序列，把合法的 Unicode 字符序列识别为标识符的一部分；诊断信息输出也按同一编码处理，避免乱码。

4. 错误处理与诊断质量

编译器的使用体验很大程度取决于报错质量。建议从早期就统一错误结构（位置、级别、消息），支持“报出一个错后尽量继续解析”的错误恢复，而不是发现第一个错就终止。这对后续测试同样大有裨益。

六、测试体系：从单元到快照

• 单元测试：针对词法器、解析器、类型检查各自编写，输入片段、断言输出结构；
• 快照测试（端到端）：准备大量“源程序 + 期望运行输出”的用例对，编译、运行、比对，一条命令回归全部；
• 对照验证：条件允许时，可将同一程序交给成熟的现有实现编译运行，比对行为差异，作为发现标准理解偏差的手段。

测试用例的组织方式与第三阶段的特性清单保持一致：标准的一个条款对应一组用例，实现到哪、测试覆盖到哪，进度一目了然。

七、总结

写一个简单编译器，最怕两种失败模式：一是追求大而全，迟迟看不到程序跑起来，热情耗尽；二是只堆语法不建测试，代码越长越不敢改。本文给出的三步法正是针对这两点：先用最小样例搭起流水线骨架，再尽快建立端到端反馈回路，最后以语言标准为纲、以单元测试为盾，稳步扩展特性。照此路径推进，编译器开发会从“高不可攀”变成一系列清晰可控的小里程碑，而你对语言、运行时与机器底层的理解，也会在这个过程中发生质的跃迁。