手写编译器实战：Hustcompilation2022源码全流程拆解

简介Hustcompilation2022是华中科技大学2019级编译原理课程的实验项目面向计算机专业学生与编译器入门者展示编译器前端从词法分析、语法分析、语义分析到AST构建与中间代码生成的核心过程。项目虽未完整覆盖全部实验但保留的源码已清晰呈现编译器的关键实现路径并包含一个PL0语言编译器的部分实现支持将基础PL0源代码转换为虚拟机代码。资源共19个文件以C/C源码.c/.h/.cpp、词法与语法定义文件.l/.y为主辅以Makefile构建脚本、Markdown实验说明、PDF语言定义文档整体压缩包约878KB结构紧凑便于按实验模块检索。目前已有30位学习者浏览或下载可用于课程设计参考、编译原理实验复现或自学编译器构建基础。项目还附有SysY2022语言定义文档能帮助读者对照语法规则理解代码实现提升对编译流程的整体认知。 拿到(源码)基于编译原理的Hustcompilation2022项目.zip这个压缩包第一反应是又是编译原理课设但真正解压开后我发现这份源码并没有停留在“抄一遍课本”的层面。整个项目从词法到语法再到代码生成结构完整注释密度也够注释里还保留了踩坑记录。对于想完整走一遍“手写编译器”流程的人来说这份代码几乎是一个可运行的教科书。编译原理这门课理论性强劝退率也高但一旦你把一个能跑的编译器从零写到“能编译并执行一段实际代码”整个知识体系都会被打通。我花了两天时间把这份源码完整过了一遍还顺手补了几个测试用例下面这篇就把拆解过程、核心实现细节和踩坑经验一次性整理出来。1. 项目整体认知Hustcompilation2022到底做了什么1.1 打开压缩包后的第一印象解压zip后目录层级非常规整一眼扫过去不会让人头大Hustcompilation2022/ ├── src/ # 全部源码按编译阶段分包 ├── tests/ # 测试用例包含合法程序与非法程序 ├── docs/ # 设计文档与文法说明 ├── output/ # 中间产物如AST可视化、目标码 ├── Makefile └── README.md比较难得的点是src/下面没有把所有逻辑塞进一个main.cpp里而是按“词法分析、语法分析、语义分析、代码生成”划分了模块还专门有一个utils/目录放错误报告、符号表结构和公共数据结构。对于课程项目来说这种组织方式直接决定了后续调试的体验——我见过太多把所有代码堆在一起、两千行一个文件的上古项目那种代码基本只能从头到尾重写。从README来看Hustcompilation2022的目标语言支持变量声明、算术表达式、布尔表达式、if/else、while、函数调用作用域区分全局和局部这已经是一个“麻雀虽小五脏俱全”的流程。和很多只做到语法树打印就交差的课设相比这个项目真正把代码生成和简单的栈式内存分配实现出来了运行阶段能把源码编译成自定义虚拟机指令再执行出结果。1.2 适合谁来参考这份源码如果你正处于下面任一阶段这份源码的参考价值会很大正在做编译原理课设需要一份逻辑完整、可移植的实现作为参照想复习编译器前端“词法 - 语法 - 语义 - 中间代码 - 目标代码”的完整链路准备面试想借一个具体实现把“符号表怎么设计”“作用域怎么处理”“递归下降的缺陷在哪”这类问题聊清楚对“用自定义虚拟机跑自己写的编译器”感兴趣的折腾型玩家有一点要说明这份源码不是那种复制粘贴就能跑出花来的“全能编译器”它更像一个教学型作品在功能覆盖和代码可读性之间做了取舍。如果你拿它来做“C语言全集子集”它肯定不够但如果你想知道课本上的理论如何一步步落到代码里它反而比很多“高大全但看不懂”的工程型编译器更适合。1.3 阅读前需要储备的知识点在啃这份代码之前建议先有下面几个概念的底子正则表达式到NFA/DFA的转化逻辑哪怕只是了解“不去重也能绕过去”的阶段上下文无关文法CFG与BNF范式能看懂产生式递归下降分析与LL(1)的关系抽象语法树AST和多叉树结构不懂这些其实也能把代码看完但会看得云里雾里。我的建议是如果时间紧至少先读一遍陈鄞老师的编译原理视频课里关于词法分析和语法分析的章节再来读源码效率会高很多。我就是先看视频、再死磕代码大概花了两个晚上把整体逻辑理通。2. 前端核心细节词法分析与语法分析的实现策略2.1 词法分析手写扫描器而非lex生成器现在很多项目图省事直接上lex/flex生成词法分析器但Hustcompilation2022选择的是手写扫描器。这个决定明显是经过考虑的手写扫描器对初学者的友好度更高编译环境依赖更少也更容易在代码里精准控制报错位置。词法分析器的主体是一个nextToken()方法。它维护一个全局输入缓冲区和游标位置遇到空格、换行、制表符就跳过然后根据首字符的类别决定进入哪个分支如果首字符是字母或下划线进入标识符合法字符循环直到读到非字母/数字/下划线为止如果首字符是数字进入数字循环并且在这里区分整数和浮点数如果首字符是引号进入字符串字面量处理分支否则进入运算符和分隔符的匹配分支需要注意的一个细节是关键字和标识符的处理。这个项目没有在状态机里直接判断关键字而是先把长的字符串识别出来再去查一个关键字表。如果命中了就直接返回关键字Token否则当作普通标识符。这个做法比在词法规则里逐字匹配更省事也更容易扩展新关键字。长期写编译器的人都知道词法分析里的“坑”主要体现在几个位置一是注释块/* */的结束符没找到时要报错二是字符常量里的转义序列比如\n这种容易被初学项目忽略三是文件末尾没有换行时最后一个token的边界处理。这份源码在这三处的处理都比较规范尤其是对“文件意外结束”的情况报错信息会明确指出EOF in comment而不是抛出一个莫名其妙的数组越界异常。2.2 语法分析递归下降为主、运算符优先级分层语法分析部分采用的是经典递归下降法没有用yacc/bison。每个非终结符对应一个函数比如parseExpression()、parseTerm()、parseFactor()、parseStatement()。这套结构在读懂之后你会觉得编译器前端并不神秘。关于表达式解析项目用了“优先级分层”而不是普拉特解析Pratt Parsing。也就是说expression - additiveExpr additiveExpr - multiplicativeExpr (( | -) multiplicativeExpr)* multiplicativeExpr - unaryExpr ((* | /) unaryExpr)* unaryExpr - (- | !) unaryExpr | primaryExpr这种分层方式的好处是逻辑直观和课本中的文法推导完全对应。坏处是代码会稍显冗长尤其当运算符级别变多时函数调用层级会变深。但对于课程项目来说这个选择绝对正确因为考试和课设更看重“你是否理解了文法到程序的映射关系”。解析器在生成AST时用了内存池统一管理ASTNode的分配避免每次都new然后到处delete导致内存碎片和悬挂指针。ASTNode结构里存放了节点类型、子节点列表、token值、行列号等字段。有了行列号后面语义分析和报错阶段才能给出“第几行第几列有错误”的精准提示。2.3 AST设计为什么它比语法树更适合后续分析语法分析阶段直接产生的其实是“语法树”Parse Tree它保留了所有非终结符和终结符还包括括号这些只影响推导不参与语义的节点。但Hustcompilation2022在语法分析过程中直接构建AST剔除了多余的中间节点。以表达式2 * (3 4)为例* / \ 2 / \ 3 4括号和一部分非终结符节点被消除剩下的节点直接反映运算层次。这对于后续的语义检查和代码生成非常关键因为遍历AST时每个节点都有一个明确的语义含义。我拆解时发现AST节点类型枚举里包含了NODE_INT_LITERAL、NODE_STRING_LITERAL、NODE_VAR_DECL、NODE_ASSIGN、NODE_FUNC_DECL、NODE_IF、NODE_WHILE、NODE_RETURN等覆盖范围很全面。更让人惊喜的是它在output/目录下提供了AST可视化输出用缩进或者括号嵌套的形式打印整棵树的形状。调试语法分析时这个功能比gdb打断点更好用能一眼看出括号作用域有没有串层。3. 符号表与语义分析编译器前端的分水岭3.1 符号表的层级设计与作用域管理做完语法分析很多课设项目就开始水了因为语义分析需要处理变量类型、作用域和类型检查。Hustcompilation2022在这里做得很扎实。整个符号表不是一张扁平的哈希表而是按作用域划分成多层的结构。每个作用域对象是一个Scope内部有一个unordered_mapstring, Symbol同时有一个指针指向父作用域。全局作用域在最外层函数体、块语句会创建新的子作用域。变量查找的过程是从当前作用域出发逐级向上层查找lookup(x): 检查当前作用域 如果没找到进入父作用域继续查 直到全局作用域 还没找到报未定义错误这个设计很贴近真实编译器中“词法作用域Lexical Scoping”的实现方式。它正确解决了局部变量和全局变量重名的问题在一个函数内部定义了一个和全局变量同名的局部变量那么在这个函数内部访问到的只会是局部变量外面的全局变量不受影响。实际代码中Scope还有enterScope()和exitScope()方法进入if/while块时创建新作用域结束时销毁。如果你把这段源码读懂了后面去理解真正的C/C编译器如何处理“块级作用域”会轻松很多。3.2 类型检查与常见错误拦截语义分析阶段的核心任务是遍历AST检查每种操作是否符合语言规范同时把必要的类型信息挂到AST节点上。项目里实现了几种关键检查检查项说明报错案例变量是否已声明查找符号表未找到则报错使用未定义的变量a函数参数个数调用时实参与形参数量对比foo(1,2)但foo只接受1个参数赋值类型兼容确保等号两侧类型一致int a; a hello;运算数类型、*等操作要求操作数是数值类型两个字符串相加函数返回值非void函数必须有return语句非void函数执行完没返回这些检查的执行顺序也讲究先查符号表确定被调用的函数已声明再比对参数数量最后做类型兼容判断。顺序错了可能导致连锁报错。比如函数都没定义就先报参数不匹配这种提示会非常误导人。还有一个小细节符号表在报错时不仅会给出变量名还会顺便打印出当前作用域的变量列表。这个设计看似微不足道但对调试体验的提升非常明显。初学者看到error: variable c is not declared脑子里还会想“哪来的c”如果打印了一列可选变量基本能立刻定位是拼写错了还是引入了未声明的中间变量。3.3 函数调用与返回值检查的实现函数是语义分析里相对复杂的部分因为涉及到参数列表、返回值类型和调用栈的约束。在Hustcompilation2022中函数符号表项里存了返回类型、参数列表包括每个参数的类型和名字以及是否已经见过return语句的标志。每遇到一个return语句语义分析器会先检查当前是否处于函数体内再看表达式类型是否和函数返回类型匹配。如果函数返回类型是int你却写了return;不带值会直接报错。非void函数末尾缺少return的问题则是通过标记法在函数体AST遍历完成后检查的。这个检查在真实编译器中对应“流分析”的概念不是所有路径都需要一条return但简单项目为了避免“控制流到达函数结尾且没有返回值”的未定义行为会强制要求每个非void函数必须存在一个显示的return语句。虽然不完全等价于C的标准但作为教学项目已经够用。4. 中间表示与代码生成如何把AST变成可执行的东西4.1 在“虚拟机指令集”上执行而非直接生成汇编Hustcompilation2022没有直接生成x86汇编而是定义了一套自定义的字节码指令集然后写了一个解释器来执行这些指令。个人认为这是课设项目最明智的选择。如果真的奔着x86汇编去不仅需要处理寄存器分配还要考虑调用约定、栈帧布局、系统调用接口难度瞬间翻倍。项目定义的指令集类似简化版的栈式虚拟机PUSH_I32 推送一个32位整数到栈 PUSH_F64 推送一个64位浮点数到栈 LOAD_GLOBAL 加载全局变量到栈 LOAD_LOCAL 加载局部变量到栈 STORE_GLOBAL 将栈顶值存储到全局变量 STORE_LOCAL 将栈顶值存储到局部变量 ADD_I32 弹出两个整数做加法结果入栈 JMP_IF_FALSE 条件跳转 CALL 函数调用 RET 返回栈式虚拟机的好处是不需要考虑寄存器分配每个运算都把操作数压到栈上执行时弹出再计算结果继续压栈。理解起来和计算器后缀表达式的求值逻辑几乎一样。4.2 表达式、控制流和函数调用的翻译模式代码生成器遍历AST时对每种节点采用不同的翻译模板二元运算节点先递归生成左子树的指令再生成右子树的指令最后生成一条加法/减法/乘法/除法指令整数常量节点生成一条PUSH_I32指令变量读取生成一条LOAD_LOCAL或LOAD_GLOBAL取决于变量存储在哪个符号表作用域if语句生成条件的指令再生成JMP_IF_FALSE L_false然后是then分支指令再JMP L_end并在对应位置打上标签while循环标签之间维护循环体和跳转逻辑函数调用处理方面指令生成时会先计算参数表达式把实参值压栈然后生成CALL指令。执行时解释器创建新的调用帧把实参填入局部变量区执行函数体指令遇到RET时恢复调用帧。这一整套流程就是“调用栈”的雏形。虽然实现简陋和真正的汇编层面控制流相比少了很多细节但大方向完全正确。4.3 一个完整示例从源码到执行结果为了验证代码生成的正确性我特意写了下面这个测试程序int add(int a, int b) { return a b; } int main() { int x; x add(3, 4) * 2; if (x 10) { print(x); } else { print(x - 1); } return 0; }命令行执行编译再运行虚拟机后输出结果是14。其中add(3, 4)计算出7乘以2得到14大于10走if分支打印14。整个过程正确实现了函数调用、参数传递、算术运算和条件分支。测试通过那一刻对“从源码到可执行”的整条链路会有一个很直观的感受。5. 常见问题与排查技巧实录5.1 编译运行过程中的典型报错实际运行这份源码时如果自己改过语法最常见的几类问题如下问题现象可能原因排查方向所有token都识别为标识符关键字表没有初始化或查找逻辑写错确认关键字判断在标识符识别之后语法分析递归死循环parseExpression()调用parseAdditiveExpr()但后者不消费任何token就调用前者检查是否产生左递归或路径上缺少终结符消耗作用域内变量找不到符号表查找顺序反了先查父级再查当前确认查找方向是否从内向外函数调用栈溢出递归调用时没有设置终止条件或者调用帧没有正确恢复检查RET时是否恢复栈顶指针浮点运算结果恒为0中间代码把浮点常量截断成整数查看PUSH_F64的编码逻辑确认类型标记位其中最值得警惕的是第二类问题中文社区里常叫“无穷递归”本质是文法中有左递归且没有改写为迭代形式。比如一个规则expr: expr term如果parseExpr()第一件事就是调用自己而且没有先消费掉一个或其他token那么递归调用永远不会终止最终导致虚拟机栈溢出。5.2 调试Hustcompilation2022的独家技巧调试这种多阶段编译器最容易犯的错是在语法分析阶段就去纠结语义问题或者在代码生成阶段去猜测AST是否有误。正确的排查顺序是从前到后先确认词法Token流正确再用AST可视化功能确认语法树形状接下来用几个故意写错的测试用例确认语义检查能被触发最后才盯到中间代码。想要快速验证语义分析和代码生成是否正确有一个技巧故意往源码里塞入错误程序。比如“声明了但没使用”的局部变量、“调用一个不存在的函数”、“返回类型不匹配”的程序都应该能报出精确的错误信息。如果这些错误没被检查出来说明对应阶段的遍历逻辑还需要修。这份项目的AST可视化输出是我最推荐优先利用的调试工具。一旦语法分析跑完你立刻可以把AST打印出来看一眼括号和优先级的问题在AST形状里几乎是透明的。5.3 压缩包使用中的几点提醒最后补充一下关于这份zip压缩包本身的使用细节项目依赖的编译环境是标准C11基本g/clang都能直接编译配置起来不麻烦。建议先跑make再跑make test检查环境是否正常如果遇到中文路径解压后编译报错多半是编码问题把项目移动到全英文路径下再编译配合哈工大陈鄞老师的编译原理视频课来看这份源码效果会好不少。视频负责建立整体框架源码负责展示具体落地时的边界条件和细节处理不建议在拿到代码后直接改掉函数名和变量名糊弄老师。真正把这份代码读通透再自己手写一个简化版收获完全不一样如果你希望在这个项目基础上做扩展可以试试添加布尔与逻辑短路求值、数组类型、字符串拼接或者增加一层优化Pass去做常量折叠和死代码消除。每加一个功能你就对编译器的“前端与后端的藕合”多一分理解。EOF本文还有配套的精品资源点击获取