如果你写过多年代码一定对编译器背后的“鸡生蛋”问题产生过好奇编译器是用什么语言写的如果编译器是用它自己编译的语言写的那第一个编译器又是哪来的这次我花了两周业余时间把“编译器自举”这条线完整走了一遍——从手写种子编译器开始到用它编译编译器自身最后用字节级对拍验证结果一致。整个过程像是解开一个递归谜题每个环节都有一层“原来如此”的快感边做边觉得这东西真该纳入每个程序员的基础训练。先交代清楚这次实战的边界。我实现的目标语言是一个类C子集叫BSCBootstrap C去掉结构体、指针运算以外的语法糖只保留int类型、函数、if/else、while、return、变量声明和算术/比较/逻辑表达式但足够支撑一个真实编译器自举。整个工程分成三段第一段用C语言写一个种子编译器能够把BSC源码编译成RISC-V 64汇编第二段用这个种子编译器去编译一份用BSC语言重写的编译器源码得到自举后的编译器本体第三段把两套流程产出的可执行文件做字节级对拍确认行为完全一致。这篇文章就是把完整过程、关键决策、踩过的坑全部摊开。无论你是想搞懂自举原理还是打算动手做一个迷你编译器又或者只是想看看“字节级对拍”这种验证手段到底怎么落地这篇都能给你一份可以直接参考的实战笔记。先不要急着看代码我们先把为什么要这么设计聊透彻。1. 整体设计与思路拆解1.1 为什么必须有一条“种子链路”要理解自举先得理解编译器的一个基本事实编译器本质上是把源码A翻译成目标代码B的程序P。P自己也是一个程序它需要另一个编译器来编译。如果我们想做一个编译BSC语言的编译器并且最终希望这个编译器自己能编译自己的源码就绕不开一个起点问题——最初的编译器是谁编译的业界给的答案就是“种子编译器”bootstrap compiler用一门已经存在、已经可用的语言通常是C写一个目标语言的最小编译器用它去编译目标语言写的更大编译器。这条链路一旦走通整个工具链就能自我供养不再依赖外部语言。我采用的方案是经典的三阶段自举路线用C语言写一个最小但完整的BSC编译器称为bsc-c它能把BSC源码翻译成RISC-V 64汇编。用C语言的gcc把bsc-c编成可执行文件bsc0这是种子编译器本体。用BSC语言重写一份功能等价的编译器源码称为bsc-self.bsc用bsc0去编译它得到bsc1。此时bsc1是一个“真正用自己语言编译出来”的编译器。核心要点在于第3步bsc-self.bsc是用BSC写的而BSC的能力范围必须在bsc0对BSC的实现能力之内也就是不能超出自己的子集标准。这是自举能否成立的关键约束。1.2 自举路线选型跨平台编译还是本地编译动手前我先纠结了一段时间到底采用交叉编译还是本地编译。所谓的交叉编译就是在x86机器上生成RISC-V的汇编文件再用目标架构的汇编器和连接器生成可执行文件。本地编译则是直接在RISC-V环境里跑完整流程。我最终选了交叉编译路线原因很实在开发环境是x86 Linux可以在本地快速迭代而且RISC-V汇编器riscv64-linux-gnu-as和连接器riscv64-linux-gnu-ld都很成熟不需要真的准备一块RISC-V开发板。交叉编译并不会影响自举性验证因为自举成立的判定标准是“编译器能否编译自己的源码”而不是“编译器跑在哪个架构上”。这里也顺带解释一个容易混淆的概念一个编译器能编译自己的源码这叫“自托管”self-hosting。这需要编译器语言本身达到“图灵完备”且表达力够用。BSC虽然去掉了指针和结构体但函数、递归、数组和整数运算组合起来已经足够表达一个编译器的全部逻辑。后来实际验证也证明了这一点整个BSC重写的编译器源码大约4300行没有用任何超出子集范围的特性。1.3 T型图思维怎么判断“自举成功”判断自举是否成功业内有个很直观的工具叫“T型图”T-diagram。思路是这样的一个编译器可以用三要素来描述——源语言S、目标语言T、实现语言I记作S - T用I写。如果BSC - RISC-V用C写而BSC - RISC-V用BSC写那么后者就是前者的“自举版本”因为实现语言从C换成了BSC自己。依赖这个图形推演就能得出一个判定方法如果你用BSC写的编译器源码同时用种子编译器和“被自举出来的编译器”各编译一次发现两个可执行文件在功能上完全一致那自举就验证成功了。更严格一点如果汇编输出能逐字节一致那就是字节级对拍的意义所在。级联关系理顺了后面看操作才不会迷路。2. 种子编译器实现从零定义BSC子集2.1 BSC语言的边界定义种子编译器是整个自举链的地基。地基不稳后面全是空中楼阁。我在设计BSC时给自己列了三条硬约束第一语言必须小到一个人能在一周内实现完第二语言的表达能力必须足以支撑一个编译器的编写第三每个特性都必须在bsc0和bsc1两代编译器里有一致且无歧义的语义。最终BSC的语法大概长这样int fib(int n) { if (n 1) { return n; } return fib(n - 1) fib(n - 2); } int main() { int i; i 0; while (i 10) { print_i(fib(i)); i i 1; } return 0; }支持的类型只有int函数返回值和参数也都是int但足够表达任何可计算函数。控制流只留if/else和while表达式支持四则运算、取模、位运算、比较和逻辑与或非。数组用全局数组和栈上定长数组两种方式支持结构体、指针算术、switch、for循环这类高级特性全部砍掉。这个子集看着简单但有一个隐性门槛你必须接受“没有指针也能写编译器”这个事实。编译器的核心数据结构是语法树没有指针就得用数组下标模拟指针比如用全局节点池索引来表示树节点。BSC源码里我不停地写int left; int right;这样的节点索引字段硬是用数组把AST、符号表、栈帧管理全部实现出来了。2.2 种子编译器架构单遍还是多遍经典的迷你编译器大多用“词法分析-语法分析-代码生成”三件套有人会把语义分析插在里面。我一开始贪图简单用单遍编译边解析边生成汇编后来发现教训很大。原因在于BSC支持函数先调用后定义比如main里调用fib而fib写在main后面。单遍编译时函数调用点的偏移地址必须等目标函数体编译完才能确定这就逼着你先做符号收集再做代码生成要么就得生成跳转占位符再回填。我在第一版单遍实现里靠“两遍伪单遍”解决第一遍先扫描所有函数声明建立起符号表第二遍才做词法语法生成调用点直接用符号表里的函数序号生成jal指令具体地址交给汇编器处理。虽然最终能用但代码里到处是补丁逻辑维护起来很心累。如果这次重新做我会直接选用经典多遍架构词法分析把源码切成token流语法分析构建AST语义分析建符号表并做类型检查最后代码生成遍历AST发射汇编。多一遍处理有利于逐步排查问题尤其在后面做字节级对拍时AST的中间表示能帮你快速定位是哪一阶段出了差异。2.3 种子编译器的代码生成策略代码生成我采用的是朴素栈机模型不做寄存器分配。每个表达式求值都走“压栈-运算-弹栈”的路径所有的临时变量都在栈上分配固定偏移。比如a b会生成lw t0, -4(s0) # 加载a addi sp, sp, -4 sw t0, 0(sp) # 压栈 lw t0, -8(s0) # 加载b addi sp, sp, -4 sw t0, 0(sp) # 压栈 lw t0, 0(sp) # 弹b addi sp, sp, 4 lw t1, 0(sp) # 弹a addi sp, sp, 4 add t2, t1, t0 addi sp, sp, -4 sw t2, 0(sp) # 结果压栈每个局部变量在栈帧里都有固定偏移函数入口一次addi sp, sp, -N分配好栈空间退出时恢复。虽然生成的汇编冗余度很高但胜在逻辑直接几乎不可能出错。对于种子编译器来说可验证性比运行效率重要得多。反正我们后面要自举等第二版编译器做寄存器分配也来得及。2.4 种子编译器验证冒烟测试和自举测试种子编译器写好之后我先用一组冒烟测试用例验证基本语法和代码生成。比如阶乘、斐波那契、素数判断这类经典函数每个用例都先拿gcc编译一遍生成期望输出再用bsc0跑一遍同样的BSC源码逐字节比对输出。这一步很关键因为如果种子编译器有问题后面所有自举环节的错误都会层层放大到时候根本分不清是种子编译器的锅还是BSC重写版的锅。冒烟测试全部通过后我做了第一次自举尝试用bsc0编译bsc-self.bsc。第一次运行时编译到第200多行就开始报语法错误查了半天发现是BSC的语法规则对“函数声明带数组参数”的处理有歧义而bsc-c能编是因为C编译器对空格和换行不敏感我的词法分析器却把换行当语句终止符了。这类“种子编译器过松、自举版本过严”的不一致问题后面还会遇到很多次。3. 二次编译用BSC自己编译它自己3.1 “自举编译器源码”怎么写才不会功亏一篑从C版种子编译器转向BSC版编译器源码核心工作不是翻译而是“换一种实现策略”。比如C语言里的指针和结构体在BSC里全得用“节点池索引”来模拟。我先定义了一个全局数组nodes每个节点用5个int槽位存储token类型、左右子节点索引、整型值、符号表索引。语法分析时每构建一个节点就往数组里追加5个int。这带来的思维转变很大但也很锻炼人。原来用node-left访问左子树在BSC里变成了nodes[left_idx 1]。一段简单的表达式a b * cAST构建逻辑大概长这样int make_binop(int op, int left, int right) { int idx node_count * NODE_SLOT_SIZE; nodes[idx 0] op; nodes[idx 1] left; nodes[idx 2] right; nodes[idx 3] 0; nodes[idx 4] 0; node_count node_count 1; return idx; }然后所有遍历AST的递归函数参数从“指针”变成“节点索引”。递归深度受栈大小限制而BSC函数每层栈帧固定分配空间所以深度不太可能溢栈扫描一个几千行的源码文件完全没问题。另一个大改动是错误处理。C语言里可以随时fprintf(stderr, ...)但BSC支持的系统调用很有限。我干脆给BSC加了一个内建函数print_i(int)和print_s(int)前者输出整数后者按字符串表索引输出字符串常量。这样编译器报错信息还能保留下来对调试帮助巨大但它必须是种子编译器固化的内建能力不能依赖库函数。3.2 二次编译的核心步骤解析整个二次编译流程我拆成三步走每一步都有一个明确的验证节点第一步把bsc-c.c里实现编译器的C源码手工翻译成bsc-self.bsc的BSC源码。这一步的难点在于语言特性映射而非算法逻辑。所有的struct变成全局数组所有malloc变成静态节点池分配所有printf变成内建打印函数。第二步用bsc0编译bsc-self.bsc生成bsc1可执行文件。这一步能否成功直接检验种子编译器对BSC语言子集的实现是否完整。任何语法或语义的实现缺失都会在这里暴露。第三步用bsc1编译bsc-self.bsc生成bsc2。然后对比bsc1和bsc2对同一份源文件的编译输出。如果两组输出一致说明编译器已经“锁定”了自己的语义不再依赖任何外部编译器。第二步和第三步的区别其实很微妙。bsc1是“用种子编译器编译出来的BSC编译器”它还不是完全意义上的自举bsc2是“用BSC编译器编译出来的BSC编译器”自举链闭合了。当我第一次在终端里跑通三步看到bsc1和bsc2编译同一份代码输出完全一致时那种“递归成功落地”的感觉确实很微妙。3.3 二次编译过程中的典型坑点这里必须记录三个非常典型的翻车现场。第一个是符号表容量问题。BSC里我把符号表设计成固定数组初始容量只有256。C版种子编译器跑小型测试没问题但编译bsc-self.bsc这种4300行的源码时符号表直接溢出编译到一半数组越界生成一堆垃圾汇编。最后我把符号表改成动态扩容版本——容量不够时重新分配一个更大的全局数组并拷贝旧数据才解决。第二个是栈帧对齐问题。RISC-V要求栈指针16字节对齐但BSC编译器为每个局部变量分配的栈空间是按4字节来的函数参数和调用约定来回复制。当函数局部变量特别多、栈偏移累计不是16的倍数时调用call指令前栈指针没对齐程序跑着跑着就段错误。我在生成函数序言时增加了一个对齐修正先把栈帧大小向上取整到16的倍数再按数组编址。第三个是数组下标和函数参数传递顺序问题。C语言里函数参数的求值顺序是未定义的但BSC必须把它定死。我在BSP里规定参数从右往左压栈因此f(g(1), h(2))会先调用h再调用g。如果重写时没保持这个顺序某些副作用相关的调用就会产生不同结果字节级对拍也会对不上。3.4 二次编译的里程碑判定关于“二次编译到底成了没成”我自己有四个判定标准依次递进bsc1能够成功编译bsc-self.bsc不报错不崩溃。bsc1编译产出的bsc2可执行文件能够正确运行测试用例输出结果与bsc0一致。bsc2再次编译bsc-self.bsc产出bsc3功能表现与bsc2一致。进一步做字节级对拍把bsc2和bsc3编译同一份源码生成的汇编文件做逐字节比较。到第4步基本可以宣告自举成功。我实际跑下来在第2步就遇到过bsc1编译出来的可执行文件能跑但输出错乱的问题那就是某个基础语义翻译错了并不是自举失败只是需要回到重写源码里修bug。4. 字节级对拍如何验证两代编译器完全一致4.1 对拍的目标和方法论“字节级对拍”听起来高深说白了就是同一份输入用两套流程分别处理最后对比产物。区别在于普通对比的是运行结果我们对比的是生成的汇编文件每个字节都要一样。为什么要求字节级一致因为如果一个编译器自举成功了理论上它的行为和产生它的那个编译器应当完全等价。等价的意思不是“跑同一个测试用例结果相同”而是“对任意输入产出的输出都相同”。后者比前者严格得多也更能反映编译器实现的确定性。当然这里有一个现实前提汇编器版本、连接器版本、编译选项、源码文件路径这些环境因素必须保持一致否则即使编译器行为完全相同字节也会因为文件路径注释不同而对不上。所以我的对拍流程固定为riscv64-linux-gnu-as -o out1.o out1.s riscv64-linux-gnu-ld -o prog1 out1.o -lc riscv64-linux-gnu-as -o out2.o out2.s riscv64-linux-gnu-ld -o prog2 out2.o -lc汇编和连接阶段使用完全相同的工具和参数确保差异只可能来自编译器前端和代码生成环节。4.2 对拍代码怎么组织我写了一个Python脚本用法很简单传入两个汇编文件路径脚本先做一次归一化再去掉明显非语义噪声的差异最后逐字节比较。脚本核心逻辑长这样import sys import re def normalize(path): with open(path, r, encodingutf-8) as f: lines f.readlines() out [] for line in lines: line line.strip() # 去掉注释 line re.sub(r#.*$, , line).strip() # 统一空白符 line re.sub(r\s, , line) # 去掉某些汇编器生成的伪指令注释 out.append(line) return out def compare(path1, path2): a normalize(path1) b normalize(path2) if len(a) ! len(b): return False, f行数不同: {len(a)} vs {len(b)} for i, (la, lb) in enumerate(zip(a, b)): if la ! lb: return False, f第{i1}行不同:\n a: {la}\n b: {lb} return True, 完全一致 if __name__ __main__: path1, path2 sys.argv[1], sys.argv[2] ok, msg compare(path1, path2) print(msg) sys.exit(0 if ok else 1)注意这里的“字节级”其实是以文本为单位做了空白归一化因为汇编格式本身会有空格差异。如果你要做真正意义上的字节级那就直接对二进制可执行文件做cmp但那会把汇编器版本差异也卷进来我倾向于先做汇编文本级别的严格对比再做一次功能对拍双保险。4.3 常见差异来源逐个击破在第一次跑对拍时脚本很快就报出大量差异。我一口气列了四个来源。第一类是头注释差异。汇编文件顶部会带有生成工具的标识比如.file foo.bsc。如果源码路径不同或者汇编器版本不同这里就会出现差异。解决办法是对拍前先把这类行过滤掉。第二类是布局差异里最恶心的“标签顺序不同”。两代编译器在遍历AST生成代码时如果遍历顺序不一致输出的标签编号和摆放位置就会错位。语法上两段汇编做的事情完全一样但标签名对不上。遇到这种问题我会先跑一次功能对拍确认行为一致再接受“标签顺序不同但在语义上等价”的结果同时去重写源码里查是不是某处遍历顺序混了。第三类是地址偏移差异。如果代码生成对栈帧偏移的分配顺序不同sw t0, -4(s0)会变成sw t0, -8(s0)。这种差异几乎可以断定是编译器内部某个序贯逻辑不一致必须修复。因为我用的是固定栈帧分配方式每个变量在符号表里的偏移是确定性的正常不该出现随机偏移。第四类是伪指令展开差异。RISC-V的li伪指令会被汇编器展开成多条指令比如加载大常数时可能变成luiaddi也可能变成li一条。不同编译器版本的展开策略不同但我对拍的是同一个汇编器所以这条更多是提醒大家不要在环境不同的时候做严格对拍否则纯属浪费时间。4.4 对拍之后功能验证也不能省字节级对拍通过只能说明“两代编译器对这份源码产生了相同的汇编”。要证明编译器对任意BSC源码都等价理论上需要穷举实际不可能。所以我额外准备了一个“大杂烩测试套件”包含50多个测试用例覆盖算术、函数调用、递归、数组、while循环、嵌套函数调用、全局变量等每个用例都用bsc1和bsc2分别编译运行比对运行输出。这里有个很深的体会字节级对拍强在“确定性验证”功能对拍强在“正确性验证”两者结合才不会漏掉问题。比如有一段代码如果编译器的循环条件比较方向反转汇编文本可能能对上因为都是同样的错误但运行结果会错。所以每次对拍通过后我还会用套件跑一遍确保运行输出和gcc版本一致。5. 常见问题与排查技巧实录5.1 自举失败排查思路树我总结了整个实战过程中遇到的所有问题把它们组织成一张排查思路树给大家一个参考如果bsc0连种子编译器源码都编不过问题几乎一定在C语言版编译器对BSC子集的定义有缺陷。仔细检查是否在语法分析里漏了某个符号比如、||、%。如果bsc0编bsc-self.bsc报语法错误先怀疑源码里的语法是否符合BSC规范再怀疑词法分析器对空白符、换行符的处理边界。如果编译通过但生成的可执行文件一运行就段错误优先检查栈帧已对齐、数组越界、符号表是否溢出。如果编译结果能运行但输出错乱八成是代码生成时变量偏移或算术运算顺序出错。如果字节级对拍差异集中在标签名或注释忽略差异检查语义等价性如果差异集中在指令本身老老实实从汇编反推编译器逻辑错在哪。5.2 数组池的坑固定容量还是动态扩容前面提到符号表固定容量的问题这里单独拿出来再说一次。编译器处理的数据规模往往在运行前不可预知。写种子编译器时贪方便用了固定大小的节点池和符号表前期测试完全够用直到编译源码量上来才发现数组越界。我的解决方案是把节点池和符号表都做成“满则翻倍”的动态数组。BSC里没有realloc我就在代码里实现int grow_pool(int old_cap)申请一块新的大数组手动把旧数据逐项拷过去再更新全局池指针和容量变量。这本质上是把C的realloc逻辑翻译成BSC写法不算复杂但非常容易写错下标偏移建议每一步都加断言。5.3 调试技巧从汇编反向定位源码逻辑错误编译器出bug之后最痛苦的是从几千行源码里找那个逻辑错误。我试过加打印、单步调试最后还是觉得“从汇编反向定位”最有效率。方法是构造一个最简测试用例比如int f(int x){ return x 1; }然后用出问题的编译器编译它打开生成的汇编文件人工走一遍每一条指令和预期对照。有一次发现x 1生成了sub指令而不是add立刻意识到是表达式节点构建时操作符类别映射写反了。还有一次比较运算a b生成的汇编用的是bge跳转也就是说条件逻辑反转了回去一查是AST里比较节点的左右子树在遍历时被交换了。这种问题靠打印输出很难看出来但盯汇编一分钟就能定位。5.4 保留“中间产物”比想象中重要我还有一个习惯就是每轮编译都把中间文件留下来源码、词法token输出、AST dump、生成的汇编、最终可执行文件按阶段分开存。用脚本一键生成全套方便对拍时快速排查。具体来说bsc-self.bsc编译时我可以加一个--dump-tokens和--dump-ast选项打印出中间状态。种子编译器阶段我没做这两个选项结果自举失败时只能看汇编猜原因效率很低。到了BSC重写版我特意把这两个dump选项实现进去调试成本一下子降了很多。强烈建议每个编译器项目都保留中间产物输出能力哪怕只是开发期选项。写在最后的几个实操心得整个自举项目做下来我最大的感触是编译器自举真正考验的不是编译原理知识而是对“确定性与一致性”的偏执追求。代码生成器里一个毫不起眼的遍历顺序选择在单次编译时根本看不出区别一旦进入字节级对拍就会变成刺眼的差异。如果现在让我精简成三条建议我会这么说第一种子编译器宁可慢、宁可丑也要做到逻辑绝对简单因为它是一切正确性的根基第二尽早做字节级对拍框架不要等到自举链路完全跑通才验证每一阶段对拍一次能帮你把问题牢牢锁在小范围内第三为每一代编译器保留可完全复现的构建环境和中间产物让每次自举都有迹可循。后续我还打算把手上的BSC子集扩展到支持结构体和指针然后试着让编译器生成优化后的汇编再用同一个自举链路跑一遍字节级对拍。这个过程一旦打通就等于握住了编译器开发的“可重复验证”武器以后任何改动都有把握不会搞坏基础能力。也建议对这块感兴趣的人从你熟悉的架构开始哪怕只是做一个能编译自己子集的小玩具也值得走完这条链路——它带来的收获绝对不只是一份能跑起来的编译器那么简单。