第一次把“编译器自举”这条路走通是在一个周六凌晨。谈不上多壮丽但那一刻确实把脑子里存了很久的一道疑问解开了编译器到底是怎么出现的更准确地说如果只给你一台能运行最基本工具的机器你要怎么让一门语言能“自己编译自己”这篇文章想记录一次完整的自举实战从种子编译器起步经历二次编译链路最后用字节级对拍把两代编译器的产物逐字节对比证明整个自举过程是闭合的。整个实验花了我大概一个月的业余时间不要求你有编译器骨架级别的背景只要会一点C、有基本的命令行经验就能跟着这套思路复现。我给自己定下的验证原则是不拿“结果能跑”当证据不拿“测试用例部分通过”当证据而是让第N代编译器去编译同一份编译器源码再把它的输出与第N-1代输出做字节级对拍只有逐字节一致这个循环才真正闭合。1. 项目规划与总体方案自举链路怎么设计最稳妥1.1 三种自举路线与我的选择不是所有自举都是同一条路。动手之前我花了整整两天把自己能查到的开源自举方案梳理了一遍总结下来大致有三种典型做法。垂直自举手写一个非常小的种子编译器每个新一代编译器都由上一代去编译自己的源码生成。这是最“纯”的做法也是本文采用的主路线。交叉自举在成熟的宿主平台上先编出目标平台的编译器再把产物拷贝到目标平台继续使用。嵌入式场景常见但严格来说不解决“小鸡从哪来”的问题。半自举先用另一门语言重写编译器前端通过某种中间层逐步过渡最终让新语言去编译自己的编译器。GCC、Rust 早期都走过类似路线工程上稳妥但链路长内部依赖多。我自己做实验选择的是垂直自举因为它的每一步都能单独被验证种子越小越容易人工审查每一代产物都有明确来源最后一环的字节级对拍可以在没有任何神秘黑盒的情况下完成。缺点也很明显就是“慢”每一代都要从源码开始完整编译但个人项目完全能耗得起。路线优点缺点适用场景垂直自举逻辑清晰、可验证性强、独立性强慢需要从极小子集起步个人实验、可信编译链交叉自举快复用宿主工具链依赖宿主目标机无法独立重建嵌入式、新架构移植半自举兼容性好演进平滑过渡期存在多套语言混合大型语言工程三种路径各有侧重。如果你只是想体验自举的完整逻辑垂直自举是最合适的。如果你想给自己团队的语言做工程化构建半自举更现实。1.2 目标语言与关键约束我定义了一门极简的类C语言命名为 MiniLang。目标平台定为 x86-64 Linux输出 ELF 可执行文件。MiniLang 的语法刻意去掉了不少 C 里容易干扰自举设计的东西没有前置声明依赖没有复杂头文件机制没有泛型也没有运算符重载。它保留的是支撑“写编译器”这级别复杂度所需的最小能力集整数与布尔类型、指针、数组、函数、递归、控制流、结构体。这里有一个很重要的考虑自举不是让语言能编译“Hello World”而是让语言能编译自己的编译器源码。这意味着语言必须能表达词法分析、语法树、符号表、代码生成这类常规业务逻辑。MiniLang 的这套能力其实和早期 Pascal、Modula-2 的子集很像它刻意回避了真正困难的特性比如带闭包的匿名函数、泛型、异常处理因为那些会把种子编译器瞬间撑大让审查成本高到不现实。关键的工程约束我写出来供你参考种子编译器不引入任何动态分析或优化只做词法、语法、代码生成这条线性链路。编译器源码不依赖第三方库所有数据结构表、树、栈都用 MiniLang 自己实现理由我会在第 3 章详述。构建全过程不联网不下载任何二进制保证每一步可追溯。生成汇编后统一调用系统汇编器as和链接器ld组装成可执行文件。这一步相当于把最小信任边界划在了汇编器和链接器上对个人实验完全可接受。这套约束看起来是自我设限实际上它帮我避免了一类很隐蔽的问题只要依赖第三方库自举验证的结论就会被“库由谁编译”的问题污染。1.3 为什么最终验证标准是字节级对拍很多人会问自举成功与否跑一遍编译器测试集不就行了我一开始也是这么想的但推演下来发现功能测试只能证明“新编译器行为范围覆盖了测试集”无法证明“新编译器就是旧编译器的等价物”。真实场景里两个编译器可能在某条冷路径上行为不同而所有测试用例恰好都走不到那条路径。字节级的对比逻辑是强得多的验证如果来源相同的源码用 Stage1 和 Stage2 两次独立编译二进制产物逐字节完全一致那至少可以断言在这份源码对应的语义范围内两代编译器没有任何可观察差异。更进一步如果让这个过程连续重复三轮哈希值依然一致那基本可以把“确定性构建”也一并验证掉。字节级对拍不能解决的问题我也坦诚说它无法证明种子编译器本身没有恶意或没有错误。这是“信任起点”问题后面第 2 章会专门讲。2. 种子编译器最小但完整的第一步2.1 种子编译器该包含什么、不该包含什么种子编译器Stage0是整个链条里唯一可以直接人工审查的部分。它的定位很明确足够小到一个人能在一周内读完整份代码并理解每一行的作用同时又足够完整到能把“真实编译器”的源码翻译成可运行的机器码。这里真实编译器指的是用 MiniLang 写的 MiniLang 编译器也就是后面要自举的对象。所以种子编译器并不需要懂语法树优化不需要寄存器分配策略它只需要做一件事把 MiniLang 源码翻译成 x86-64 汇编。我给自己划的规模红线是种子编译器不超过 1500 行 Python。词法分析约占 250 行语法分析约 600 行代码生成约 400 行辅助工具和错误处理约 250 行。这个规模的好处是出问题的时候真的可以把整份代码打印出来逐行盯。不该包含什么同样重要。种子编译器不做任何常量折叠层面的优化不做复杂的错误恢复不支持浮点数不支持嵌套注释。所有这些表面上是语言特性缺失实际上是在压低种子的复杂度。每少一个分支你的人工审查就少一个盲区。2.2 词法与语法用最朴素的递归下降搞定词法分析器的工作非常机械把源文件变成 token 流。MiniLang 的 token 类型包括整数常量、标识符、字符串、关键字以及各种运算符和分隔符。种子编译器里这一段完全可以当模板看。# seed/lexer.py关键逻辑已简化 import re KEYWORDS {if, else, while, return, let, fn, struct} def tokenize(src): tokens [] i 0 n len(src) while i n: c src[i] if c.isspace(): i 1 continue if c #: # 单行注释 while i n and src[i] ! \n: i 1 continue if c.isdigit(): j i while j n and src[j].isdigit(): j 1 tokens.append((INT, int(src[i:j]))) i j continue if c.isalpha() or c _: j i while j n and (src[j].isalnum() or src[j] _): j 1 word src[i:j] tokens.append((word, None) if word in KEYWORDS else (IDENT, word)) i j continue # 运算符与符号 two src[i:i2] if two in (, !, , , , ||, -): tokens.append((two, None)) i 2 continue tokens.append((c, None)) i 1 tokens.append((EOF, None)) return tokens词法分析有一个经验点尽早把所有注释剔除而不是把注释作为一种 token 交给语法分析。自举阶段所有源码都是自己写的注释里不会有任何需要解析的内容交给下阶段只会徒增复杂度。语法分析我选了递归下降没有用 LALR 或 PEG 生成器。为什么生成器需要引入一套 DSL 语法来描述文法这意味着种子编译器里又多了一层需要审查的信赖关系。递归下降写出来就是普通的函数调用一个函数对应一个语法产生式参数、循环、递归都用现成的机制任何一个只懂基础编程的人都能直接读代码理解文法。表达式解析是递归下降里最容易写错的地方。MiniLang 表达式涉及优先级*、/高于、-比较运算再低一层。标准做法是分层函数。我依赖了一个简单的 Pratt 解析技巧但底层逻辑还是同一套从左到右通过优先级绑定“吸收”右边的操作数。# seed/parser.py表达式解析的骨架 def parse_expr(self): node self.parse_primary() while self.peek_type() in (, -, *, /): op self.next() rhs self.parse_primary() node (binop, op, node, rhs) return node这段代码有个明显的取舍它没有严格按优先级拆层而是用了先结合的先入树的方式。对于一个小语言自举来说这种简化足够用代价是生成的语法树会让a b * c变成先算加法。解决起来也不难把 parse_primary 里的运算符选择换成递归调下一层即可我就不贴完整版了网上随便找都能搜到。2.3 代码生成先保证正确再谈效率种子编译器的代码生成是最容易“翻车”的部分。MiniLang 是强类型但很接近 C 的语言所以代码生成不复杂表达式对应一段求值代码语句对应一段含控制流的代码函数对应带 prologue/epilogue 的汇编段。我选择用一个极简的固定寄存器分配策略而不是做完整的寄存器分配器。策略是每个表达式计算完之后结果放进固定寄存器%rax临时值不足时统一使用栈来保存。这会让生成代码非常啰嗦很多局部变量不断在写栈和读栈之间来回搬运但正确性极好也很容易调试因为每个表达式的汇编结构都是肉眼可检查的。一个 MiniLang 加法表达式翻译到汇编大概是这个样子movq -8(%rbp), %rax pushq %rax movq -16(%rbp), %rax popq %rcx addq %rcx, %rax没有优化没有化简可读性却很高。对比一下真实编译器动辄生成几百种不同指令组合自举场景的编译器老老实实生成模板化代码完全是可以接受的。原因很现实编译器的运行时间我们耗得起编译器源码的正确性我们验证不起。关于“效率让位于正确性”我在第 5 章还会讲怎么把这两者的权重反转过来。2.4 关于“种子必须被信任”的一点思考熟悉编译原理的人应该知道Ken Thompson 曾在图灵奖演讲里讲过一个反例如果种子编译器在识别某段特定源码时故意生成带后门的二进制那么后续所有代编译器都会继承这个后门并且因为自举的存在后门可以在源码层面完全不可见。这类问题叫做“信任起点问题”。字节级对拍只能证明两代编译器彼此行为一致不能证明这组行为是安全的。所以我做自举实验的时候给自己定了一条纪律种子编译器只保留一个月等自举完成后会从头手工再读一遍它的每一行确认没有任何“惊喜”逻辑。这不是偏执而是接触到可信计算之后养成的习惯。编译器是人写的只要它是人写的它就可能写得不诚实。3. 二次编译让编译器“自证清白”3.1 二次编译的完整流程整个自举链路最精彩的部分就在二次编译。先把这个过程用命令写下来后面一步步展开解释。# 第 1 代用种子编译真实编译器源码 python3 seed/seed.py minic/compiler.mi -o build/stage1.s cc -o build/stage1 build/stage1.s -no-pie -Wl,--build-idnone # 第 2 代用 stage1 再次编译同一份源码 ./build/stage1 minic/compiler.mi -o build/stage2.s cc -o build/stage2 build/stage2.s -no-pie -Wl,--build-idnone # 对比后面会细化 sha256sum build/stage1 build/stage2从命名上看stage1是种子编译器产出物stage2是stage1编译同一份compiler.mi得到的产物。如果两者行为完全等价那么自举就等于完成了一大半。这里有个细节很关键cc命令只是把汇编代码变成可执行文件不做任何 C 语言层面的编译所以这一环节在严格验证时也可以用as加ld来代替。我上面写cc只是为了省事。-Wl,--build-idnone是我绕过的第一个坑。GNU ld 默认会给每个 ELF 生成build-id这个 ID 基于内容计算虽然对二进制对比影响不大但会让哈希值里多一个变量不利于排查阶段定位问题。3.2 二次编译到底在证明什么这是理解整篇博客最重要的一节。二次编译不是脱裤子放屁它从逻辑上截断了对种子的依赖。设想一下种子编译器用 Python 实现它把 MiniLang 源码翻译成汇编。现在我们把用 MiniLang 写的真实编译器源码compiler.mi交给种子编译器得到stage1。此时stage1是一个可执行的二进制它本身是 MiniLang 编译器。关键的一步出现了再用stage1去编译同一个compiler.mi得到stage2。如果stage1和stage2字节一致那么我们就得到了一个不依赖任何 Python 脚本、也不依赖任何外部解释器的独立编译器。把这一步拆开解释就是stage1的编译工具是 Python 种子输入是compiler.mi。stage2的编译工具是stage1输入同样是compiler.mi。如果stage1和stage2相同说明“用 Python 写的种子编译器”和“用 MiniLang 写的编译器”在compiler.mi这个输入上达成了语义等价。更进一步从stage2开始我们已经不需要 Python 种子了。种子可以删掉编译器自己可以继续编译自己跳出“鸡生蛋”循环。这正是自举的精髓种子只是引导最终系统靠自己的力量存续。3.3 为什么第一次自举容易失败我原以为二次编译既然只需要几分钟过程应该很顺。实际上第一次尝试stage2和stage1根本无法同时通过验证。原因出在链接阶段编译器源码里我顺手用了一个来自系统库的函数种子编译器能正常调用但生成的可执行文件却因为动态链接引入了一些额外的启动逻辑。解决方式是写一个最小的运行时库把编译器自身的入口点、内存分配和简单的内存布局全部塞进源码里不直接依赖系统提供的启动代码。MiniLang 编译器在编译之后需要通过一段固定的入口代码进入main函数这段代码我用汇编写了大概 60 行然后在链接时显式指定_start符号。这个过程里没有编译器能帮你自动解决“运行时边界”问题。你必须明确知道自己的程序从哪里开始执行堆内存从哪里拿栈帧怎么布局。这反而是自举最好的老师——它直接把操作系统的 ABI 逼到你面前。4. 字节级对拍两个编译器等价的硬核证据4.1 对拍脚本的设计思路字节级对拍听起来很高端实现起来其实特别朴素一个哈希函数一个文件对比工具加一点脚本胶水。但真正设计脚本时有两个点要想清楚。第一对拍的对象不止是最终二进制。我会把每一种中间产物都纳入对比汇编文件、反汇编文本、编译时错误输出。只看最终二进制有一个盲区链接器可能因为环境变量不同而改变布局从而掩盖或放大真实的差异。多级对比能帮你快速定位差异到底发生在哪一层。第二对拍要支持重复执行。自举验证不是一次性结论必须连续三次运行得到同样结果才算通过。这能排除掉环境变量、随机哈希、时间戳这类偶发因素。我一直维护的一套脚本结构是这样#!/usr/bin/env python3 import hashlib import subprocess import sys def sha256_file(path): h hashlib.sha256() with open(path, rb) as f: for block in iter(lambda: f.read(65536), b): h.update(block) return h.hexdigest() def run(cmd): print(, .join(cmd)) subprocess.run(cmd, checkTrue) BUILD build SRC minic/compiler.mi def main(): # stage1 run([python3, seed/seed.py, SRC, -o, f{BUILD}/stage1.s]) run([as, -o, f{BUILD}/stage1.o, f{BUILD}/stage1.s]) run([ld, -o, f{BUILD}/stage1, f{BUILD}/stage1.o, -no-pie]) # stage2 run([f./{BUILD}/stage1, SRC, -o, f{BUILD}/stage2.s]) run([as, -o, f{BUILD}/stage2.o, f{BUILD}/stage2.s]) run([ld, -o, f{BUILD}/stage2, f{BUILD}/stage2.o, -no-pie]) h1 sha256_file(f{BUILD}/stage1) h2 sha256_file(f{BUILD}/stage2) print(fstage1 sha256: {h1}) print(fstage2 sha256: {h2}) if h1 ! h2: print(MISMATCH, filesys.stderr) sys.exit(1) print(BOOTSTRAP OK) if __name__ __main__: main()没有装任何复杂的测试框架就是二十几行 Python。但脚本内部体现了两个工程约束所有编译参数写死不让它在不同机器上随机变化输出路径固定避免绝对路径污染 ELF。4.2 常见的“字节不一致”来源如果你第一次自举就完美通过那只能说明你运气好或者你复现的是别人调好的链条。我踩过的“函数能跑但字节不一致”的来源基本集中在四类。第一类是哈希表遍历顺序不稳定。编译器里的关键字查询、变量表、符号冲突表凡是用了开放寻址或者桶数组的如果插入顺序受随机种子影响那么生成的汇编顺序就会变化最终二进制必然不同。这是字节对拍最容易触发的差异。解决方式很简单编译过程里把哈希表的迭代改成按键值排序后再输出牺牲一点点时间换确定性。第二类是链接器生成的元数据。build-id、.comment段、文件名时间戳这些会在最终 ELF 里留下痕迹。用readelf -x .comment看一眼通常能看到编译器版本和构建时间。要做字节级对拍就得把这些全部去掉或固定下来。第三类是未初始化内存。编译器在生成汇编时如果有一个局部数组没清零而某个分支只写了一部分就直接输出读出来的内容就会是栈上残留的垃圾值。这在单次运行时不会有可观察差异但对拍非常敏感。从代码上解决就是所有缓冲区统一 calloc 而不是 malloc。第四类是命令行参数中的路径。我的编译器会把源码路径作为调试信息嵌入到汇编文件注释里导致不同目录下编译结果不同。这个更容易处理生成汇编时不输出绝对路径只输出文件名。4.3 字节级对拍失败时的定位方法对拍失败的第一步不是去改代码而是先按层次定位差异在哪一层出现。我通常按下面的顺序操作先对比.s汇编文件。如果汇编已经一致说明问题在汇编器或链接器真正要查的是系统工具链。如果汇编不一致对比两个汇编文件的行号。差异通常集中在某几个函数上直接搜对应源代码位置。如果两个汇编文件完全一致但.o不一致大概率是.comment段或调试信息在作祟用objdump -s看具体哪个段不同。如果.o一致但可执行文件不一致基本就是链接时的 build-id 或布局问题。有一次我遇到一个特别诡异的情况stage2.s和stage1.s只有一行注释不同但二进制差异却出现在另一个完全不相干的函数里。最后发现是符号表重排列导致了对齐填充发生了变化。这提醒我字节级对拍不该只看最终文件哈希还要看中间产物。否则你会被一层层间接差异折磨到怀疑人生。5. 踩坑实录与工程化建议5.1 常见问题速查表把我在整个实验里遇到的高频问题整理成表方便你按图索骥。症状根因处理方式stage2 二进制哈希不稳定连续两次不同哈希表遍历顺序受随机化影响将编译器输出统一按键排序二进制不同但 .s 文件一致链接器写入 build-id 或时间戳用ld --build-idnone固定SOURCE_DATE_EPOCH编译器运行时段错误递归下降解析器栈溢出增大栈帧或改写解析循环减少深层递归生成汇编在as阶段报错暂存寄存器覆盖了跨表达式的值统一使用栈保存跨表达式值禁止跨调用保持临时值二次编译后行为正常但与 stage1 不同某种依赖宿主环境的未定义行为用编译器源码里强制初始化所有栈缓冲区禁止依赖残留值链接失败找不到 _start编译器源码依赖了系统启动代码在汇编层显式定义入口自己处理栈和入口调用这张表里的每一项都是我在实际运行里亲手撞过的不是从文档里抄来的。尤其是“暂存寄存器覆盖”这一条最容易发生也最隐蔽。MiniLang 代码里只要你写了一个类似tmp a b * c的表达式代码生成阶段需要连续计算多个子表达式寄存器不够用时就会用到栈。这个栈保存和恢复的代码一旦少了一句汇编器不会报错但运行时结果就是随机的。5.2 三条实操心得第一测试集一定要先写再写编译器。我一开始的顺序是反的先写编译器再补测试结果所有测试都被编译器带偏很容易写出“编译器通过测试”但“测试验证的是编译器错误行为”的假象。后来我改成先把 MiniLang 的运行行为定了写一套独立的参考测试程序再让编译器去对齐这套程序。测试集不需要很大几十个小程序覆盖基本语法、递归、指针、结构体就够用了关键是每个程序都必须有明确预期输出。第二保留现场比修复错误更重要。自举过程中最怕的就是“这次失败了但改了源码后没法复现”。所以我养成了一个习惯每次失败先把当时的stage1、stage2、两个.s文件和输入源码全部打 tag 存档再动代码。这样一旦新改动引入新问题我可以随时回到旧现场对比。不要低估这个习惯的价值字节级对拍恰恰需要旧二进制做参照。第三逐步去除宿主依赖。种子编译器是用 Python 写的它天然带了一些宿主特性比如大整数、按键遍历字典、动态字符串。这些特性在小规模测试时没问题一旦编译器源码变大就会出现很多“Python 能算、stage1 算不出相同结果”的情况。我的做法是尽早用 MiniLang 重写工具链里所有非核心组件比如打印、字符串处理、符号表把 Python 能调用的特殊手段全部替换成固定行为。宿主特性每少一个自举的可信度就高一分。5.3 后续可以怎么扩展自举成功不代表项目就此终结恰恰相反它意味着你现在拥有了一个“自己的编译器”这比任何第三方编译器都更适合当教学骨架和实验载体。一个自然的扩展方向是给 MiniLang 加优化能力。比如在语法分析之后插入一层简单的常量折叠让2 * 3这样的表达式在编译期就算成6。这能显著减少生成汇编的体积也让编译器源码变得更复杂值得作为第二个自举项目的起点。另一个方向是端口到其他架构。MiniLang 的种子编译器把代码生成集中在一个模块里换架构只需要替换这个模块。我后来试着把代码生成从 x86-64 改成 RISC-V 风格的伪汇编大概两个晚上就看到了效果。这个过程的收益在于你会更深刻理解“编译器前端与后端分离”的必要性。如果你还有精力可以尝试把构建脚本也“自举”。我现在是手动维护那个 Python 对拍脚本理论上也可以用 MiniLang 重写一个构建系统让构建过程本身也能被编译器自身生成。这就进入“吃自己的狗粮”的循环了工程上非常过瘾但也非常容易上瘾。有一次我把系统整个重装旧 stage1 误删了。唯一保留下来的只有种子编译器和一堆源码。我照着全新环境从种子开始重新走完整个链路最后打出的哈希和上次一模一样。那一刻我才真正明白自举的意义不在于“编译器能编译自己”这一个结果而在于整条工具链可以在没有外部依赖的环境里把自己从源头完整重建出来。编译器不再是某个藏在模型里无法直视的黑暗盒子它会变成你手里一件随时可以拆开再装上、坏了也能修的日常工具。如果你也想建立这种心底的踏实感找一门小语言照这个流程完整做一次自举实战值得。