去年年底我给自己定了一个听起来有点疯狂的年度目标从零手写一个能编译 C 子集的编译器。不是去调现成的编译框架也不是照抄龙书里的伪代码而是把字符读取、词法分析、语法分析、语义检查、中间代码生成、运行时执行这条完整链路亲手走一遍。前后折腾了大概三个月最终产出了一个能在自定义虚拟机上运行的小型编译器能处理 int 和 float 变量、四则运算、比较和逻辑表达式、if/else、while 循环、函数定义与递归调用。这篇文章就把整个开发过程做一次完整复盘从为什么选 C 子集、如何设计架构到每个核心模块的实现细节和调试心得全部摊开来讲。如果你对编译器的印象停留在“龙书太难啃、写的玩具跑不起来”这个项目或许能帮你找到一条真正能从 0 开始并最终跑起来的路径。我要先强调一个定位问题这不是一篇论文复现而是给真实动手开发者的旅程记录。目标读者是有一定编程基础、想理解编译器工作原理却一直被理论门槛拦住的人。你看完能真正明白一个编译器是由哪些部件拼起来的、每个部件要解决什么核心问题以及我在实际开发过程中踩过的那些教科书里根本不会写出来的坑。1. 整体设计先想清楚要做一个什么样的编译器1.1 为什么选择 C 子集而不是直接写完整 C提到写编译器大多数人的第一反应是“完整支持 C 语言”但完整 C 的复杂度是初学者不可能短期吃下的。预处理指令、指针运算、结构体和联合体、类型系统细节、ABI 调用约定、栈帧布局、寄存器分配……任何一个模块单独拎出来都能让人研究好几个月。我最终决定把范围砍到刚好能学到东西又不至于劝退的边界支持的部分包括整数和浮点数两种基本类型、变量声明和赋值、算术和逻辑运算、if/else 条件分支、while 循环、函数的定义与调用、return 返回值、块作用域。明确不做的内容包括指针、数组、结构体、字符串、宏、多文件编译、指针运算和类型强制转换。这个边界我是反复权衡过的。保留函数和块作用域是为了让符号表、作用域管理和函数调用约定都能真实地跑一遍这些都是编译器的核心难点砍掉指针是因为涉及地址计算和类型系统的大幅扩张砍掉结构体则是为了避开内存布局和字段偏移的计算。老实说如果你能把这个范围内的东西做到完整、可靠你对编译器前中端运作的理解已经超过绝大多数只背过概念的开发者。1.2 经典三分层架构前端、后端与运行时整个项目我采用了教科书里的经典三段式架构但按照实际工作量做了重新配比前端负责把源码字符串拆成 Token再构造成抽象语法树 AST同时做作用域和类型检查。中间层负责把 AST 翻译成自定义的中间指令序列。这里我没有直接生成 x86 汇编而是设计了一套极简栈式虚拟机指令集。后端是一个用 C 写的解释型虚拟机加载指令序列后模拟执行。为什么选择这套方案而不是直接生成机器码原因很现实生成真实汇编需要安排寄存器、计算栈帧偏移、处理调用约这些工作会淹没编译器核心逻辑的学习。栈式虚拟机把表达式的计算变成简单的压栈和弹栈操作函数调用只需要一套运行栈管理机制理解成本低得多。生成中间指令后后续如果想移植到真实目标平台也只需要把指令翻译成对应平台汇编主体架构不用动。用生活化的类比来说前端像是一个翻译官负责读懂中文文章的结构和含义中间层像是把文章整理成一份带格式的笔记后端像是按照笔记内容实际朗读出来的人。三个部分职责清晰可以分开调试。2. 词法分析把字符流变成 Token 流2.1 Token 类型如何设计词法分析是编译器的第一道工序输入是源码字符串输出是一串有类型的单词单元也就是 Token。我的 Token 类型设计如下表所示Token 类型对应内容示例KEYWORD关键字int float if else while returnIDENTIFIER标识符a b main addValueNUMBER数值常量3 42 3.14OPERATOR运算符 - * / ! !PUNCTUATION分隔符( ) { } ; ,判断关键字和标识符的时候有个经典细节把很多新手绊倒关键字本质上就是标识符。我的实现方式是先按标识符规则读入完整字母序列然后查一张关键字表命中就是 KEYWORD否则就是 IDENTIFIER。这里不能边读边判断否则会把 “intx” 错误地拆成关键字“int”加标识符“x”必须遵循最长匹配原则先把完整的字母串读出来再判断类型。2.2 手写状态机的核心逻辑我没有用类似 Flex 的生成器而是手写了一个小的状态机。对于一个 C 子集手写词法分析器其实非常简单核心逻辑是逐字符循环根据当前累积内容和下一个字符决定是否结束当前 Token。Token nextToken() { skipWhitespaceAndComments(); char c getChar(); if (isAlpha(c)) { return readIdentifierOrKeyword(); } if (isDigit(c)) { return readNumber(); } return readOperatorOrPunctuator(); }其中 readIdentifierOrKeyword 的逻辑是不断读入字母、数字和下划线直到遇到非这些字符为止然后查关键字表返回对应类型。readNumber 要稍微复杂一点需要处理整数和浮点数Token readNumber() { while (isDigit(peekChar())) { advance(); } if (peekChar() .) { advance(); while (isDigit(peekChar())) { advance(); } return makeFloatToken(); } return makeIntToken(); }在写这个模块时最容易踩的坑是运算符的贪婪匹配。比如源码里出现 如果只读到大于一就返回 OPERATOR后面等于号就会被单独识别等于给语法分析器丢了一个不存在的 token。因此我专门在识别运算符的地方加了多字符匹配逻辑读取一个字符后如果它是 、、!、还要再尝试读下一个等号看看能否组合成 、、、!。2.3 错误定位每一处报错都要有行列号词法阶段的错误处理看似简单实际体验差异很大。最开始我遇到非法字符比如 时只会输出一句 “invalid character”后来写递归下降解释器的时候才发现问题错误信息不带位置根本没法定位。正确做法是每次读取字符时维护一个当前行号和列号报错时带上行号、列号和具体内容例如错误词法分析失败 [第3行, 第12列]无法识别字符 这个行列号还要一直传到语法分析和语义分析阶段。我的经验是在 Token 结构体里直接保存起始行列位置后续所有报错都引用对应 Token 的位置信息。输入行号这事看着琐碎但在代码量超过一千行之后它会把调试效率提升一个数量级。3. 语法分析递归下降与表达式优先级3.1 文法设计如何处理左递归语法分析阶段把 Token 流变成 AST。我选用了递归下降分析法原因很直接手写递归下降比 LR 分析直观得多每个语法规则对应一个解析函数遇到什么结构就调用什么函数调试时能准确看到栈轨迹对初学者非常友好。递归下降分析要求文法不能有左递归。以表达式为例教科书上最自然的文法可能是expr - expr term | term但这样的文法直接写递归函数时会死循环因为解析 expr 首先要解析 expr永远也走不到 term。我采用的经典解决方案是把左递归改写成右递归的循环形式expr - term ((|-) term)* term - factor ((*|/) factor)* factor - NUMBER | IDENTIFIER | (expr)对应到代码里就是每个解析函数先解析一个左操作数然后用 while 循环检查下一个 Token 是否属于当前运算符集合是则继续解析右操作数并生成新节点ASTNode *parseExpr() { ASTNode *node parseTerm(); while (currentTokenIs(PLUS) || currentTokenIs(MINUS)) { Token op getCurrentToken(); advance(); ASTNode *right parseTerm(); node createBinaryOpNode(op, node, right); } return node; }这套层级结构天然保证了运算符优先级乘除先于加减因为 parseExpr 会先调用 parseTerm而 parenthsis 的优先级则通过 factor 里对括号的递归调用实现。3.2 表达式优先级和结合性的细节在我设计的表达式中优先级层次从低到高排列如下逻辑或 ||逻辑与 等式运算符 !关系运算符 加减乘除一元负号括号和函数调用理论上每一层都需要一个独立的解析函数但这会让代码显得冗长。我实际采取的办法是用一个参数化的优先级爬升函数 parseExpr(int minPrecedence)把每个运算符绑定一个优先级数值统一处理所有二元运算typedef struct { int precedence; int leftAssoc; } OpInfo; OpInfo getOpInfo(Token op); ASTNode *parseExpr(int minPrec) { ASTNode *lhs parseUnary(); while (true) { Token op getCurrentToken(); OpInfo info getOpInfo(op); if (info.precedence minPrec) break; advance(); ASTNode *rhs parseExpr(info.leftAssoc ? info.precedence 1 : info.precedence); lhs createBinaryNode(op, lhs, rhs); } return lhs; }这个写法值得说明一下leftAssoc 表示左结合比如减法当解析右操作数时传入 precedence 1就能阻止把连续的 a - b - c 错误解析成 a - (b - c)。对于右结合运算符则在递归时不加 1。在我选择的 C 子集里所有二元运算符都是左结合但保留这个参数便于以后扩展。3.3 AST 节点如何设计AST 是整个编译器中流转的核心数据结构。我的节点定义非常朴素typedef enum { NODE_NUMBER, NODE_VARIABLE, NODE_BINARY_OP, NODE_IF_STMT, NODE_WHILE_STMT, NODE_ASSIGN_STMT, NODE_FUNC_CALL, NODE_FUNC_DEF, NODE_RETURN_STMT, NODE_BLOCK, } NodeKind; typedef struct ASTNode { NodeKind kind; Token token; // 对应的原始 token用于行号和值 struct ASTNode *left; struct ASTNode *right; struct ASTNode *body; // 语句块或参数列表 struct ASTNode *next; // 兄弟链 } ASTNode;使用统一节点结构的好处是内存管理简单、遍历方式统一坏处是需要频繁通过 kind 字段判断节点含义。实际开发里我为了省内存还考虑过分类型定义结构体但后来发现统一节点配合清晰的类型辅助函数反而更容易推进新手阶段不建议过度设计层级结构。语法分析阶段的调试建议每个解析函数入口输出当前 Token出口输出生成的节点摘要。这个日志在早期开发中能救你很多次命因为递归下降最怕的就是某个分支误吞 Token导致后续解析在错误位置报错。4. 语义分析与符号表管理4.1 作用域模型符号表栈的建立与弹出语法分析只能保证语句结构符合文法但无法知道变量 a 是否声明过、函数 add 的参数个数是否匹配。语义分析负责做这些检查核心数据结构是符号表。我采用作用域栈的方式管理符号表。全局符号表位于栈底每进入一个块或函数体压入一个新区块结束弹出当前区。查找变量时从栈顶向下逐层找声明变量时只在当前层插入。这个模型和现代编程语言的作用域规则一致。typedef struct Symbol { char *name; Type type; // TYPE_INT / TYPE_FLOAT int isFunction; int paramCount; Type *paramTypes; int slotIndex; // 运行时局部变量槽位 } Symbol; typedef struct Scope { struct Scope *parent; Symbol **symbols; int symbolCount; int capacity; } Scope; Scope *currentScope; Symbol *lookupSymbol(const char *name) { Scope *s currentScope; while (s) { for (int i 0; i s-symbolCount; i) { if (strcmp(s-symbols[i]-name, name) 0) { return s-symbols[i]; } } s s-parent; } return NULL; }这个阶段最容易出现的 bug 是作用域弹出时机错误。比如块结束的代码被写在语法分支的某个错误位置导致变量在块外仍可访问。我的经验是严格在 createBlock 和 leaveBlock 两个函数里处理作用域栈的压入与弹出不要在语法分析过程中临时手动操作符号表栈。4.2 类型检查的收益与成本我的 C 子集只有 int 和 float 两种类型类型检查表面上简单实际仍然要覆盖不少场景两个操作数类型是否匹配、算术结果是什么类型、函数实参和形参类型是否一致、return 表达式的类型是否和函数返回值类型一致、条件表达式是否能当逻辑判断使用。类型检查最核心的一件事是处理 int 和 float 混合运算。我最初想严格禁止混合运算任何类型不匹配直接报错但在写测试用例时发现太反直觉。最终采用的策略是当二元运算的两个操作数类型不同时把 int 隐式提升为 float且结果类型为 float。这样 1 2.5 合法而赋值时 float 赋给 int 需要额外报一个警告或错误。隐藏的类型提升逻辑会增加 AST 转换节点的复杂度但从使用者视角看更符合 C 语言的直觉。类型检查的调试技巧是把自己当成解释器手工模拟代码执行过程检查每个变量在每一条语句中的类型状态。我发现很多类型错误是符号表查空导致的——变量名拼错、作用域没压栈报错信息却是“类型不匹配”排查时会很困惑。因此报错信息一定要细分为“未声明变量”“重复声明”“类型不匹配”“参数数量错误”和“参数类型错误”不要把问题都揉在一条消息里。4.3 函数作用域与 return 语句的语义约束进入一个函数定义的语法树节点时我会先创建新的作用域这个作用域里存放函数名和参数变量之后解析函数体。函数体内遇到 return语义分析要检查两层约束当前是否处于函数体内部以及 return 表达式类型是否与函数返回类型一致。这两个检查看起来简单但在处理嵌套函数虽然我的子集不支持嵌套函数但支持函数体内有块和循环时需要用一个独立的栈记录当前正在解析的函数上下文。如果你在实现时只是设置一个全局变量 isInFunction那一旦函数 A 体内包含函数 B 的定义就会出错所以必须用函数上下文栈。虽然我的子集没有函数嵌套但这个设计为以后扩展埋了伏笔。另一个坑是 return 没有表达式时应该返回一个默认值。我规定返回值为 int 的函数必须 return 表达式返回类型为 void 的函数不允许 return 表达式但允许单独的 return;。语义分析阶段要把这些规则固化成明确的枚举错误码。5. 中间代码生成与虚拟机执行5.1 栈式虚拟机指令集设计中间代码生成是前端 AST 与后端执行之间的桥梁。我设计了一套 16 条指令的栈式虚拟机指令集指令参数含义LOAD_CONST浮点值把常量压栈LOAD_VAR槽位索引读取局部变量并压栈STORE_VAR槽位索引弹出栈顶并存入指定槽位ADD SUB MUL DIV无弹出两个值计算结果压栈LT无比较弹出 a,b压入 b aEQ无比较弹出 a,b压入 a bJMP目标偏移无条件跳转JZ目标偏移弹出栈顶若为 0 跳转CALL函数索引调用指定编号函数RET无从当前函数返回PRINT无弹出栈顶并输出为什么用槽位索引而不是变量名因为中间指令面向运行时变量名在符号表里已经处理过了运行时只关心变量存在哪里。每个函数在进入时被分配一组局部变量槽位函数调用时槽位通过运行时栈管理。选择栈式而不是寄存器式对初学者的好处是巨大的。表达式树的每个节点自然对应一条或几条压栈弹栈操作几乎不需要额外优化就能得到正确的可执行代码。5.2 从 AST 生成指令的核心算法生成指令的过程本质上是对 AST 做一次深度优先遍历。表达式节点的代码生成极有规律先递归生成左子树的指令再递归生成右子树最后根据节点运算符输出一条对应指令。void genExpr(ASTNode *node, CodeBuffer *buf) { if (node-kind NODE_NUMBER) { emit(buf, LOAD_CONST, node-token.value); return; } if (node-kind NODE_VARIABLE) { emit(buf, LOAD_VAR, getSlotIndex(node-token.name)); return; } if (node-kind NODE_BINARY_OP) { genExpr(node-left, buf); genExpr(node-right, buf); emit(buf, opToInstruction(node-token.type), NULL); return; } }控制和循环结构的指令生成稍微花些心思。if/else 的典型模式是计算条件表达式 JZ 到 else_label 执行 then 分支指令 JMP 到 end_label else_label: 执行 else 分支指令 end_label:while 循环则是对照跳转执行完循环体后跳回条件计算的位置loop_label: 计算条件表达式 JZ 到 end_label 执行循环体 JMP 到 loop_label end_label:生成跳转指令的最大痛点是目标偏移未知。我用的是两遍解法先生成指令但把跳转目标位置留空并记录当前指令序号和需要回填的指令序号第一遍完成后再根据标签位置回填跳转偏移。这段逻辑不复杂但面对嵌套 if/while 时很容易搞混哪个 JMP 回填到哪我建议先写一个简单的 Label 结构体统一管理。5.3 运行时函数调用约定运行时用的是一个以“帧”为单位的调用栈。每个帧包含函数的返回地址、调用前的栈底指针和该函数的局部变量槽位。调用指令 CALL 的执行流程找到函数在函数表里的索引。把参数逐个从操作数栈弹出放入新帧的局部变量槽位。记录当前指令指针压入新帧。将指令指针切换到函数体起始位置。执行到 RET 时从当前帧获取返回值并存到一个全局寄存器弹出当前帧恢复调用方的指令指针再把返回值压入操作数栈。这个过程和真实 CPU 的函数调用非常相似区别是我用数组模拟内存用 index 模拟栈指针。第一次实现函数调用时我卡了很久原因是新帧中的局部变量槽位和参数槽位没有正确对应导致函数内访问参数得到的是上一个函数遗留下的变量。后来我干脆在函数调用流程中手动打印整个栈帧的内容才定位到帧创建顺序错了必须先开新帧再把参数写入槽位否则参数写入后开新帧会被覆盖。即使手写栈式虚拟机性能依然能跑得动几十个函数的递归计算因为每秒钟最多处理数万条指令测试起来完全够用。6. 常见问题与排查技巧实录6.1 悬空 else 到底归谁匹配C 语言中 if 和 else 的匹配规则是 else 与最近的未匹配 if 结合。递归下降天然支持这种匹配因为当解析完 if 的分支语句后解析器会立即检查下一个 Token 是否为 else。但如果分支本身又包含 if情况会变得复杂。我写了一个测试用例如果 else 被错误绑定到内层 if程序行为就会和 C 标准行为不一致。排查时最有用的工具是打印 AST 结构。我写了一个递归的 dump 函数把每个节点的类型和子节点缩进打印出来一眼就能看出 else 节点挂在了错误的 if 节点下。6.2 运算符优先级带来的诡异算术结果表达式解析最常见的 bug 是优先级处理错误。我遇到过 2 3 * 4 输出 20 而不是 14 的情况原因是我在 parseTerm 中没有继续向前调用 parseFactor而把乘除放在了同一个优先级层次解析。解决方案是严格执行层级调用。测试表达式优先级时我准备了一组经典的算术用例涵盖加乘混用、括号嵌套、减法结合性、一元负号、关系运算符混合每个都在每次改动后跑一遍。一个值得一提的坑是-3 * 4这种表达式。一元负号的优先级必须高于乘除否则会被解析成 -(3 * 4)这在语义上也能算对但当表达式变成-3 * -4时优先级错误会让 parser 直接报错。一元负号的实现方法是在 parseUnary 中检查负号 Token生成一个特殊的 NODE_NEGATE 节点而它出现在 parseExpr 的最低层调用中因此优先级总是最高的。6.3 符号表泄漏变量在块结束后还能访问作用域栈没有正确弹出的最典型症状是在 if 的一声部声明一个变量离开 if 后在函数外部还能引用到它。排查方法是对符号表栈加一层打印日志进入和离开块时打印当前作用域深度和变量名。我最终用结构化方式把所有 block 入口出口统一收口到两个函数实现杜绝了零散拼接代码导致的遗漏。6.4 调试和测试的黄金策略编译器比普通程序难调试因为它本身就是把一种输入翻译成另一种输出出错位置和出错原因往往隔着几层转换。我的实践是叠了三层防护第一层是增量验证。每完成一个模块就先写一个小测试文件只测试该模块的行为。词法分析器单独跑时用测试驱动把所有 Token 类型打印出来语法分析器单独跑时打印 AST语义分析器单独跑时检查错误码。第二层是端到端测试准备一组涵盖所有语法特性的测试脚本比如 12*3、函数递归求阶乘、if/else 分支、while 循环求和每次修改后全量运行。第三层是中间产物 dump写专门的打印函数输出 token 流、AST 结构、指令流和运行时栈状态任何一步和预期不符都能立即定位到具体阶段。6.5 常见问题速查清单以下是我开发过程中遇到的高频问题整理成了一张可直接对照的表现象可能原因解决方式词法分析把int拆成关键字和标识符缺少最长匹配先读完整字母串再查关键字表被拆成两个运算符运算符识别未做多字符匹配遇到 ! 时预读下一个字符表达式结果优先级错误解析函数层级跳层严格执行才 term factor 的层级调用变量在块外可访问作用域栈未弹出统一块进入退出代码打印作用域深度函数参数读取到错误值栈帧创建和参数写入顺序不对先创建帧再写入参数槽位跳转指令全部跳到最后一条跳转目标偏移未回填标签管理采用两遍生成方案类型不匹配报错位置不准确Token 位置信息缺失构建 AST 时保留每个节点的起始行列号6.6 给同样想动手的你几点建议最后聊几个我在整个过程中领悟最深的东西。首先坚持手写任何一个阶段都不要偷懒使用现成生成器这样才能切身体会到每个抽象层的必要性其次测试文件也要“写作”得足够用心尤其是边界条件比如优先级、嵌套循环、递归函数、数据类型混合这些都会暴露真实编译器里才会出现的问题。建议至少留三周时间专门做“把语法覆盖完整”和“把特性交叉调用”的集成测试比如在 while 里嵌套 if在函数返回值里调用另一个函数这种组合才是编译器开发中最容易出问题的部分最后保持日志系统的清晰和可开关开发结束后这些打印函数不要急着删后续想加新语法特性时它们还会回来帮你。开发一个编译器哪怕只是一个 C 子集都会让你重新理解一遍编程语言、程序运行和机器执行三者之间的关系。相比背下一堆编译原理术语亲手从头把一条表达式变成一串指令再执行出正确结果那种踏实感是任何理论书给不了的。希望这篇记录能给你一个清晰的路线图别怕啃硬骨头从最小的规则集开始一个个模块搭起来很快就能看到属于你自己的编译器吐出第一个正确的运行结果。