简介一份小型C编译器完整实现源码面向想深入钻研编译原理的学生与开发者。编译器将C语言翻译为可执行程序需经历词法分析、语法分析、语义分析、优化与代码生成等阶段这份代码完整覆盖这些核心流程并配套头文件与构建脚本方便对照阅读与实践。通过分析源码可以掌握标记识别、抽象语法树构建、符号表与类型检查、汇编代码生成等机制还能基于已有实现开展实验比如扩展关键字、调整优化策略或增加对结构体、指针操作的测试从而深化对C语言底层运作方式的理解。资源包共86个文件主体为50个C源码与12个头文件辅以少量演示程序及Makefile、批处理脚本等构建配置整体仅210KB结构紧凑适合按编译流程拆解学习。目前已有478人学习下载适合对编译器实现有探索欲的开发者作为动手起点。1. 一个能读懂的小型C编译器实现把“语言到机器码”的每一站摊开讲透你写int a 10;然后按下编译这十几个字符是怎么变成机器指令的我以前也自认为懂直到完整读了一份小型 C 编译器实现的源代码才把这条链路里每一站都串了起来。这个项目不是编译器教科书的片段也不是 gcc 那种几十万行的庞然大物它是把词法分析、语法分析、类型检查、代码生成四个阶段都做成完整闭环的教学型编译器几千行源码能独立编译运行。新手可以从 main 入口一路跟踪数据变化熟手则能研究它在作用域、栈帧和寄存器分配上做的取舍。如果你也想让“编译器”从黑匣子变成一个可以拆开、可以改动的工程这份源码值得先跑通再读透。2. 先定边界再动手这份C编译器源码支持什么、流水线怎么走2.1 C子集的边界支持到什么程度才算一个完整编译器全量 C 语言编译器是几十万行规模教学型 C 编译器首先要做减法。“小型 C 编译器”这个标题已经把边界写清楚了它实现的是 C 语言的一个实用子集。以我拆过的同类项目为例最常见的选型是支持int、char两种基本类型加上指针、一维数组、函数定义与调用、if/else、while、for、return以及加减乘除、赋值、比较、逻辑运算。struct、union、float、switch、goto这类功能几乎都会被砍掉因为引入它们会把语义分析和代码生成的复杂度同时放大一个量级。这个边界选择不是偷懒而是把编译原理的主干留全。拿到源码后别急着跑先打开 README 或源码目录里的说明确认它支持哪些语法。我一般会把支持列表抄在纸上再对照测试用例看一遍这样后面读代码时才知道某个报错到底是编译器写错了还是源码本身就不在该子集内。常见教学编译器的目录组织方式如下模块作用常见文件名词法分析把源码字符串拆成 tokentoken.c / lexer.c语法分析将 token 序列组装成 ASTparse.c / parser.c语义分析收集符号表、做类型检查resolve.c / sema.c代码生成输出汇编或中间代码codegen.c / gen.c前端入口读文件、串联各阶段main.c这个表格对应的是这类项目的主流组织方式不一定和每一份源码完全相同但思路一致。拿到源码后第一件事应该是找main函数看它如何调用这几个阶段而不是直接跳进某个算法细节。2.2 流水线的四道工序每一站的输入与输出一个 C 程序从文本到可执行结果通常要经过四个阶段词法分析、语法分析、语义分析、代码生成。小型编译器为了让人看得懂几乎都会把这四步做成线性流水线。入口函数一般长这样int compile_file(const char *path) { char *src read_file(path); // 读取整个源文件 Token *tokens tokenize(src); // 词法分析字符串 - token 数组 ASTNode *ast parse(tokens); // 语法分析token 数组 - 抽象语法树 check_semantics(ast); // 语义分析符号表 类型检查 gen_asm(ast, stdout); // 代码生成AST - 汇编文本 free_ast(ast); free_tokens(tokens); free(src); return 0; }这里tokenize接收源码字符串输出Token数组parse消费Token数组构建出抽象语法树check_semantics遍历 AST完成符号收集和类型验证gen_asm把修正后的 AST 翻译成汇编文本。每一步的输出都是下一步的输入结构上很像 Unix 管道。参数说明src是原始代码文本tokens是线性序列Token里保存类型、文本、行号ast是树状结构每个节点记录操作符、类型、子节点gen_asm最终把结果写到标准输出或文件。“行号”这个信息容易被忽略但它在报错提示里价值极大。从第一次跑通代码起就应该保留 token 的行号字段否则后面所有语法报错都只能告诉你“哪里错”不能告诉你“第几行错”。2.3 单遍与多遍的取舍为什么小型编译器也值得用四阶段早期编译器受内存限制倾向于单遍边读源码边生成代码。现在做教学型编译器几乎不会再有人写单遍因为符号表和 AST 分开处理每一遍的职责单一出问题时能快速定位。比如函数定义可以先用一次遍历把所有函数签名收集进符号表再单独遍历函数体做类型检查两次 pass 各管各的事。多遍带来的另一个好处是代码生成阶段可以更晚做决定。语义分析发现某个表达式类型不对可以在 AST 上直接改或报错不用回退词法状态。这个取舍是值得重点理解的地方以后你自己写 DSL 或者脚本解释器时这个四阶段结构可以直接复用它比把逻辑堆在一个大循环里要好维护得多。读源码的顺序我建议是先跑通一个测试用例再在两个关键位置打断点或加打印。第一个位置是tokenize返回后打印全部 token第二个位置是parse返回后按缩进打印 AST。把这两份输出对照源码看整个编译器的前半段就基本清晰了。后半段则在gen_asm中看每个 AST 节点如何映射到汇编指令这个映射关系是代码生成的核心后面第四章会详细展开。3. 词法与语法分析拆词、优先级表、递归下降如何协同3.1 词法分析器手写有限状态机而不是调正则库许多初学者会以为词法分析应该调正则表达式库但实际的小型编译器更喜欢手写状态机因为自己写的词法分析器在出错时能给出更精确的行号和上下文也不会把教育项目的依赖搞复杂。词法分析器的核心是一个循环跳过空白符、识别下一个 token、推进指针。识别数字和标识符的典型实现如下static int next_token(const char **s, Token *tok) { const char *p *s; while (*p isspace(*p)) p; // 跳过空格、换行、tab if (isdigit(*p)) { // 数字常量 tok-kind TOK_NUM; const char *start p; while (isdigit(*p)) p; tok-len p - start; *s p; return 1; } if (isalpha(*p) || *p _) { // 标识符或关键字 tok-kind TOK_IDENT; const char *start p; while (isalnum(*p) || *p _) p; tok-len p - start; *s p; return 1; } // 运算符与分隔符的分支略 return 0; }这个函数的要点是只在读取完一个完整 token 后才移动*s指针。如果读取过程中发现字符不属于当前 token不做回退而是把当前位置留在原处。isdigit和isalpha判断的都是单字节字符对 ASCII 范围内的 C 源码足够用。Token里记录len而不是复制字符串是为了减少 malloc 次数指针加长度就可以在后续阶段取用源码片段。识别完标识符后还需要查关键字表。常见做法是维护一个strcmp表把if、else、while、for、return、int、char等映射到独立的 token 类型。顺序很关键先按标识符读进来再查表查中就把TOK_IDENT改成TOK_IF这类类型。如果反过来先查表再按长度读取可能会把intx误判成int加x。遇到无法识别的字符时返回 0 并记录行号错误信息写成unexpected character at line N。行号的维护是在词法层每次读到\n时把 line 加 1token 结构里存 line后面所有语法报错都能用。这个细节看起来小但调试时能省大量时间。3.2 表达式优先级递归下降的四层结构表达式解析是语法分析里的重头戏。C 表达式优先级有十几层教学编译器通常只保留核心的几层赋值、等式、关系、加减、乘除、一元、基本项。递归下降把每一层写成一个 parse 函数层与层之间逐级调用优先级高的在更内层。以加减和等式为例AST *parse_add(void) { AST *node parse_mul(); // 先解析更高优先级的乘除 while (next_is() || next_is(-)) { Token op consume_op(); AST *rhs parse_mul(); node new_binop(op, node, rhs); } return node; } AST *parse_equality(void) { AST *node parse_relational(); // 先解析关系运算 while (next_is() || next_is(!)) { Token op consume_op(); AST *rhs parse_relational(); node new_binop(op, node, rhs); } return node; }因为乘除的parse_mul在最内层所以1 2 * 3会被解析成1 (2 * 3)无需额外查优先级表。左结合通过 while 循环实现每遇到一个运算符就把左边已累积的节点作为左操作数再解析右侧。这里有个常见疑惑为什么不用递归调用parse_add来解析右操作数因为那样会形成无限递归导致左结合表达式栈溢出。单运算符的右结合比如赋值才用递归或特殊处理。优先级层数和运算符的映射通常会整理成一张常量表层运算符结合性实现函数赋值右parse_assign等式 !左parse_equality关系 左parse_relational加减 -左parse_add乘除* / %左parse_mul一元- ! ~右parse_unary基本项数字/标识符/()-parse_primary这张表的作用不只是参考它还提示了实现顺序先写parse_primary再逐层向外包。如果发现某个表达式解析结果不对优先怀疑 parse 函数之间的调用顺序是不是写反了。3.3 悬空 else 与后缀自增语法层的两个经典问题悬空 else 是指if (1) if (0) a 1; else a 2;里 else 到底匹配哪个 if。C 标准规定 else 与最近的未匹配 if 结合递归下降实现时只要在 parse_if 里先解析内层语句再检查当前 token 是否为 else就天然满足这个规则。如果想把 else 匹配到外层 if需要跳过内层 if 的完整语句块那就要为语句列表增加清晰的分界。教学型编译器通常不提供这个选项建议也不要改保持标准行为即可。自增、自减这类后缀运算符的麻烦在于它的优先级高于一元运算但又要在parse_primary之后处理乘法。常见做法是在parse_postfix里循环检查 token属于或--就包一层 AST 节点循环直到不是后缀运算符。不要试图在词法层区分前和后它们的区别只发生在语法树的位置提前在词法层处理反而会把问题复杂化。语法错误恢复也是一个不能回避的问题。最简单的策略是“报错即停”解析到意外 token 时打印错误和行号直接退出。进阶一点的做法是跳过当前语句到分号或右括号让一次编译能报告多个错误。我建议第一版先做报错即停等全部测试用例跑通后再加恢复逻辑否则错误恢复本身会引入新的不确定性。4. 符号表与代码生成从AST到x86-64汇编的执行细节4.1 符号表的数据结构作用域链加哈希表语义分析的第一件事是建立符号表。作用域会产生嵌套数据结构上适合用链式哈希表全局是一个表进入函数体进一个子表进入代码块再进一个更深的子表退出时弹出。典型结构如下typedef struct SymTable SymTable; struct SymTable { SymTable *parent; // 上一层作用域 struct HashEntry *entries; // 当前层的哈希桶 }; SymTable *push_scope(SymTable *cur) { SymTable *new calloc(1, sizeof(SymTable)); new-parent cur; return new; } Symbol *resolve(SymTable *cur, const char *name) { for (; cur; cur cur-parent) { // 由内向外逐层查 Symbol *sym lookup_entries(cur, name); if (sym) return sym; } return NULL; }push_scope返回一个新的表头resolve从内向外逐层查找内层变量自动遮蔽外层同名变量。参数说明parent指针把各层串成链lookup_entries只查当前层的哈希桶不做递归resolve负责链式查找。这种设计在 C 编译器里几乎成了标准答案原因很简单出作用域时只需要丢弃当前表头不需要在每一层做复杂的符号回收。符号表里除了变量名还要记录类型、作用域深度、是否已初始化、在栈帧中的偏移量。偏移量在语义分析阶段可以先不填留到代码生成前统一分配但类型和作用域深度必须在解析阶段就定下来。Symbol结构里我建议预留一个scope_depth字段调试时能直接看出变量是在哪一层声明的避免在多层嵌套里对着名字猜。4.2 类型检查char 和 int 的隐性提升与指针退化类型检查要保证赋值两侧类型兼容、函数实参与形参数量一致。教学编译器通常支持int和char的互相赋值遇到指针时限制更严格。常见规则是char赋值给int做零扩展int赋值给char做截断指针与整数不能混用数组名在表达式中自动退化为指针。退化这个规则如果不做就无法通过参数传递数组。实现上AST 节点要保存自己的类型字段语义分析阶段用递归方式遍历在类型不匹配时返回错误。错误信息建议带行号比如line 5: left is int, right is int*。这里的关键是类型检查要在函数体所有函数签名都入表之后做所以很多教学编译器分两个 pass 遍历函数第一遍收集函数签名第二遍检查函数体。如果不这样做在 A 函数里调用后定义的 B 函数就会误报未声明。函数调用的实参求值顺序在 C 标准里是未规定的教学编译器为了稳定输出通常固定为从左到右并在 AST 里保留一个参数链表。如果你发现生成汇编后实参顺序总是不对先检查是 AST 顺序反了还是压栈顺序反了。x86-64 的传参规则是把前 6 个参数放进rdi/rsi/rdx/rcx/r8/r9多余参数入栈。4.3 代码生成固定寄存器映射与栈帧布局生成 x86-64 汇编时小型编译器普遍用固定映射策略每个临时变量对应一个寄存器或栈槽。相比真正的寄存器分配算法这种策略会多一些内存访问但逻辑清晰适合教学。局部变量统一放在栈帧里通过%rbp加负偏移访问。以a 1; b a 2;为例movl $1, -4(%rbp) # a 1 movl -4(%rbp), %eax # 读取 a 到 eax addl $2, %eax # eax 2 movl %eax, -8(%rbp) # b eax参数说明-4(%rbp)是局部变量a的栈槽-8(%rbp)是b的栈槽%eax是计算临时值的地方每次存储前把中间值留在%eax避免被下一次运算覆盖。这种“每次算完都写回栈”的策略牺牲了一点性能但每个 AST 节点对应几条固定汇编调试时很容易对齐。栈帧布局在函数进入时统一分配pushq %rbp movq %rsp, %rbp subq $48, %rspsubq $48是给局部变量预留 48 字节空间这个值由语义分析阶段统计每个函数的局部变量总大小得出。如果这个值算错汇编代码会覆盖返回地址程序运行后会在函数返回时直接段错误。常见排查方法是把每个函数的栈帧大小打印出来手算一遍每个局部变量的偏移是否落在预留区间内。AST 到汇编的映射关系可以整理成一张核心模板表AST 节点汇编模板num(n)movl $n, %eaxname(var)movl var_offset(%rbp), %eax加法先读左值到%eax压栈再读右值到%eaxpop 左值后addl赋值先算右值存入%eax再movl %eax, var_offset(%rbp)ifcmp加je/jne跳转到 else 或 end 标签函数调用依次设置rdi/rsi/...再call这张表几乎是一份“汇编速查手册”。遇到不认识的 AST 节点先查它对应哪几条指令再回到代码生成器里找模板函数。小型编译器的代码生成器本质上就是一个巨大的 switch节点类型分派到对应的模板代码。理解了这个结构你就能很自然地在模板里插入常数折叠或短路求值等优化。5. 避坑手册写C编译器时最常见的五类翻车现场5.1 作用域弹出时机不对导致变量遮蔽异常现象内层代码块里声明同名变量后外层同名变量在块结束后仍保留内层的类型或值。原因符号表子表没有在代码块解析结束时及时弹出后续语句错误地解析到了内层符号。解决在代码块 AST 的解析入口 push_scope结束时 pop_scopepop 必须放在所有局部变量解析完成之后。尤其注意 return 语句若在 pop 之前解析return 里引用的符号仍属于块作用域。手动检查时可以在解析每个代码块时打印符号表深度。没有嵌套的代码块前后深度差必须是 1。我一般会在语义分析阶段加一个断言pop 后当前表头必须等于进入前的表头否则直接抛内部错误。这是调试作用域问题最快的方法能比肉眼排查快一个量级。5.2 悬空 else 看似无关遇到空语句就出问题现象解析if (a) if (b) ; else x 1;时 else 被错误匹配到外层 if。原因内层 if 在解析到分号后结束parser 没有检查当前 token 是否为 else就把这条 if 语句收掉了导致 else 冒泡到外层。解决解析内层 if 的 then 分支后立即检查下一个 token 是否为 else如果是 else 且属于内层 if就当场消费掉绝不让它冒泡。C 标准的就近匹配规则在小编译器里不需要额外配置只要保证每个 if 都尝试消费自己的 else 即可。这个坑在写测试用例时最容易暴露多写几个嵌套 if 再加空语句如果编译器解析结果和 gcc 不一致八成就是这个原因。5.3 类型截断char 和 int 的宽度差异藏在赋值里现象char变量赋值大于 255 的整数后又把它当作函数实参传给int形参结果值变成 -1 或其它怪数。原因int到char的赋值会截断但很多实现忘记在类型检查阶段记录“这是一个 char”后续取值时用movzbl还是movsbl全看心情。解决符号表里保存变量声明的类型读取char变量时用movzbl扩展为int写入时用movb只写低 8 位。关键不是生成汇编那一刻而是语义分析时就要把类型标注在 AST 节点上。排查技巧用char类型跑一个边界值测试比如赋 255、256、-1再打印成整数。如果 256 变成 0、-1 变成 255说明无符号零扩展写对了如果出现随机乱值多半是符号扩展和零扩展混用了。5.4 局部变量偏移分配与栈帧大小不一致现象生成的汇编在函数内多次赋值后进入下一个函数调用时寄存器或栈数据被冲掉。原因栈帧预留空间subq算小了函数体内生成代码访问-24(%rbp)但栈帧只留了 16 字节。解决在代码生成前统计每个局部变量需要的槽位并记录栈帧最小 size函数序言里的subq值用该 size 向上取整到 16 字节对齐。修改代码生成器后必须把所有函数的栈帧大小打印出来和手算值逐一比对。这个坑的隐蔽之处在于有时只是恰好没踩到被覆盖的位置程序能跑但结果随机出错。一旦出现“运行时行为不稳定但编译输出看起来正常”优先怀疑栈帧。5.5 数组参数退化成指针后sizeof 行为失实现象函数内对数组参数用sizeof本意求数组长度结果只有 8指针大小。原因C 标准规定数组参数退化为指针教学编译器若未建立这条规则就会把参数错误标记为数组。解决函数参数列表里int a[]在语义分析阶段直接改成int* a符号表里不再保留数组类型。顺带要注意对数组名取地址得到的地址值相等但类型不同这对指针算术影响极大现阶段直接禁止对退化的数组参数取地址即可。测试方法是写一个接收数组参数并打印sizeof的函数期望输出是 864 位指针如果编译器输出了数组实际长度说明退化规则没有生效。6. 把这份源码用出价值测试骨架与三个进阶方向6.1 建一个可回归的测试骨架读编译器源码我第一件事就是给它建测试壳把每个测试.c文件编译、运行输出结果与期望值比对。这个习惯能防止改语法分析器时把原本能跑的表达式弄坏。测试脚本可以很简陋但必须能一键执行for f in tests/*.c; do ./mini-cc $f out.s gcc -no-pie out.s -o a.out if ./a.out result.txt; then diff result.txt tests/$(basename $f).expected fi done这个循环就是一个回归测试所有用例编译并运行结果与.expected文件逐行比对。参数说明-no-pie关闭地址随机化便于汇编调试out.s是生成的汇编diff失败说明用例回归需要判断是期望文件错了还是代码改错了。在普通用例之外加一个空跑 case 专门验证编译器不出错这个用例的价值是覆盖崩溃路径。每次修改代码生成器后手动跑几组 gcc 相同源码的结果对比一下能快速发现寄存器分配和栈帧的隐性错误。6.2 三个值得动手的拓展常数折叠、短路求值、struct第一常数折叠最简单在语义分析阶段的 AST 节点构造处判断两个子节点都是数字常量直接把结果算出替换成一个新的数字节点。比如2 3在语义分析后直接变成5代码生成少生成三条指令改动范围小回报明显。第二短路求值让a b在a为零时不再求值b这要求代码生成阶段把逻辑运算符翻译成cmp加je/jne而不是函数调用或简单算术。工作量中等但做完后你对“控制流如何从 AST 中诞生”会有直观理解。第三struct支持会把字段偏移计算引入系统这是第一个涉及内存布局规划的功能。做完它你对符号表、类型系统和栈帧分配的理解会上一个台阶因为字段偏移本质上是一种“具名偏移量”和局部变量偏移共用一套概念。每一个扩展做完后都回到测试骨架跑全量用例。从那以后我每次改语法分析器或代码生成器都强制走一遍完整测试对比编译器输出和 gcc 行为确认没有引入任何回归。这份源码最大的价值不在于跑通它而在于你敢不敢在读懂它之后动手改一条优先级规则、加一个类型或调一次栈帧布局。能改得动说明这条流水线真正属于你了。希望帮到你。本文还有配套的精品资源点击获取
简介一份小型C编译器完整实现源码面向想深入钻研编译原理的学生与开发者。编译器将C语言翻译为可执行程序需经历词法分析、语法分析、语义分析、优化与代码生成等阶段这份代码完整覆盖这些核心流程并配套头文件与构建脚本方便对照阅读与实践。通过分析源码可以掌握标记识别、抽象语法树构建、符号表与类型检查、汇编代码生成等机制还能基于已有实现开展实验比如扩展关键字、调整优化策略或增加对结构体、指针操作的测试从而深化对C语言底层运作方式的理解。资源包共86个文件主体为50个C源码与12个头文件辅以少量演示程序及Makefile、批处理脚本等构建配置整体仅210KB结构紧凑适合按编译流程拆解学习。目前已有478人学习下载适合对编译器实现有探索欲的开发者作为动手起点。1. 一个能读懂的小型C编译器实现把“语言到机器码”的每一站摊开讲透你写int a 10;然后按下编译这十几个字符是怎么变成机器指令的我以前也自认为懂直到完整读了一份小型 C 编译器实现的源代码才把这条链路里每一站都串了起来。这个项目不是编译器教科书的片段也不是 gcc 那种几十万行的庞然大物它是把词法分析、语法分析、类型检查、代码生成四个阶段都做成完整闭环的教学型编译器几千行源码能独立编译运行。新手可以从 main 入口一路跟踪数据变化熟手则能研究它在作用域、栈帧和寄存器分配上做的取舍。如果你也想让“编译器”从黑匣子变成一个可以拆开、可以改动的工程这份源码值得先跑通再读透。2. 先定边界再动手这份C编译器源码支持什么、流水线怎么走2.1 C子集的边界支持到什么程度才算一个完整编译器全量 C 语言编译器是几十万行规模教学型 C 编译器首先要做减法。“小型 C 编译器”这个标题已经把边界写清楚了它实现的是 C 语言的一个实用子集。以我拆过的同类项目为例最常见的选型是支持int、char两种基本类型加上指针、一维数组、函数定义与调用、if/else、while、for、return以及加减乘除、赋值、比较、逻辑运算。struct、union、float、switch、goto这类功能几乎都会被砍掉因为引入它们会把语义分析和代码生成的复杂度同时放大一个量级。这个边界选择不是偷懒而是把编译原理的主干留全。拿到源码后别急着跑先打开 README 或源码目录里的说明确认它支持哪些语法。我一般会把支持列表抄在纸上再对照测试用例看一遍这样后面读代码时才知道某个报错到底是编译器写错了还是源码本身就不在该子集内。常见教学编译器的目录组织方式如下模块作用常见文件名词法分析把源码字符串拆成 tokentoken.c / lexer.c语法分析将 token 序列组装成 ASTparse.c / parser.c语义分析收集符号表、做类型检查resolve.c / sema.c代码生成输出汇编或中间代码codegen.c / gen.c前端入口读文件、串联各阶段main.c这个表格对应的是这类项目的主流组织方式不一定和每一份源码完全相同但思路一致。拿到源码后第一件事应该是找main函数看它如何调用这几个阶段而不是直接跳进某个算法细节。2.2 流水线的四道工序每一站的输入与输出一个 C 程序从文本到可执行结果通常要经过四个阶段词法分析、语法分析、语义分析、代码生成。小型编译器为了让人看得懂几乎都会把这四步做成线性流水线。入口函数一般长这样int compile_file(const char *path) { char *src read_file(path); // 读取整个源文件 Token *tokens tokenize(src); // 词法分析字符串 - token 数组 ASTNode *ast parse(tokens); // 语法分析token 数组 - 抽象语法树 check_semantics(ast); // 语义分析符号表 类型检查 gen_asm(ast, stdout); // 代码生成AST - 汇编文本 free_ast(ast); free_tokens(tokens); free(src); return 0; }这里tokenize接收源码字符串输出Token数组parse消费Token数组构建出抽象语法树check_semantics遍历 AST完成符号收集和类型验证gen_asm把修正后的 AST 翻译成汇编文本。每一步的输出都是下一步的输入结构上很像 Unix 管道。参数说明src是原始代码文本tokens是线性序列Token里保存类型、文本、行号ast是树状结构每个节点记录操作符、类型、子节点gen_asm最终把结果写到标准输出或文件。“行号”这个信息容易被忽略但它在报错提示里价值极大。从第一次跑通代码起就应该保留 token 的行号字段否则后面所有语法报错都只能告诉你“哪里错”不能告诉你“第几行错”。2.3 单遍与多遍的取舍为什么小型编译器也值得用四阶段早期编译器受内存限制倾向于单遍边读源码边生成代码。现在做教学型编译器几乎不会再有人写单遍因为符号表和 AST 分开处理每一遍的职责单一出问题时能快速定位。比如函数定义可以先用一次遍历把所有函数签名收集进符号表再单独遍历函数体做类型检查两次 pass 各管各的事。多遍带来的另一个好处是代码生成阶段可以更晚做决定。语义分析发现某个表达式类型不对可以在 AST 上直接改或报错不用回退词法状态。这个取舍是值得重点理解的地方以后你自己写 DSL 或者脚本解释器时这个四阶段结构可以直接复用它比把逻辑堆在一个大循环里要好维护得多。读源码的顺序我建议是先跑通一个测试用例再在两个关键位置打断点或加打印。第一个位置是tokenize返回后打印全部 token第二个位置是parse返回后按缩进打印 AST。把这两份输出对照源码看整个编译器的前半段就基本清晰了。后半段则在gen_asm中看每个 AST 节点如何映射到汇编指令这个映射关系是代码生成的核心后面第四章会详细展开。3. 词法与语法分析拆词、优先级表、递归下降如何协同3.1 词法分析器手写有限状态机而不是调正则库许多初学者会以为词法分析应该调正则表达式库但实际的小型编译器更喜欢手写状态机因为自己写的词法分析器在出错时能给出更精确的行号和上下文也不会把教育项目的依赖搞复杂。词法分析器的核心是一个循环跳过空白符、识别下一个 token、推进指针。识别数字和标识符的典型实现如下static int next_token(const char **s, Token *tok) { const char *p *s; while (*p isspace(*p)) p; // 跳过空格、换行、tab if (isdigit(*p)) { // 数字常量 tok-kind TOK_NUM; const char *start p; while (isdigit(*p)) p; tok-len p - start; *s p; return 1; } if (isalpha(*p) || *p _) { // 标识符或关键字 tok-kind TOK_IDENT; const char *start p; while (isalnum(*p) || *p _) p; tok-len p - start; *s p; return 1; } // 运算符与分隔符的分支略 return 0; }这个函数的要点是只在读取完一个完整 token 后才移动*s指针。如果读取过程中发现字符不属于当前 token不做回退而是把当前位置留在原处。isdigit和isalpha判断的都是单字节字符对 ASCII 范围内的 C 源码足够用。Token里记录len而不是复制字符串是为了减少 malloc 次数指针加长度就可以在后续阶段取用源码片段。识别完标识符后还需要查关键字表。常见做法是维护一个strcmp表把if、else、while、for、return、int、char等映射到独立的 token 类型。顺序很关键先按标识符读进来再查表查中就把TOK_IDENT改成TOK_IF这类类型。如果反过来先查表再按长度读取可能会把intx误判成int加x。遇到无法识别的字符时返回 0 并记录行号错误信息写成unexpected character at line N。行号的维护是在词法层每次读到\n时把 line 加 1token 结构里存 line后面所有语法报错都能用。这个细节看起来小但调试时能省大量时间。3.2 表达式优先级递归下降的四层结构表达式解析是语法分析里的重头戏。C 表达式优先级有十几层教学编译器通常只保留核心的几层赋值、等式、关系、加减、乘除、一元、基本项。递归下降把每一层写成一个 parse 函数层与层之间逐级调用优先级高的在更内层。以加减和等式为例AST *parse_add(void) { AST *node parse_mul(); // 先解析更高优先级的乘除 while (next_is() || next_is(-)) { Token op consume_op(); AST *rhs parse_mul(); node new_binop(op, node, rhs); } return node; } AST *parse_equality(void) { AST *node parse_relational(); // 先解析关系运算 while (next_is() || next_is(!)) { Token op consume_op(); AST *rhs parse_relational(); node new_binop(op, node, rhs); } return node; }因为乘除的parse_mul在最内层所以1 2 * 3会被解析成1 (2 * 3)无需额外查优先级表。左结合通过 while 循环实现每遇到一个运算符就把左边已累积的节点作为左操作数再解析右侧。这里有个常见疑惑为什么不用递归调用parse_add来解析右操作数因为那样会形成无限递归导致左结合表达式栈溢出。单运算符的右结合比如赋值才用递归或特殊处理。优先级层数和运算符的映射通常会整理成一张常量表层运算符结合性实现函数赋值右parse_assign等式 !左parse_equality关系 左parse_relational加减 -左parse_add乘除* / %左parse_mul一元- ! ~右parse_unary基本项数字/标识符/()-parse_primary这张表的作用不只是参考它还提示了实现顺序先写parse_primary再逐层向外包。如果发现某个表达式解析结果不对优先怀疑 parse 函数之间的调用顺序是不是写反了。3.3 悬空 else 与后缀自增语法层的两个经典问题悬空 else 是指if (1) if (0) a 1; else a 2;里 else 到底匹配哪个 if。C 标准规定 else 与最近的未匹配 if 结合递归下降实现时只要在 parse_if 里先解析内层语句再检查当前 token 是否为 else就天然满足这个规则。如果想把 else 匹配到外层 if需要跳过内层 if 的完整语句块那就要为语句列表增加清晰的分界。教学型编译器通常不提供这个选项建议也不要改保持标准行为即可。自增、自减这类后缀运算符的麻烦在于它的优先级高于一元运算但又要在parse_primary之后处理乘法。常见做法是在parse_postfix里循环检查 token属于或--就包一层 AST 节点循环直到不是后缀运算符。不要试图在词法层区分前和后它们的区别只发生在语法树的位置提前在词法层处理反而会把问题复杂化。语法错误恢复也是一个不能回避的问题。最简单的策略是“报错即停”解析到意外 token 时打印错误和行号直接退出。进阶一点的做法是跳过当前语句到分号或右括号让一次编译能报告多个错误。我建议第一版先做报错即停等全部测试用例跑通后再加恢复逻辑否则错误恢复本身会引入新的不确定性。4. 符号表与代码生成从AST到x86-64汇编的执行细节4.1 符号表的数据结构作用域链加哈希表语义分析的第一件事是建立符号表。作用域会产生嵌套数据结构上适合用链式哈希表全局是一个表进入函数体进一个子表进入代码块再进一个更深的子表退出时弹出。典型结构如下typedef struct SymTable SymTable; struct SymTable { SymTable *parent; // 上一层作用域 struct HashEntry *entries; // 当前层的哈希桶 }; SymTable *push_scope(SymTable *cur) { SymTable *new calloc(1, sizeof(SymTable)); new-parent cur; return new; } Symbol *resolve(SymTable *cur, const char *name) { for (; cur; cur cur-parent) { // 由内向外逐层查 Symbol *sym lookup_entries(cur, name); if (sym) return sym; } return NULL; }push_scope返回一个新的表头resolve从内向外逐层查找内层变量自动遮蔽外层同名变量。参数说明parent指针把各层串成链lookup_entries只查当前层的哈希桶不做递归resolve负责链式查找。这种设计在 C 编译器里几乎成了标准答案原因很简单出作用域时只需要丢弃当前表头不需要在每一层做复杂的符号回收。符号表里除了变量名还要记录类型、作用域深度、是否已初始化、在栈帧中的偏移量。偏移量在语义分析阶段可以先不填留到代码生成前统一分配但类型和作用域深度必须在解析阶段就定下来。Symbol结构里我建议预留一个scope_depth字段调试时能直接看出变量是在哪一层声明的避免在多层嵌套里对着名字猜。4.2 类型检查char 和 int 的隐性提升与指针退化类型检查要保证赋值两侧类型兼容、函数实参与形参数量一致。教学编译器通常支持int和char的互相赋值遇到指针时限制更严格。常见规则是char赋值给int做零扩展int赋值给char做截断指针与整数不能混用数组名在表达式中自动退化为指针。退化这个规则如果不做就无法通过参数传递数组。实现上AST 节点要保存自己的类型字段语义分析阶段用递归方式遍历在类型不匹配时返回错误。错误信息建议带行号比如line 5: left is int, right is int*。这里的关键是类型检查要在函数体所有函数签名都入表之后做所以很多教学编译器分两个 pass 遍历函数第一遍收集函数签名第二遍检查函数体。如果不这样做在 A 函数里调用后定义的 B 函数就会误报未声明。函数调用的实参求值顺序在 C 标准里是未规定的教学编译器为了稳定输出通常固定为从左到右并在 AST 里保留一个参数链表。如果你发现生成汇编后实参顺序总是不对先检查是 AST 顺序反了还是压栈顺序反了。x86-64 的传参规则是把前 6 个参数放进rdi/rsi/rdx/rcx/r8/r9多余参数入栈。4.3 代码生成固定寄存器映射与栈帧布局生成 x86-64 汇编时小型编译器普遍用固定映射策略每个临时变量对应一个寄存器或栈槽。相比真正的寄存器分配算法这种策略会多一些内存访问但逻辑清晰适合教学。局部变量统一放在栈帧里通过%rbp加负偏移访问。以a 1; b a 2;为例movl $1, -4(%rbp) # a 1 movl -4(%rbp), %eax # 读取 a 到 eax addl $2, %eax # eax 2 movl %eax, -8(%rbp) # b eax参数说明-4(%rbp)是局部变量a的栈槽-8(%rbp)是b的栈槽%eax是计算临时值的地方每次存储前把中间值留在%eax避免被下一次运算覆盖。这种“每次算完都写回栈”的策略牺牲了一点性能但每个 AST 节点对应几条固定汇编调试时很容易对齐。栈帧布局在函数进入时统一分配pushq %rbp movq %rsp, %rbp subq $48, %rspsubq $48是给局部变量预留 48 字节空间这个值由语义分析阶段统计每个函数的局部变量总大小得出。如果这个值算错汇编代码会覆盖返回地址程序运行后会在函数返回时直接段错误。常见排查方法是把每个函数的栈帧大小打印出来手算一遍每个局部变量的偏移是否落在预留区间内。AST 到汇编的映射关系可以整理成一张核心模板表AST 节点汇编模板num(n)movl $n, %eaxname(var)movl var_offset(%rbp), %eax加法先读左值到%eax压栈再读右值到%eaxpop 左值后addl赋值先算右值存入%eax再movl %eax, var_offset(%rbp)ifcmp加je/jne跳转到 else 或 end 标签函数调用依次设置rdi/rsi/...再call这张表几乎是一份“汇编速查手册”。遇到不认识的 AST 节点先查它对应哪几条指令再回到代码生成器里找模板函数。小型编译器的代码生成器本质上就是一个巨大的 switch节点类型分派到对应的模板代码。理解了这个结构你就能很自然地在模板里插入常数折叠或短路求值等优化。5. 避坑手册写C编译器时最常见的五类翻车现场5.1 作用域弹出时机不对导致变量遮蔽异常现象内层代码块里声明同名变量后外层同名变量在块结束后仍保留内层的类型或值。原因符号表子表没有在代码块解析结束时及时弹出后续语句错误地解析到了内层符号。解决在代码块 AST 的解析入口 push_scope结束时 pop_scopepop 必须放在所有局部变量解析完成之后。尤其注意 return 语句若在 pop 之前解析return 里引用的符号仍属于块作用域。手动检查时可以在解析每个代码块时打印符号表深度。没有嵌套的代码块前后深度差必须是 1。我一般会在语义分析阶段加一个断言pop 后当前表头必须等于进入前的表头否则直接抛内部错误。这是调试作用域问题最快的方法能比肉眼排查快一个量级。5.2 悬空 else 看似无关遇到空语句就出问题现象解析if (a) if (b) ; else x 1;时 else 被错误匹配到外层 if。原因内层 if 在解析到分号后结束parser 没有检查当前 token 是否为 else就把这条 if 语句收掉了导致 else 冒泡到外层。解决解析内层 if 的 then 分支后立即检查下一个 token 是否为 else如果是 else 且属于内层 if就当场消费掉绝不让它冒泡。C 标准的就近匹配规则在小编译器里不需要额外配置只要保证每个 if 都尝试消费自己的 else 即可。这个坑在写测试用例时最容易暴露多写几个嵌套 if 再加空语句如果编译器解析结果和 gcc 不一致八成就是这个原因。5.3 类型截断char 和 int 的宽度差异藏在赋值里现象char变量赋值大于 255 的整数后又把它当作函数实参传给int形参结果值变成 -1 或其它怪数。原因int到char的赋值会截断但很多实现忘记在类型检查阶段记录“这是一个 char”后续取值时用movzbl还是movsbl全看心情。解决符号表里保存变量声明的类型读取char变量时用movzbl扩展为int写入时用movb只写低 8 位。关键不是生成汇编那一刻而是语义分析时就要把类型标注在 AST 节点上。排查技巧用char类型跑一个边界值测试比如赋 255、256、-1再打印成整数。如果 256 变成 0、-1 变成 255说明无符号零扩展写对了如果出现随机乱值多半是符号扩展和零扩展混用了。5.4 局部变量偏移分配与栈帧大小不一致现象生成的汇编在函数内多次赋值后进入下一个函数调用时寄存器或栈数据被冲掉。原因栈帧预留空间subq算小了函数体内生成代码访问-24(%rbp)但栈帧只留了 16 字节。解决在代码生成前统计每个局部变量需要的槽位并记录栈帧最小 size函数序言里的subq值用该 size 向上取整到 16 字节对齐。修改代码生成器后必须把所有函数的栈帧大小打印出来和手算值逐一比对。这个坑的隐蔽之处在于有时只是恰好没踩到被覆盖的位置程序能跑但结果随机出错。一旦出现“运行时行为不稳定但编译输出看起来正常”优先怀疑栈帧。5.5 数组参数退化成指针后sizeof 行为失实现象函数内对数组参数用sizeof本意求数组长度结果只有 8指针大小。原因C 标准规定数组参数退化为指针教学编译器若未建立这条规则就会把参数错误标记为数组。解决函数参数列表里int a[]在语义分析阶段直接改成int* a符号表里不再保留数组类型。顺带要注意对数组名取地址得到的地址值相等但类型不同这对指针算术影响极大现阶段直接禁止对退化的数组参数取地址即可。测试方法是写一个接收数组参数并打印sizeof的函数期望输出是 864 位指针如果编译器输出了数组实际长度说明退化规则没有生效。6. 把这份源码用出价值测试骨架与三个进阶方向6.1 建一个可回归的测试骨架读编译器源码我第一件事就是给它建测试壳把每个测试.c文件编译、运行输出结果与期望值比对。这个习惯能防止改语法分析器时把原本能跑的表达式弄坏。测试脚本可以很简陋但必须能一键执行for f in tests/*.c; do ./mini-cc $f out.s gcc -no-pie out.s -o a.out if ./a.out result.txt; then diff result.txt tests/$(basename $f).expected fi done这个循环就是一个回归测试所有用例编译并运行结果与.expected文件逐行比对。参数说明-no-pie关闭地址随机化便于汇编调试out.s是生成的汇编diff失败说明用例回归需要判断是期望文件错了还是代码改错了。在普通用例之外加一个空跑 case 专门验证编译器不出错这个用例的价值是覆盖崩溃路径。每次修改代码生成器后手动跑几组 gcc 相同源码的结果对比一下能快速发现寄存器分配和栈帧的隐性错误。6.2 三个值得动手的拓展常数折叠、短路求值、struct第一常数折叠最简单在语义分析阶段的 AST 节点构造处判断两个子节点都是数字常量直接把结果算出替换成一个新的数字节点。比如2 3在语义分析后直接变成5代码生成少生成三条指令改动范围小回报明显。第二短路求值让a b在a为零时不再求值b这要求代码生成阶段把逻辑运算符翻译成cmp加je/jne而不是函数调用或简单算术。工作量中等但做完后你对“控制流如何从 AST 中诞生”会有直观理解。第三struct支持会把字段偏移计算引入系统这是第一个涉及内存布局规划的功能。做完它你对符号表、类型系统和栈帧分配的理解会上一个台阶因为字段偏移本质上是一种“具名偏移量”和局部变量偏移共用一套概念。每一个扩展做完后都回到测试骨架跑全量用例。从那以后我每次改语法分析器或代码生成器都强制走一遍完整测试对比编译器输出和 gcc 行为确认没有引入任何回归。这份源码最大的价值不在于跑通它而在于你敢不敢在读懂它之后动手改一条优先级规则、加一个类型或调一次栈帧布局。能改得动说明这条流水线真正属于你了。希望帮到你。本文还有配套的精品资源点击获取
