聊一个我最近踩得很深的圈：“编译器自举”。
光看这四个字可能觉得高不可攀，但简单说就是——你亲手写了一个编译器，然后让这个编译器去编译它自己的源代码。听起来像个圆环，鸡生蛋蛋生鸡：编译器本质也是一段程序，它也得被某个编译器编译成可执行文件，那第一个“能编译自己”的编译器到底从哪来？
三个月前我决定自己倒腾一个叫 MiniLang 的小语言，并且定下一个硬目标：不仅要写出它的编译器，还要完成一次完整的编译器自举，最后把两个阶段的编译器产物做字节级对拍（byte-by-byte comparison）。这篇文章就是这次实战的完整记录：种子编译器怎么选型、二次编译怎么跑通、字节级对拍到底在拍什么、又踩了哪些文档里不会写的坑。如果你也想给自己写的语言做一次“自己编译自己”的仪式，这篇应该能帮你省掉不少弯路。
1. 自举到底在解决什么问题
1.1 鸡生蛋的困境
先把这个最基本的困境讲透。假设你发明了一门语言，比如 MiniLang，然后你用 MiniLang 写了一整套编译器源码。这个编译器源码本身是一堆文本文件，机器是不认的。你必须用一个“能把 MiniLang 源码变成机器码”的程序去编译它。可问题是：第一个 MiniLang 编译器程序又该由谁来编译？
你当然可以说：我先用 C 写一个 MiniLang 编译器。好，那这个 C 写的编译器又由谁来编译？有人会用 gcc。那 gcc 又是谁编译的？答案是更早的 gcc。一路追下去，总会追到某个“上古”时刻，那时还没有成熟编译器，整个体系是靠汇编和机器码手工搭起来的。
编译器自举就是把这条追根溯源的链条在你的项目中重新走一遍：先造出一个能用的初始编译器（种子编译器），再让这个编译器去编译“用 MiniLang 自己写的编译器源码”，产生新一代编译器，然后用新一代编译器再次编译同一份源码，验证整个过程是否一致，并且可以循环往复。一旦跑通，你的语言就不再依赖任何外部编译器，真正“自己养自己”。
1.2 自举的本质：三个阶段
整个自举过程用大白话拆开，就三个阶段：
- 阶段 0：用一门已有的语言（我用的 Python）写一个极简编译器，目标是把 MiniLang 编译成 x86-64 汇编，再调用汇编器和链接器生成可执行文件。这是第一个能用的编译器，业内叫种子编译器（seed compiler）。
- 阶段 1：用 MiniLang 自己重写一套编译器源码。注意，这时的 MiniLang 语言基本成型，但编译器还需要外部工具来编译。把这个 MiniLang 源码丢给种子编译器，产物叫 stage1 编译器。
- 阶段 2：用 stage1 编译器再去编译同一份 MiniLang 编译器源码，产物叫 stage2 编译器。
关键点来了：stage1 和 stage2 都是“编译同一份源码”得来的，只是编译器本身不同。如果 MiniLang 编译器已经自举成功，那么 stage1 和 stage2 的行为应该完全一致，甚至二进制产物也应当一致。这时候我们就能做字节级对拍——把两个可执行文件逐字节比较，看它们是不是同一个东西。能一致，说明自举链路是稳定、可信的；不一致，你就有机会顺藤摸瓜找到 bug。
T 型图是编译原理里描述自举的经典工具，一句话就能说清它的意思：
MiniLang 源码 -> MiniLang 编译器（可执行程序） -> 机器码 ^ | 这个编译器由谁编译？ Python 源码 -> Python 解释器 -> 可执行程序简单理解，每一层编译都需要一个“能执行编译器代码”的宿主环境。自举要做的事，就是让“编译 MiniLang 源码”这件事的宿主环境，从 Python 换成 MiniLang 自己。
2. 种子编译器的设计与实现
2.1 起步策略怎么选
想完成自举，第一步不是急着写语言特性，而是先想清楚种子编译器用什么方式落地。常见的路子大约有三种。
第一种：直接用宿主机的高级语言写完整编译器。比如用 Python 或 C 写一个功能足够全的 MiniLang 编译器，然后让 MiniLang 重写源码。这条路实现速度最快，调试方便，适合一个人快速验证整套方案。缺点是你得维护两份编译器实现（一份 Python 一份 MiniLang），两份逻辑必须在行为上对齐。
第二种：用汇编语言写一个极其精简的编译器。这是老一辈编译器作者干的事，信息密度极高，效率极低，但对机器底层的理解会达到变态程度。我敬重这条路，但不推荐现代人上来就干。
第三种：用目标语言（MiniLang 自己的子集）写编译器，然后用宿主语言写一个能编译这个“子集”的最小子解释器或编译器。这种做法的典型代表是 Lisp 的 bootstrap：先写一个非常小的 Lisp 解释器（几百行），然后用这个 mini 解释器去解释更完整的语言实现。这种方式优雅，但调试链路更长，对新手不太友好。
我最后选了第一种，用 Python 写种子编译器。原因很直白：Python 写起来快，好调试，字符串和列表语义跟“编译器该有的数据结构”天然接近。我当时给自己定的原则是：种子编译器只求能用，不求优雅，目标是尽早跑通“Python 版编译器能编译 MiniLang 版编译器”这条链路，之后再慢慢打磨。
2.2 MiniLang 语言定义与编译目标
动手写种子编译器之前，必须先想清楚 MiniLang 到底长什么样。这门语言必须“够用”，因为它要被用来重写一个完整的编译器。一个编译器源码需要的语言特性通常包括：
- 变量声明与赋值：局部变量、全局变量都要有。
- 基础类型：int、指针（int*）、字符串字面量（char*），足够应付符号表、AST 等数据结构。
- 表达式：四则运算、比较、逻辑与或非、取地址、解引用、函数调用。
- 语句：表达式语句、if/else、while、return、块语句花括号。
- 函数：支持递归，支持多参数，函数返回值用 int（反正所有内部数据都能用 int 表示）。
- 结构体：为了让 AST 节点、符号表条目写起来不那么痛苦，我决定让 MiniLang 支持 struct。
MiniLang 的语法我刻意做成了 C 的极简子集。为什么选 C 的子集？因为 C 的语法大家最熟，递归下降解析器写起来顺手；而且将来的目标汇编代码生成也能参考成熟的 System V AMD64 调用约定。
编译目标我直接选 x86-64 汇编（AT&T 风格），然后用 GNU as 汇编器把它变成目标文件，再用 ld 链接成可执行文件。这一步很取巧：我不需要自己处理机器码编码和 ELF 头，只要生成合法的汇编文本即可。
一个示例的 MiniLang 函数长这样：
int add3(int x, int y, int z) { int s; s = x + y + z; if (s > 10) { s = s * 2; } else { s = s - 1; } return s; }就是这么朴素的语言。种子编译器不需要做任何优化，能生成正确、可运行的汇编就够了。
2.3 种子编译器核心模块拆解
种子编译器用 Python 写，整体结构分成三大块。
词法分析器（lexer）：逐字符读入源码，识别出标识符、数字、字符串字面量、运算符和关键字，输出一个 token 数组。MiniLang 的 token 不需要太复杂，几十行代码就能搞定。
语法分析器（parser）：递归下降实现。语法上只有函数定义、变量声明、if/else、while、return 和表达式。表达式我采用大名鼎鼎的“普拉特解析”（Pratt parsing），也就是优先级爬升法。这样加减乘除、比较、逻辑运算的优先级处理极其清爽，比手写十几个优先级的递归函数舒服太多。
代码生成器（codegen）：遍历 AST，为每个函数生成汇编。所有局部变量都静态分配栈帧中的固定槽位，不做寄存器分配优化。表达式求值用类栈机方式，每算出一个子表达式就存到栈里，需要时再取出来。这么做效率不高，但生成逻辑极其简单，几乎是一个模式匹配就能完成。
种子编译器输出汇编后，直接调用外部命令：
as minic_out.s -o minic_out.o ld minic_out.o -o minic_out这样 MiniLang 程序就能跑起来了。运行期间任何“编译出的程序跑挂了”的问题，都能快速定位到是种子编译器代码生成 bug 还是 MiniLang 语言语义本身的问题。
提示：种子编译器阶段尽量少做优化。优化的优先级永远排在“正确”和“可复现”之后。我的种子编译器连常量折叠都没有，所有表达式都老老实实在运行时算，因为这对后续对拍更有利。
3. 二次编译：从 Python 版到自举版
3.1 为什么必须用 MiniLang 重写编译器
这里有个很容易被忽略的关键逻辑：如果你一直用 Python 版编译器去编译 MiniLang 代码，那 MiniLang 充其量只是“被 Python 养着的语言”。只有当你写出一套 MiniLang 版的编译器源码，并且让这套源码被编译成可执行程序，MiniLang 才算真正独立。
“用 MiniLang 重写编译器”本质上不是重新设计编译器，而是把 Python 版种子编译器的逻辑“翻译”成 MiniLang 代码。整体的词法、语法、代码生成逻辑完全保持一致。这是一项体力活，也是整个自举过程中最消磨耐心的阶段。
重写的时候，编译器源码我拆成了几个文件：
- lexer.ml：词法分析器
- parser.ml：递归下降语法分析器
- codegen.ml：代码生成器
- main.ml：入口，读取文件、串联各模块、输出汇编
每个文件短则几百行，长则上千行，全靠 MiniLang 自身的能力支撑。
3.2 重写过程中的取舍
重写编译器源码时，我遇到一个很现实的取舍问题：MiniLang 的“数据结构表达能力”其实不够丰富。比如经典的做法是用结构体数组模拟对象，用链表表示 AST。MiniLang 只有 int、指针、结构体和数组，所以我做了个很朴素的设计：
- AST 节点用一个 struct 表示，节点类型用整型枚举值；
- 子节点用固定大小的指针数组保存；
- 符号表直接就是一个全局数组，线性查找，编译几百行源码足够用了。
这设计听起来很土，但有个巨大优势：行为完全确定。假如你用哈希表存符号，表扩容时机、遍历顺序都可能影响编译器内部状态的展开方式，给后面的字节级对拍引入大量不确定性。用固定数组加线性查找虽然慢，但每次跑出来的结果一定一样，这对对拍至关重要。
另一个取舍是整数语义。Python 的 int 是任意精度的，而 MiniLang 的 int 我定义成 32 位有符号数。这意味着从 Python 版“翻译”到 MiniLang 版时，所有可能溢出的地方都要特别小心。比如哈希函数里最常见的写法hash = hash * 31 + c，在 Python 里随便跑，但在 MiniLang 里整型溢出后就悄悄回绕。如果不统一语义，等到二次编译阶段，同一份输入在两个编译器之间产生不同结果，你连 bug 在哪都找不到。所以我提前把 MiniLang 里所有整数运算都固定成“32 位溢出回绕”的语义，并在每个关键计算点做了行为一致性测试。
3.3 完整的三阶段构建流程
重写完成后，激动人心的时刻来了。整个自举流程我录成了一个三行命令的脚本：
# 阶段 0：种子编译器（Python 版）编译 MiniLang 版编译器源码 python3 mc_seed.py src/mc.ml src/lib.ml -o bin/mc1 # 阶段 1：stage1 编译器（mc1）再次编译同一份源码 ./bin/mc1 src/mc.ml src/lib.ml -o bin/mc2 # 阶段 2：stage2 编译器（mc2）再次编译同一份源码 ./bin/mc2 src/mc.ml src/lib.ml -o bin/mc3这里我给的命令涉及两个源码文件：mc.ml是编译器主源码，lib.ml是编译器内部要用到的一些工具函数（字符串操作、符号表查找等）。种子编译器必须支持一次读入多个源文件并分别解析，这也算一个额外需求。
第一次跑完这三行命令时，整个人的状态是“头顶冒汗”。因为只要有一处编译错误、一处代码生成 bug，stage1 可能直接段错误、输出垃圾汇编、或者在链接时失败。我当时在实际操作中遇到的第一个问题是mc2跑起来根本没有输出，连汇编文件都没生成。排查了好久发现是 MiniLang 版源码里把字符串比较的语义写错了，导致编译器读文件名时就挂了。
等我把这一堆初级问题修完，真正跑通三行命令、看到 bin/mc3 正常生成时，心里那叫一个舒畅。但舒畅没持续多久，因为下一个挑战才是本项目的重头戏：字节级对拍。
4. 字节级对拍：等价性验证实操
4.1 对拍思路和意义
为什么非要字节级对拍？因为“行为一致”这种主观判断不够硬。你说 stage1 和 stage2 都能编译同一个测试程序，但两个编译器编译出来的程序可能只是恰好在测试集上表现相同。字节级对拍更狠：如果两个可执行文件的每一个比特都完全相同，那基本可以认定 stage1 和 stage2 在编译这条源码时走的是完全相同的路径，没有任何隐性分支被触发到不同方向。
对拍的意义还不止于此。它顺便给了你一门“可重现构建”（reproducible build）的语言。今天的软件供应链里，可重现构建是验证“源码到二进制无被篡改”的重要防线：同一份源码，任何人、任何时间、在相同环境下构建，产物应当逐字节一致。编译器自举的对拍，其实是把这套思想应用在自己身上。
4.2 对拍命令与规范化处理
最直接的对拍命令如下：
# 查看哈希 sha256sum bin/mc1 bin/mc2 bin/mc3 # 两个编译器直接逐字节比较 cmp bin/mc2 bin/mc3 # 如果想看具体差异位置 cmp -l bin/mc2 bin/mc3 | head -20我第一次执行cmp bin/mc2 bin/mc3，结果毫无悬念地告诉我：文件不同。这时候心里反而踏实了，因为这才是常态，自举一次就成功且二进制一致的案例太少见了。
接下来要处理的是“哪些差异是真正的语义差异，哪些只是表面差异”。
表面差异通常来自这些地方：
- ELF 头里的 build-id：链接器可能默认生成一个随机的 build-id；
- 调试信息里的绝对路径：编译时如果源码路径被写进了
.debug_str段，不同路径就会造成差异； - 时间戳：某些链接配置会在产物里打上时间戳；
- 默认 PIE 配置：不同工具链版本处理 PIE 的方式不同，会产生不同布局。
对这些表面差异，处理办法不是改代码，而是规范化构建环境。我当时在构建脚本里加了这些环境变量和参数：
export SOURCE_DATE_EPOCH=1700000000 export LANG=C # 汇编和链接时固定工具链版本，并禁用随机 build-id as --version ld --build-id=none -o 目标文件 ...由于 MiniLang 编译器是自己生成汇编文本再调用 as/ld，我可以直接在代码生成器里给 ld 传参，把--build-id=none写进链接命令。这样一步到位解决 build-id 差异问题。
接着我又用objdump反汇编两个产物，然后把反汇编文本做 diff，确认差异集中在哪些 section：
objdump -d bin/mc2 > mc2.text objdump -d bin/mc3 > mc3.text diff mc2.text mc3.text | head -100如果差异只出现在.text段之外，那么问题大概率是“编译器自身的代码生成路径有一致性隐患”，而不是“死循环”级别的 bug。这一步能帮你把问题范围从“整个二进制不一致”缩小到“某一段代码生成不一样”。
4.3 字节不一致的定位方法
规范化表面差异后，如果还有字节不同，下一步就是缩小范围。我的调试方法是写一个脚本，让 mc2 和 mc3 分别编译自己源码中的一个小测试函数，然后比较编译产物。逐步把输入从“整个编译器源码”缩小到“某一个函数”，直到找到一个最简单的测试用例如下：
int f(int x) { return x * 31 + 1; }如果 mc2 和 mc3 对这个函数的编译产物仍不一致，问题范围就被压缩到了编译器内部的表达式生成逻辑。如果一致，再逐步扩大源码范围，二分定位到具体模块。
我还见过一个更隐蔽的坑：编译器源码里用了“全局变量初始化顺序”和不同 stage 的可执行文件里 BSS/BBS 段布局不同，导致某个全局变量在运行时被踩到不同的内存地址。这种情况下反汇编 diff 看不出明显逻辑差异，但运行行为就是不一致。我的土办法是在编译器里加一个内部诊断指令——可以理解为一个隐藏接口——让编译器把符号表的内容完整打印出来。mc2 和 mc3 分别跑这个诊断模式，对比输出结果，一眼就能看出是哪个符号的编号、地址或者哈希值发生了变化。
实操心得：对拍调试的黄金法则是“先缩小输入，再缩小范围”。不要一上来就抱着整个编译器源码找 bug，那是大海捞针。花十分钟写个自动二分脚本，比折腾半小时人肉肉眼看汇编强得多。
5. 常见问题与避坑记录
5.1 stage1/stage2 对拍不一致
这大概是自举项目里最常见的噩梦。你辛辛苦苦跑通了三阶段构建，兴致勃勃地cmp两个文件，结果它们不同。先别慌，按顺序排查：
第一步，确认是不是表面差异。用上一节提到的规范化手段：固定 build-id、剥离调试信息、设置 SOURCE_DATE_EPOCH。很多“不一致”其实是环境噪音。
第二步，检查你的编译器是否有非确定性行为。比如符号表用了哈希表，而哈希表的插入顺序依赖某个随机种子；或者代码生成器遍历了某个字典，字典迭代顺序不稳定。这些东西在 Python 版编译器里可能无伤大雅，但到了 MiniLang 版，不同 stage 的编译结果就会分叉。我采取的措施是把所有需要遍历的数据结构都改成固定顺序的数组。
第三步，检查是否有未定义行为。C/C++ 里的经典未定义行为在自研语言里同样存在，比如 32 位整型溢出、有符号右移、指针比较等。如果没有明确规定语义，两个编译器可能各自解释，产生不同代码。无论自研语言还是 C 语言，都得在语言定义阶段就把这些语义钉死。
5.2 编译器特性不足导致的自举死锁
自举过程中最难受的瞬间，是你想要实现一个新语言特性，却发现编译器自身还没有这个特性。举个例子：我早期想让 MiniLang 支持结构体，但 MiniLang 版编译器源码本身还没有结构体可用，所以我没法用结构体来实现结构体的支持——这不是鸡生蛋问题，这是你站在悬崖边的死锁问题。
我的解决办法其实很朴素：先在 Python 版种子编译器里把结构体语法和语义实现好，让 MiniLang 能使用结构体；然后把 MiniLang 版编译器源码改写成用结构体实现；最后重新做一次三阶段构建。整个过程等于“用旧编译器编译支持新特性的新编译器”，这正是自举的又一个循环。
这个经历给我的启发是：设计一门“要自举的语言”时，从语言定义阶段就要留足底子。哪怕你一开始只用全局数组写编译器，也要把 struct、指针、递归这些特性先塞进去，否则后期每加一个特性都要经历一次“特性倒逼”的阵痛。
5.3 工具链版本对字节一致性的影响
另一个让我头疼很久的问题来自外部工具链：as 和 ld 的差异同样会导致二进制不一致。当时我换了台机器重新构建，发现哈希突然对不上了。查了很久才发现，新机器上默认的 GNU as 版本比旧机器新，而新版汇编器对某条指令的默认编码策略跟旧版不同，导致目标文件出现细微差异。
解决方案有二：一是固定使用相同版本的工具链，甚至把 as、ld 的二进制路径写死在构建脚本里；二是尽量让生成汇编的格式简单、稳定。比如我后来规定编译器代码生成一律不依赖汇编器的指令选择结果，转而直接用明确的指令助记符和操作数字节。
链接层面的布局差异也同样隐蔽。如果 ld 默认链接脚本变化，section 顺序就可能改变，最终可执行文件的布局就不同。我直接写了一个自定义链接脚本，把 .text、.data、.bss 的地址全部固定：
SECTIONS { . = 0x400000; .text : { *(.text*) } .data : { *(.data*) } .bss : { *(.bss*) } }这样就让链接结果只取决于源码和汇编内容，与外部环境基本解耦。虽然这种硬编码地址缺乏通用性，但放在自举验证场景里完全够用。
5.4 信任边界值得多想一步
聊到对拍，必须得提一个无法回避的点：对拍能证明“两个构建产物一致”，但证明不了“种子编译器是善意的”。
计算机科学里有一个非常著名的思想实验，叫“信任信任”（Reflections on Trusting Trust）。它的核心意思是：如果攻击者能悄悄修改你最初的种子编译器，让它在编译任何代码时都隐藏一个后门，那么这个后门会随着每一代编译器自动延续下去。哪怕你后来用新版编译器重新编译自己，后门也可能被完整保留。传统的字节级对拍遇到这种情况，很可能只会告诉你“两次构建完全一致”，因为这份源码和这个编译器里都藏着那个后门，它们“诚实地”把恶意功能继续编译了出来。
所以我个人的经验是：对拍是为了验证一致性，但真正要提高安全性，得从一开始就降低对单一信任根的依赖。比较务实的几个做法，一个是尽量减小种子编译器的尺寸；另一个是用两条完全独立的实现路径（比如 Python 一条路、用 C 写的另一条路）去互相验证；还可以找第三方独立交叉检查编译结果。对于玩个人语言项目来说，这些不一定都得做，但至少心里要有这根弦。
6. 实测记录与一点心里话
最后说点我的实测结果。
整个项目跑通后，我拿到了几组有意思的数字：MiniLang 版本编译器源码大约 5000 行；Python 版种子编译器编译 MiniLang 版源码，需要大概 3 秒钟；stage1 编译同一份源码，大约需要 0.2 秒；stage2 编译同样源码，也是 0.2 秒。最终 mc2 和 mc3 的哈希完全一致，cmp没有任何输出，那一刻确实很有成就感。虽然中间经历了无数次段错误、死循环、汇编生成错乱和对拍失败，但看到两个二进制完全一致时，你会觉得之前熬的夜都值了。
如果非要分享一点个人体会，我想说：编译器自举最大的收获不是“我会写编译器了”，而是你亲手验证了“语言和它的工具链是一个可以自洽生长的体系”。你写的语言从此不再依赖任何外部宿主语言，它有了自己的生命力。
想自己动手试的朋友，我建议从小做起。不要一上来就想做一个完整的高级语言，能表达算术、函数、控制流和数组就足够了。种子编译器尽量写简单，用你最熟悉的 Python 或 C 都行，核心目标是尽快跑通三阶段链路。每改一次语言特性，就重新跑一遍三阶段构建和字节对拍，让对拍脚本替你把关。
最后再分享一个小技巧：把对拍脚本写成自动化的 shell 脚本，每次修改完编译器源码就顺手跑一遍，三阶段构建、哈希比较、反汇编 diff 全部一键完成。这玩意儿看着土，但在整个自举迭代过程里，它是我最重要的护身符。没有它，我大概率会在某一次改动后彻底迷失方向。祝你也早日跑通属于自己的自举之旅。
