编译器自举实战：从种子编译器到字节级对拍

聊一个我最近踩得很深的圈“编译器自举”。光看这四个字可能觉得高不可攀但简单说就是——你亲手写了一个编译器然后让这个编译器去编译它自己的源代码。听起来像个圆环鸡生蛋蛋生鸡编译器本质也是一段程序它也得被某个编译器编译成可执行文件那第一个“能编译自己”的编译器到底从哪来三个月前我决定自己倒腾一个叫 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 汇编ATT 风格然后用 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 # 阶段 1stage1 编译器mc1再次编译同一份源码 ./bin/mc1 src/mc.ml src/lib.ml -o bin/mc2 # 阶段 2stage2 编译器mc2再次编译同一份源码 ./bin/mc2 src/mc.ml src/lib.ml -o bin/mc3这里我给的命令涉及两个源码文件mc.ml是编译器主源码lib.ml是编译器内部要用到的一些工具函数字符串操作、符号表查找等。种子编译器必须支持一次读入多个源文件并分别解析这也算一个额外需求。第一次跑完这三行命令时整个人的状态是“头顶冒汗”。因为只要有一处编译错误、一处代码生成 bugstage1 可能直接段错误、输出垃圾汇编、或者在链接时失败。我当时在实际操作中遇到的第一个问题是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_EPOCH1700000000 export LANGC # 汇编和链接时固定工具链版本并禁用随机 build-id as --version ld --build-idnone -o 目标文件 ...由于 MiniLang 编译器是自己生成汇编文本再调用 as/ld我可以直接在代码生成器里给 ld 传参把--build-idnone写进链接命令。这样一步到位解决 build-id 差异问题。接着我又用objdump反汇编两个产物然后把反汇编文本做 diff确认差异集中在哪些 sectionobjdump -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 全部一键完成。这玩意儿看着土但在整个自举迭代过程里它是我最重要的护身符。没有它我大概率会在某一次改动后彻底迷失方向。祝你也早日跑通属于自己的自举之旅。