很多朋友一听到“写编译器”三个字第一反应就是“这是大佬做的事”。但我自己把这个项目走完之后最大的感受是编译器不过是一条流水线只要有人把每个环节拆开你就能跟着走一遍。这篇博文记录了我从零实现一个C 子集编译器的完整过程目标很明确把一份看着像 C 的源码变成能在自己设计的虚拟机上运行的字节码。适合正在学编译原理、想做点硬核项目却不知道怎么下手的同学也适合报着“我想彻底搞懂程序本质”这个念头的非科班开发者。看完之后你会发现编译器并没有你想的那么高不可攀。1. 项目概述从零写编译器的整体思路1.1 为什么选择 C 子集作为目标真正的 C 语言标准非常庞大光是类型系统、结构体、指针、预处理、存储修饰符这些东西就能让一个团队忙上几年。我给自己定了一个极简的目标语言只保留 int 整数类型、函数定义与调用、全局/局部变量、if/else、while、return再加上最基本的四则运算、比较运算和括号表达式。这些特性组合起来已经能让编译器碰到所有核心难题。为什么这样选因为“麻雀虽小五脏俱全”。只要支持函数调用就必须处理调用栈、返回地址和参数传递只要支持局部变量就必须做作用域管理和符号查找只要支持控制流就必须解决跳转指令的生成和标签回填。可以说把这一圈走完编译器的骨架已经立起来了。而砍掉指针和结构体这类特性又不会让工作量大到一个人扛不住。我建议所有想体验编译器开发的人也从这种“可编程的最小语言”起步。不是 C 太小而是我们不需要为了练手去对抗语言规范里的历史包袱。一个能跑斐波那契数列、能算最大公约数的语言已经完全值得叫“编译器”了。1.2 整体架构与编译流水线编译器的经典四阶段架构在我这个项目里体现得很直白词法分析、语法分析、语义分析、代码生成。每一步的输入输出都非常明确。阶段输入输出核心要解决的问题词法分析原始源码字符串Token 流如何把字符流切成有意义的单词语法分析Token 流抽象语法树 AST如何把单词序列还原成语法结构语义分析抽象语法树 AST带符号表信息的标注树如何保证变量、函数使用合法代码生成语义检查过的 AST三地址码/字节码如何把结构化的树展开为线性指令这里我个人最喜欢的一种理解方式编译过程就是信息逐步降级的过程。源码里既有“什么是变量”又有“变量怎么使用”的信息经过词法分析之后变成 TokenToken 仍然保留部分词法细节到了 AST语法层面的嵌套关系被彻底固定再到三地址码连嵌套都没了变成一串线性指令。每一层都在丢弃无关信息、保留对下一层有用的信息。用生活类比解释一下这不像是翻译一篇文章更像是把一座房子从设计蓝图缩小到结构骨架再缩小到砖和钢筋的采购清单。每条指令就是一个零件编译器的责任就是保证零件之间能严丝合缝地组装。1.3 语言特性边界与示例程序我的 C 子集正式名字就叫“MiniC”。支持的内容包括基本数据类型只保留 int函数返回类型也只有 int 和 void函数支持参数列表支持递归调用语句支持变量声明、赋值、表达式语句、if/else、while、return、花括号代码块表达式支持 、-、*、/、% 以及 、、、、、!支持括号改变优先级支持// 行注释和 /* 块注释 */为了贯穿全篇讲解我会反复用下面这个求斐波那契数列的程序作为示例。int fib(int n) { if (n 1) { return n; } return fib(n - 1) fib(n - 2); } int main() { int result; result fib(10); return result; }2. 词法分析器让源码变成 Token 流2.1 Token 的类型划分与定义词法分析是所有后续阶段的源头不管多漂亮的语法树都要从这段把字符切词的工作开始。我第一版犯过一个大错误把 Token 结构设计得太简陋只保存了类型和文本值没保存行列号。结果后期报错时只能写出“语法错误”写不出“第 5 行第 3 列附近发生了什么”调试体验简直灾难。Token 至少要包含这几项类型、文本、所在行、所在列。类型上我做了一个枚举总共就十几种绝不贪多Token 类型说明示例IDENT标识符fib、result、nKEYWORD关键字int、if、else、while、returnINT_LITERAL整数常量10、2、0OPERATOR运算符、-、*、/、、PUNCT分隔符(、) 、{、}、;、,EOF文件结束标记无这里的 KEYWORD 和 IDENT 在词法规则上是同一类东西都是字母开头的字母数字串。区别只是查一下关键字表之后归类不同。我维护了一张哈希表把 int、if、else、while、return、void 放进去看到标识符后先查这张表查到就是 KEYWORD查不到就是 IDENT。在 C 语言里定义 Token 结构大致长这样typedef struct Token { TokenType type; const char *text; int line; int column; } Token;代码生成阶段最终会用到文本但词法分析阶段必须把它保留下来否则后续根本无法知道变量的真实名字。2.2 手写词法分析器的状态机实践有没有必要使用 lex/flex 这类工具有必要但不适合学习阶段。自动生成器会掩盖太多细节一旦生成的代码出了问题你连排查入口都找不到。手写词法分析器其实一点都不难本质就是一个字符级的状态机读一个字符判断这个字符属于数字、字母还是符号再决定进入哪个状态。我大致是这样组织的外层循环不断调用 nextToken()内部维护一个当前读取位置。遇到空白字符就跳过但行号要跟着换行符累积。遇到数字就不断读取直到非数字字符然后用 strtol 或者手写转换变成整数。遇到字母或下划线就不断读取直到非字母数字字符然后查关键字表。遇到运算符时要做最长匹配比如看到 之后还得再看下一个字符是不是 如果是就得到 在我的 MiniC 里不支持 但至少要准备这个逻辑否则以后扩展语法时会被卡住。核心逻辑可以浓缩为这样一段代码Token nextToken() { skipWhitespaceAndComments(); if (*src \0) return makeToken(T_EOF, , line, col); if (isdigit(*src)) return scanNumber(); if (isalpha(*src) || *src _) return scanIdentifierOrKeyword(); return scanOperator(); }词法分析器的代码量通常只有三四百行但它值得你好好打磨。我后来把注释处理也放到这里因为从语法角度看注释就是空白。处理跨行注释时尤其要注意换行符它会改变行号。我刚开始没处理导致某个错误始终报错到错误的行排查了很久。2.3 词法分析阶段的调试技巧写完词法分析器之后我最先做的不是继续往下写而是先写一个 dumpTokens 函数把 Token 流一行一个地打出来。每种 Token 用不同前缀加文本显示例如IDENT(fib)、INT_LITERAL(10)、OPERATOR()。跑一遍示例程序确认输出的每个 Token 都在正确顺序上再往下推进。这个习惯帮我规避了大量没必要的排查。很多所谓“语法分析出错”的情况其实是词法阶段就把 Token 切错了。比如 10x 这种写法严谨的编译器应该报错我第一版却会把它切成 INT_LITERAL(10) 加上 IDENT(x)后面语法怎么分析都会莫名其妙。后来我加一个检查数字后面紧跟字母就报词法错误。所以词法分析器也要验证一个小小疏忽会在后级阶段被放大成诡异的问题。3. 语法分析从 Token 流到抽象语法树3.1 为什么要选择递归下降法语法分析的方法总体分两类一类是自底向上的 LR/LALR典型工具有 yacc/bison另一类是自顶向下的递归下降。我选择的是递归下降原因很简单它和你书写的文法规则是一一对应的几乎不需要理解状态机跳转写起来就像在描述语法本身。递归下降法最大的坑在于左递归。如果文法里写着expr - expr term翻译成递归函数就会无限调用自身。解决办法有两个一是在文法层面改写为循环二是用 Pratt 解析法处理表达式。对于表达式层次我用了 Pratt 解析因为它处理优先级和结合性更优雅。什么叫 Pratt 解析你可以想象成每个运算符带一个“绑定力量值”数字越大绑定越紧。解析表达式时Parser 从左往右拿运算符并和当前最大绑定力量比较如果遇到更紧的运算符就递归解析右侧。这种方式替代了一层层嵌套函数调用特别适合处理加减乘除、比较运算这类优先级明确的场景。下面是一段简化核心int expr(int minPrecedence) { Node *left parseUnary(); while (true) { Operator op peekOperator(); if (op.precedence minPrecedence) break; advance(); Node *right expr(op.precedence 1); left makeBinOpNode(op, left, right); } return left; }3.2 表达式优先级与文法设计MiniC 的表达式优先级从低到高通常是这样安排的优先级运算符结合性最低右结合较低||左结合低左结合中等 !左结合略高 左结合高 -左结合更高* / %左结合最高! -一元右结合最高( ) 函数调用左结合注意赋值是右结合所以a b 10应当被理解为a (b 10)。在 Pratt 解析里这只需要把赋值运算符的递归最小优先级设为当前优先级而不是加一即可。我写出的文法简化如下program : function* function : type IDENT ( param_list ) block param_list : (type IDENT (, type IDENT)*)? block : { statement* } statement : var_decl | assignment ; | if ( expr ) statement (else statement)? | while ( expr ) statement | return expr? ; | block var_decl : type IDENT ; expr : assignment assignment : logical_or ( assignment)?这套文法把语句和表达式清晰地分开。我始终记住一个原则语法分析器的职责是判断“结构是否符合语法”而“变量是否声明过”这是语义分析阶段的事。两边别混在一起不然 Parser 越写越乱错误信息也不好报。3.3 AST 节点设计与全流程串联AST 是我整个项目里最重要的数据结构。每个节点都带有类型、行号、子节点指针。定义大致如下typedef enum { N_PROGRAM, N_FUNC_DEF, N_BLOCK, N_VAR_DECL, N_ASSIGN, N_IF, N_WHILE, N_RETURN, N_CALL, N_BINOP, N_UNOP, N_INT_CONST, N_IDENT } NodeType; typedef struct Node { NodeType type; int line; union { struct { char *name; Node *param_list; Node *body; } func; struct { Node *cond; Node *then; Node *else; } if_s; struct { char *name; Node *args; } call; struct { char *op; Node *left; Node *right; } binop; struct { int value; } int_val; struct { char *name; } ident; } data; struct Node **children; } Node;不同节点存储的内容差别很大所以用 union 来节省空间是常见做法但代价是访问时你得一直惦记着当前节点的类型。我为了调试方便额外写了一个 printAST 函数把 AST 以缩进树的形式打印出来。这个函数的作用在后面测试中远超预期很多逻辑问题用肉眼看 AST 一眼就能定位。例如result fib(10) 1;这行代码经过语法分析后AST 尾部会呈现这种结构ASSIGN IDENT(result) BINOP() CALL(fib, ARGS[INT(10)]) INT(1)把 AST 打印出来再往下写语法分析阶段的信心会瞬间提高很多。没人愿意靠猜去推进语义分析。4. 语义分析与符号表让程序变得有意义4.1 符号表的结构与作用域管理语法分析只保证“形状正确”但像“变量 result 在声明之前就被使用”这种错误语法分析根本发现不了语义分析就是在这里登场。核心数据结构就一个字表。我实现了一张符号表每个符号包含名字、类型、作用域层级、以及后续代码生成需要的栈偏移。作用域管理是语义分析的重点。MiniC 的作用域规则是这样的最外层是全局作用域每个函数体内部是一个局部作用域函数参数也属于这个局部作用域。如果出现嵌套代码块就再往里推一层。为了处理嵌套我使用了链式作用域栈typedef struct Symbol { char *name; Type type; int scope_level; int stack_offset; struct Symbol *next; } Symbol; typedef struct Scope { struct Scope *parent; Symbol *symbols; } Scope;查找符号时先查当前作用域查不到就去 parent 继续向上查声明新变量时则只插入当前作用域链表的头部。这样天然实现了变量的遮蔽内层声明了一个同名变量外层那个就被暂时盖住了。我在第一次实现时犯了一个低级错误符号表用单层哈希表没有按作用域分层导致全局变量和局部变量同名时互相覆盖。测试程序跑出来的结果匪夷所思最后加了一个 printSymbolTable 函数把每个作用域里的变量打出来问题一目了然。4.2 类型检查与常见语义错误MiniC 只有一个 int 类型所以类型检查工作看起来少但依然有几个必须检查的点凡是出现在表达式里的标识符必须能在符号表中查找到同一作用域内不允许重复声明同一个变量函数调用时实参个数必须和形参个数一致return 语句所在的函数类型如果是 void则不能返回整数赋值运算符左值必须是变量不能是表达式最开始我漏掉了实参个数检查。某次测试时调用 fib(10, 20) 竟然顺利编译通过代码生成阶段把第一个参数放到栈上第二个参数也放了函数返回时栈帧弹出数量对不上运行时直接崩溃。加了参数个数检查之后这类问题直接变成编译期可诊断的错误。语义分析阶段还要顺便做一件事给每个局部变量分配栈偏移。变量声明顺序决定偏移量符号表里记录好这个值代码生成时就能直接生成“往相对栈顶第几个位置存”的指令。这一步如果在语法分析阶段做会遇到函数嵌套时的顺序混乱所以放在作用域创建之后统一处理更合理。5. 代码生成与运行时把 AST 变成可执行的东西5.1 为什么选择三地址码作为中间表示到这里我们有了合法的 AST接下来就是把它变成真正可运行的东西。这个环节选择很多可以直接生成 x86-64 汇编可以生成 C 语言再交给本机编译器也可以生成自定义的字节码交给虚拟机执行。我选择了三地址码加大虚拟机。直接生成 x86-64 汇编看上去最硬核但说实话汇编指令集里的寄存器分配、调用约定、栈对齐问题每一样都能让人写崩溃。如果目标是理解编译器逻辑而不是修炼汇编内功三地址码是性价比最高的选择。三地址码的特点是一条指令最多只有一个运算操作和三个地址比如t2 t1 * 3。它很像汇编但没有寄存器数量和指令约束的问题用编号 0、1、2 表示临时变量无限个数。之后再把它翻译成虚拟机字节码或者汇编或者直接边解释边执行都是可行的。我最终的做法是先生成三地址码指令列表然后交给一个简单的栈式虚拟机执行。这个虚拟机会模拟函数调用栈运行结束后返回结果。5.2 从 AST 生成三地址码的规则三地址码的指令集我总共定义了大约 20 种指令含义LOAD_CONST result, value把常量加载到临时变量COPY result, source复制源变量ADD result, a, b结果 a bSUB result, a, b结果 a - bMUL result, a, b结果 a * bDIV result, a, b结果 a / bLT/LE/GT/GE result, a, b比较指令结果为 0 或 1GOTO label无条件跳转IFFALSE cond, label条件为假则跳转CALL result, func, argc函数调用结果存入 resultPARAM value压入实参供 CALL 使用RET value返回值并退出函数从 AST 生成三地址码本质是对树做后序遍历。先递归生成左子树的指令把结果放到临时变量 t1再递归生成右子树的指令结果放到 t2最后生成一条加法指令ADD t3, t1, t2。这个规则简单到接近机械但正是这种机械性保证了正确性。表达式fib(n - 1) fib(n - 2)可能生成类似如下的三地址码LOAD_CONST t1, 1 SUB t2, n, t1 PARAM t2 CALL t3, fib, 1 LOAD_CONST t4, 2 SUB t5, n, t4 PARAM t5 CALL t6, fib, 1 ADD t7, t3, t6控制流的翻译是最有意思的部分。if 和 while 都需要用到标签。比如 while 循环通常是这样翻译的L_begin: 条件求值到 t1 IFFALSE t1, L_end 循环体语句 GOTO L_begin L_end:因为跳转目标常常是后面才确定的我需要用“标签回填”技术先生成一个空跳转指令等知道目标位置后再把指令里的标签参数补齐。语法分析阶段的 AST 结构在这里起到了决定性作用没有它你根本不知道什么时候该发 GOTO 回去。5.3 函数调用的运行时链接与栈帧函数调用是代码生成阶段最大的难点没有第二个。每调用一次函数就要为一个新的栈帧分配内存。我的虚拟机栈帧布局如下地址内容栈帧顶部 8返回地址虚拟机程序计数器栈帧顶部 4保存的调用者栈基址栈帧顶部 0第一个局部变量按偏移递减...局部变量区栈帧底部实参列表从 CALL 前推入调用前会先执行若干 PARAM 指令把实参压入栈然后执行 CALL。CALL 指令的职责是保存当前程序计数器作为返回地址保存当前栈基址然后建立新的栈帧跳转到函数的入口。函数末尾执行 RET 时取出返回值恢复调用者的栈基址和程序计数器完成返回。这里的参数顺序要特别注意。MiniC 的调用约定是参数从左往右压栈但栈是向下增长的因此最后一个参数在最栈顶。函数体内访问参数时需要以栈基址加上固定偏移。如果这里搞反拿到的参数顺序会完全颠倒。运行时还能做一层保护检查栈指针是否超过预设的最大值并在报告溢出。递归函数很容易触发栈溢出有了这个检查出现死递归时至少报错信息清晰不会整个虚拟机上崩掉。虚拟机本身我用 C 语言实现代码量零零总总不到 500 行但跑起斐波那契数列毫无压力。6. 实测与调试中的那些坑6.1 最常见的几个问题与排查方式写编译器一定会经历大量奇怪的失败。我把自己掉进去的坑总结成一份速查表后面遇到同类问题可以直接对照现象可能原因解决办法所有 Token 行号都偏移词法阶段跨行注释没更新行号在注释处理循环里遇到 \n 就 line表达式运算结果完全错误优先级处理不对打印 AST检查加减和乘除的嵌套关系变量赋值没生效语义阶段栈偏移没有记录打印符号表里每个变量的偏移量函数递归调用无限循环进入函数体前栈帧没有分配检查 CALL 指令是否创建新栈帧条件判断体永远不执行IFFALSE 和 IFTRUE 写反单步跟踪第一条控制流指令的跳转目标return 值拿不到RET 指令把返回值放到错误位置检查栈帧恢复顺序防止覆盖返回值局部变量互相串值两个变量分配到了相同偏移确认符号表是否按作用域分层管理这些问题里最难的其实是第一种和最后一种。词法阶段的错误会在后续阶段放大成特别诡异的症状而作用域分层不够清晰的错误往往只在你跑多级函数调用时才暴露。所以我强烈建议在写代码生成之前就先把符号表相关逻辑彻底验证一遍。6.2 调试手段多打印分阶段验证编译器开发者最趁手的调试工具不是 debugger而是 print。我给每个阶段都加了一个可开关的调试打印函数用环境变量控制开启关闭。词法阶段能打印 Token 流语法阶段能打印 AST 缩进树语义阶段能打印符号表代码生成阶段能打印三地址码指令序列。要排查问题时按需打开对应开关。开发顺序上也有一条很稳的路线第一步先实现整数常量和加减乘除表达式不要碰变量、不要碰控制流先确保表达式求值正确。第二步加变量声明和赋值这个时候符号表和栈偏移都能被充分测试。第三步加 if 和 while 控制流跳转逻辑都能在复杂语句结构下得到验证。最后一步才加函数调用。每完成一步就留一个测试用例比如计算 (10 - 4) * 3 / 2 的结果、计算 1 到 100 的累加、递归求斐波那契。这样每一层都有明确验证基准永远不会出现“代码全写完了但不知道问题在哪”的大爆炸式调试。我第一次写的时候直接一口气全部写完结果运行错误一片排查了一个晚上还找不到根因。后来把测试用例拆开一个阶段一个阶段验证发现真正的问题就藏在函数调用的栈帧分配里。分阶段开发长期看才是最快的路。最后再分享一个我印象很深的小技巧在语法分析器里遇到 unexpected token 时报错信息一定要包含当前 Token 的行列号、期望看到的符号、实际看到的符号。比如“希望在 while 头部看到 (但实际看到数字常量 0位于第 4 行第 9 列”。这种错误信息对人排查和自己排查都极其有价值不仅项目调试时能少走很多弯路以后回看代码维护时也会感激当初这个决定。写编译器这件事最大的收获不是“我会写语法分析器了”而是把程序运行的每一个环节从文本到机器指令完整地看了一遍。以前写高级语言感觉像隔着雾看灯写完这个项目之后感觉自己亲手把雾拨开了。如果你现在正对着编译原理教材发怵不妨试试我这个路线挑一个最小的语言子集把四阶段流水线走通再回头看书你会发现那些公式和名词突然都变得亲切起来。
