简介面向编译原理课程与学生实践的一份完整编译器工程基于SysY2022语言规范开发实现从源代码到可执行机器码或LLVM中间表示的完整编译流程。项目清晰划分词法分析、语法分析、语义分析、中间代码生成、代码优化与目标代码生成等阶段并通过多个头文件与源文件模块化组织核心逻辑同时附带SysY2022语言定义PDF、Flex实验指导及丰富测试代码便于对照规范理解每一步实现原理。资源共39个文件压缩包仅1.1MB以C头文件与源文件为主另有词法规则文件、sy测试用例、Markdown笔记、txt说明文档和PowerShell自动测试脚本整体结构紧凑、开箱即用。目前已有60人学习下载适合希望在真实项目中掌握编译器前端与后端、或基于LLVM做进一步优化研究的读者。其完整实现和可运行特性为编译原理课程设计提供了一套可直接参考与扩展的实践蓝本。1. SysY编译器项目到底在编译什么先看懂SysY2022这盘棋如果你手里拿到这样一个SysY编译器项目的标题大概率是准备参加编译系统设计赛或者正在做一门编译原理课的大作业。SysY2022本质上是C语言的一个受限子集保留int/float、数组、函数与递归、if/else、while/for这类核心控制流砍掉指针、结构体、宏和预处理。题目要求你做的不只是一个解释器而是要把SysY源程序完整走完词法、语法、语义分析生成LLVM中间表示再通过后端落到机器码或者可执行文件。这个标题背后其实是一套标准答案明确的工程路径——语言被框得很死真正考验的是编译器的工程化能力比如作用域怎么管理、SSA怎么处理、数组访存怎么用GEP表达。适合谁适合打比赛、做毕设、或者想补全“从源码到机器码”完整认知的开发者和学生刷过一遍这个流程再看LLVM其他前端或者自研后端会顺很多。2. SysY2022语言定义的取舍先把前端能处理的东西框死SysY2022的定义把一个C编译器最常见的前端工作量砍掉了大半。它保留了int和float两种基本类型支持一维和多维静态数组不支持变长数组数组维度必须是编译期常量函数允许递归参数可以是数组控制流覆盖if/else、while、for、break、continue、return运算符包括算术运算、比较运算、逻辑运算和赋值。main函数必须返回int不能带参数。砍完之后编译器前端依然是完整的词法、语法、语义流程但文法规模比C小一个数量级正好适合在一个学期或一个赛期内做透。2.1 手写递归下降还是生成器前端选型的核心理由大多数SysY项目会选手写递归下降而不是flex/bison。原因是SysY的表达式优先级层级固定、关键字表很小递归下降可以直接在解析函数里控制错误位置和错误信息用生成器虽然省去部分手写代码但生成出来的parser遇到语义错误时错误定位往往变成黑匣子。我在类似项目里习惯用一个简单的词法分析器加十几个递归下降函数整体量不大且好调试。// 词法分析先把 SysY 关键字和标识符分清楚 static const unordered_mapstring, TokenKind keywords { {int, TK_INT}, {float, TK_FLOAT}, {void, TK_VOID}, {if, TK_IF}, {else, TK_ELSE}, {while, TK_WHILE}, {for, TK_FOR}, {break, TK_BREAK}, {continue, TK_CONTINUE}, {return, TK_RETURN}, {const, TK_CONST}, }; Token nextToken() { while (isSpace(c)) c getChar(); if (isalpha(c) || c _) { string s; while (isalnum(c) || c _) { s c; c getChar(); } auto it keywords.find(s); if (it ! keywords.end()) return Token(it-second, s); return Token(TK_IDENT, s); } if (isdigit(c)) { // SysY 只要求十进制整数和浮点数别被 C 的十六进制带偏 string s; while (isdigit(c) || c .) { s c; c getChar(); } if (s.find(.) ! string::npos) return Token(TK_FLOAT_LIT, s); return Token(TK_INT_LIT, s); } // 运算符和标点符号需要做最长匹配 ! 这些优先 }这段代码的逻辑分两层关键字表和标识符识别分开浮点字面量只按十进制处理。SysY不要求支持十六进制、八进制或科学计数法的字面量词法阶段不需要做得比C更宽。如果你在词法里混入了十六进制后续语义检查和评测样例反而容易在边界翻车。运算符的最长匹配要单独写因为、、、!如果按单字符切分语法分析阶段会非常痛苦。常见写法是先读一个字符再看下一个字符能否组成双运算符形成Token后再决定是否需要stderr输出警告。把词法阶段做扎实后面语法分析踩坑的几率会小很多。2.2 AST优先还是语法制导翻译语义检查与IR生成的分工新手最常见的冲动是在语法分析动作里直接生成LLVM IR也就是语法制导翻译。SysY的语法规模看着不大但一旦遇到短路求值、for循环作用域、多维数组和函数嵌套调用直接生成IR会让代码变成一坨纠缠不清的拼接逻辑尤其当你想在IR生成前做一轮独立的语义检查时会寸步难行。我一般会先构建AST再在AST上做类型检查和常量折叠最后才走IR生成。这样每一层只解决一个问题出了错误也能定位到是语法、语义还是IR生成阶段。// AST 节点先定义表达式、语句、函数的最小公共结构 struct Expr { enum Kind { INT_LIT, FLOAT_LIT, IDENT, BINARY, UNARY, CALL, ASSIGN } kind; Type ty; // 语义分析后回填的类型 int intVal; float floatVal; string name; // 标识符 string op; // 二元/一元运算 unique_ptrExpr lhs, rhs; vectorunique_ptrExpr args; }; struct Stmt { enum Kind { EXPR, BLOCK, IF, WHILE, FOR, RETURN, BREAK, CONTINUE } kind; unique_ptrExpr expr; vectorunique_ptrStmt body; // 复合语句 unique_ptrStmt thenStmt, elseStmt; // if/else };AST设计不需要一上来就完整建模C的所有节点SysY的控制流和表达式种类有限上面的最小结构已经能覆盖绝大多数评测用例。要注意的是把数组类型和维度信息放进Type而不是散落在节点里因为语义分析和IR生成都要反复查它。Type里记录dims和每一维的大小函数返回值和参数在符号表里也复用同一套Type这样类型检查的函数就不用写两份逻辑。2.3 作用域与符号表SysY类型检查绕不开的三个动作符号表是语义分析阶段的地基。SysY的变量作用域规则和C一致块内变量遮蔽外层同名变量函数参数属于函数最外层作用域。常见做法是用一个栈式符号表进入Block Stmt时push一层退出时pop查找时从栈顶向下遍历。除了变量表函数名要单独一张表因为SysY里变量和函数的命名空间是分开的靠一张表硬存会导致同名函数和变量冲突时报错报得莫名其妙。struct Symbol { string name; Type ty; bool isConst false; int offset 0; // 栈帧布局时填 Value* llvmVal nullptr; // LLVM IR 里的 alloca 或 global }; class SymTable { vectorunordered_mapstring, Symbol scopes; public: void push() { scopes.push_back({}); } void pop() { scopes.pop_back(); } Symbol* find(const string name) { for (auto it scopes.rbegin(); it ! scopes.rend(); it) if (auto f it-find(name); f ! it-end()) return f-second; return nullptr; } };SysY的类型检查在语义阶段至少要做三件事。第一const变量和常量数组必须当场折叠SysY的数组维度是编译期常量const int n 5; int a[n 1];这种写法能否通过取决于你的常量表达式求值器我一般会在语义分析时对const变量做一次常量表登记后续维度检查直接查表。第二int和float的隐式转换赋值、传参、双目运算两侧类型不一致时SysY沿用C的通常算术转换但IR生成时要显式插入sitofp或fptosi不能在IR层省略转换指令。第三return的类型检查SysY要求函数返回值类型与声明一致非void函数必须有returnmain返回int且不允许带参数。这些检查放在AST遍历阶段做比在IR生成时边拼边查要稳得多。评测热词里常出现的“编译器未包含main类型”报错往往就是因为main的定义没有被正确登记或IR里没有生成对应函数。3. 从AST到LLVM中间表示IR生成这条主线的落地细节把SysY源码编译到LLVM中间表示是标题里明文写出的交付物之一。但“生成IR”并不等于“生成一段看起来像IR的文本”真正的闭环是让生成的IR能被LLVM工具链接受并最终编译成可执行文件。我建议把IR当作产品而不是过程每次IR生成都跑一遍llc或clang验证可运行否则到了后端阶段你根本分不清是IR生成错还是后端编译错。3.1 从文本IR到可执行文件三行命令确认你的IR是活的不少新手在IR生成阶段一上来就用LLVM C API结果被IRBuilder、Module、Function的参数列表搞到崩溃。更快的路径是先把LLVM IR当作文本格式来拼确认你的语法树能稳定输出结构正确的IR文本后再考虑要不要换成API。文本IR的好处是人眼可读出错了能直接看到基本块和指令缺点是拼字符串没有类型检查稍不注意就会生成语义非法的IR。但作为第一阶段验证它非常值得。; 最小可运行的 SysY 程序int main() { return 0; } define i32 main() { ret i32 0 }# 用 clang 驱动 LLVM 工具链把 IR 文本编译成可执行文件 clang test.ll -o test ./test这条命令看起来简单但它验证了一整条链路IR语法合法、函数签名正确、模块结构完整。SysY程序的IR生成完成后最基本的要求就是clang test.ll -o test能够通过。这里有个参数经验如果你的IR里用了i64做索引而目标机器是32位RISC-Vllc默认会生成对应宽度的地址计算一般没问题但如果IR里出现i128这种不匹配类型后端会报错。IR生成阶段最好统一用i32做大部分整数运算指针索引用i64也可但要保持一致混用会让GEP和比较指令的类型关系越来越乱。3.2 短路求值与phi节点控制流里的两个长期饭票SysY的逻辑运算符和||和C一样要求短路求值。很多初版实现会把布尔表达式直接编译成算术与或先算左边再算右边最后用and i1或or i1合并。这在语义上完全不等于短路——右边表达式即使左边已经确定结果也照样被求值。如果右边是数组越界访问或者除零表达式程序行为就会和C语义不一致评测跑起来必翻车。; 对应 if (i n data[i] 0) entry: %t1 icmp slt i32 %i, %n br i1 %t1, label %and.rhs, label %and.end and.rhs: %ptr getelementptr inbounds [100 x i32], [100 x i32]* %data, i64 0, i64 %i %val load i32, i32* %ptr %t2 icmp sgt i32 %val, 0 br label %and.end and.end: %res phi i1 [ false, %entry ], [ %t2, %and.rhs ]这段IR的结构是左侧条件%t1为假时直接跳到and.end并且%res的值由entry块的前驱值false决定左侧为真时才进入and.rhs块求右侧表达式。phi节点是SSA形式里路径合并的标准答案它告诉LLVM进入and.end块时如果来自entry%res取false如果来自and.rhs取%t2。处理if/else的合并值、循环的迭代变量时phi几乎是躲不掉的很多SysY编译器的控制流bug都出在忘记在合并块里插入phi或者phi的前驱块列表和实际CFG不一致。调试phi问题有个实用技巧把生成的IR用llvm-as再lli跑一遍如果报“PHINode should have one entry for each predecessor”之类的错误说明前驱块集合和CFG不一致肉眼检查跳转目标就能定位。3.3 数组与GEP多维索引的IR操作与边界SysY的数组是静态数组IR里对应的是alloca出的一段连续内存。访问a[i][j]时LLVM要求的不是直接计算地址然后load而是用getelementptrGEP指令做类型化地址计算。GEP的索引列表必须和变量声明的维度类型匹配少一个索引或多一个索引IR能通过校验但算出来的地址完全错误。; int a[3][4]; 访问 a[i][j] %a alloca [3 x [4 x i32]], align 4 %row getelementptr inbounds [3 x [4 x i32]], [3 x [4 x i32]]* %a, i32 0, i32 %i %addr getelementptr inbounds [4 x i32], [4 x i32]* %row, i32 0, i32 %j %val load i32, i32* %addr这里第一个索引0是固定套路对应C里数组名到首元素的衰减层级第二个索引%i选中第i行然后第二个GEP在[4 x i32]*的基础上选中第j列。如果你把两个维度写进同一个GEP的索引列表把%addr的类型算成[4 x i32]*然后直接load得到的是一个数组而不是标量llc阶段就会报类型错误。SysY的多维数组参数在函数间传递时会退化成指向首行的指针比如int a[][4]在参数里等价于int (*a)[4]。处理这种情况时IR里的函数参数类型就不能再保留[3 x [4 x i32]]这样的完整类型要显式把参数声明成[4 x i32]*。这个退化逻辑不处理好函数内访问数组元素几乎必错——llc或者clang会报GEP的指针操作数类型不匹配。遇到这类问题先打印IR里变量声明的类型再对照GEP索引逐层检查别靠肉眼猜。4. 从LLVM IR到机器码后端选择的三种路径与适用边界SysY项目的第二个交付物是机器码。严格意义上绝大多数提交并不会直接输出裸的二进制机器码而是通过LLVM后端生成目标平台的汇编再由汇编器和链接器做成可执行文件。RISC-V是编译系统设计赛的常见目标架构因为指令集精简、工具链齐全评测也容易统一环境。从IR到可执行文件有三条路径可选工程量和可控性差别很大。4.1 三条后端路径llc降级、合入管道、手写指令选择第一条路径是直接用llc把IR降级为RISC-V汇编这是最稳、最省事的选择本地上游开发时也是主力路径。第二条路径是把LLVM后端的MachineFunctionPass合入你自己的编译管道适合想做后端优化研究的人但工程量大需要理解LLVM的SelectionDAG或GlobalISel流程。第三条路径是完全手写RISC-V指令选择从IR指令逐条映射到汇编指令适合想深入理解指令集的人但性能通常难以和LLVM后端竞争。路径适用场景优点需要补的零件llc 降级快速交付可运行版本零维护直接复用LLVM优化和指令选择运行时库、链接脚本合入LLVM后端管道做后端优化研究能捕获IR到机器码的细节MachineFunctionPass、TargetMachine理解手写指令选择教学或极简目标完全可控深入理解架构寄存器分配、指令调度、栈帧布局手写指令选择还有一个常见折中只对简化IR的子集做手写映射比如只支持IF/加减法/跳转其余指令直接输出.word占位或不支持。这个方案在赛前冲刺阶段很容易拖后腿我一般不建议作为主后端除非评测只要求很小的SysY子集。# 把生成的 LLVM IR 降级成 RISC-V 32 位汇编 llc -marchriscv32 -mattrm -O2 test.ll -o test.s # 用 riscv 工具链组装并链接运行时库 riscv64-unknown-elf-gcc -marchrv32im -mabiilp32 test.s libsysy.a -o test.elf -nostdlib -static注意-mattrm是开启RISC-V的乘除扩展SysY的整数乘除依赖它-mabiilp32对应32位整数/指针的软浮点调用约定。如果SysY程序里有float运算但你没开f或d浮点指令会被降级成软浮点调用性能差但正确性没问题。另一个常被忽略的参数是-O2它是LLVM的IR优化级别也作用于后续指令选择。如果你在IR生成阶段没做优化llc的-O2会帮你清理不少垃圾指令但也会暴露SSA结构问题建议先-O0跑通正确性再上-O2。4.2 运行时库SysY IO函数如何进可执行文件SysY程序要支持输入输出靠的是getint、getch、putint、putfloat这类运行时库函数。SysY编译器不需要自己实现这些函数的IR常见做法是维护一个libsysy.c用本地编译器编译成目标文件或静态库在最终链接时和你的IR产物一起链接。你生成的IR里只需要为这些函数声明引用不必定义。// libsysy.cSysY 评测需要的运行时 IO链接时静态打进可执行文件 #include stdio.h int getint() { int x; scanf(%d, x); return x; } int getch() { return getchar(); } void putint(int x) { printf(%d, x); } void putfloat(float x) { printf(%f, x); } void putarray(int n, int a[]) { for (int i 0; i n; i) { if (i) printf( ); printf(%d, a[i]); } }在IR生成时如果一个SysY源程序调用了getint你需要保证模块里出现过declare i32 getint()这样的声明否则llc生成汇编后汇编器不会知道getint这个符号的存在最终链接时报undefined reference to getint。我之前在这个问题上踩过坑——生成IR时用了统一的函数调用封装但忘记为库函数生成declare结果本地编译能过换到评测环境就全线报链接错误。解决办法很简单在IR生成的初始化阶段把所有会用到的运行时函数全部declare一遍不要等调用时才临时补。4.3 优化开关与语义边界-O0到-O2到底差在哪LLVM后端的优化等级直接影响最终机器码也直接影响评测时间和运行结果。SysY的语义定义相对干净但依然有几个边界点在优化开关下容易出问题。第一个是整型溢出int在SysY里是32位i32加法溢出在LLVM IR里除非用nsw标记否则LLVM把它看成补码回绕如果你在IR生成时给每条加法都加nsw而源程序本身依赖回绕行为优化过后结果可能不符合预期。第二个是float到int的转换C标准里float转int在溢出时是未定义行为SysY评测常见做法是参考LLVM的默认行为但不同优化级别下fptosi生成的代码可能不同我建议在IR里显式使用fptosi不要靠隐式转换。第三个是未定义行为的暴露-O2会假设程序没有未定义行为并据此做变换如果你的SysY程序有数组越界或除零优化过的代码可能跑出更离谱的结果而-O0下往往还能碰巧得到预期输出。所以调试正确性用-O0测性能再上-O2不要一上来就开满优化然后被玄学bug折磨到深夜。5. SysY编译器从零到一最常踩的五个坑现象、根因与排查清单无论前端、IR生成还是后端失败模式都集中在几个典型场景。把每个坑按「现象 → 原因 → 解决」拆开讲能省掉大量排查时间。下面这几条都是我见过或亲身经历过的真实翻车现场按从编译到链接的顺序排列。5.1 编译器未包含main类型评测机的第一个报错现象提交到评测平台后反馈“编译器未包含main类型”本地却在终端跑出了正确结果。原因SysY要求main函数返回int且无参数但评测机检查的是IR或目标文件里是否存在define i32 main()。常见的翻车点有三个一是语法分析允许了void main生成的函数签名是define void main()类型不对二是main函数声明在符号表里没被登记IR生成阶段直接跳过三是IR里生成了declare i32 main()而不是define只有声明没有定义链接时找不到实体。解决在IR生成完成后加一个自检函数遍历模块里的函数列表确认存在且仅存在一个名字为main、返回类型为i32、无参数的函数定义。如果找不到直接报错并退出。用LLVM C API就遍历module.getFunctionList()用文本IR就直接grep生成文件里的define i32 main。这个自检还能顺带发现符号表漏登记的问题。5.2 短路求值写成了算术值和||的语义翻车现象while (i n data[i] 0)在i等于n时程序崩溃或者输出结果和C版本不一致。原因布尔表达式被编译成了算术与或LLVM IR里先把左右两边都算出来再执行and i1或or i1。右边表达式即使左边已经为假仍然会被求值数组越界、除零等副作用就会暴露。解决把二元布尔运算翻译成控制流而不是算术指令。a b的IR生成逻辑是左侧为假直接跳到合并块并让结果为假左侧为真才进入右侧求值块。a || b反过来。检查IR时不看结果指令看基本块的跳转关系——如果CFG里没有条件跳转直接进入右侧求值块基本可以判定没做短路。调试手段是把IR画成图或者对false (1 / 0 0)这种表达式做单元测试如果程序没有除零崩溃说明短路生效。5.3 数组越界与GEP维度错位地址算错一整排现象二维数组的元素访问在特定下标下输出错误但一维数组访问完全正常。原因GEP的索引列表和数组维度不匹配。声明int a[3][4]时IR里%a alloca [3 x [4 x i32]]访问a[i][j]必须用两个GEP索引层级第一层跳过外层数组选行第二层在行内选列。如果只用一个GEP却给了两个索引或者索引顺序写反得到的地址指向的不是a[i][j]而是别的行。解决把GEP索引列表和声明类型逐层对齐。打印IR时检查GEP后面的类型getelementptr [3 x [4 x i32]], [3 x [4 x i32]]* %a, i32 0, i32 %i这行的最后结果类型应该是[4 x i32]*然后在它之上再做一次GEP得到i32*。少一层GEP而直接load[4 x i32]*IR校验器会直接拒绝。遇到地址错乱最快的定位方法是写一个固定下标的小程序比如a[2][1] 7然后对生成的IR做符号执行或者用lli跑一遍看结果。5.4 编译器的堆空间不足递归下降被深嵌套表达式打爆现象编译一个中等规模的SysY源程序时编译器进程报“堆空间不足”或者栈溢出但源码本身逻辑很简单。原因递归下降解析器对表达式和嵌套块是深度优先递归。SysY表达式虽然层级固定但左结合表达式在解析时如果写成纯递归遇到几百个连续加法项就会压出很深的调用栈AST节点分配过多时内存也会快速膨胀。另一个常见诱因是AST构建时大量使用unique_ptr嵌套每个二元运算节点都递归持有子树深层嵌套括号会让析构递归同样深析构阶段触发栈溢出。解决表达式解析改成循环驱动的左结合解析不要一个加号递归一次括号处理保留递归但限制深度实践中可以加一个解析深度计数器超阈值直接报错提示输入过于复杂。AST析构如果成了瓶颈用一个全局的对象池或者改成显式节点树手动释放。这个坑在评测数据里有大量深度嵌套表达式时尤其致命本地小样例跑过不代表评测能过。5.5 链接时报undefined reference运行时库没接对现象本地编译通过评测报undefined reference to getint、undefined reference to putfloat这类链接错误。原因链接命令里没有包含运行时库或者你的IR模块里没有为这些库函数生成declare声明。SysY程序的IO调用在IR里是以外部函数引用的形式存在的最终链接时链接器必须从某个目标文件或静态库里找到函数定义。解决检查链接命令是否显式加入了libsysy.a或者libsysy.c编译出的目标文件检查IR文本里是否有declare指令。如果你用文本IR生成这一步很容易漏——因为declare和define在文本格式里长得像容易混淆。在IR生成代码里写一个运行时函数注册表把所有支持的库函数名、返回类型、参数类型登记好模块初始化时统一生成declare后续调用直接查表。链接命令建议固定写成clang test.ll libsysy.c -o test或riscv64-unknown-elf-gcc ... test.s libsysy.a ...不要靠环境变量或默认路径。6. 用差分测试验证你的编译器做对了从单点用例到批量评测验证一个SysY编译器做对没做对最有效的手段是差分测试同一个SysY程序分别用你的编译器和参考工具链编译运行逐行比较输出。SysY是C的子集所以常见做法是拿clang或gcc当参照——把SysY源文件复制成.c扩展名用本地C编译器编译出一个参照可执行文件再和你的产物跑同一组输入比较stdout。#!/bin/bash # 差分测试脚本对比你的编译器和 clang 在相同输入下的表现 for src in tests/*.sy; do base$(basename $src .sy) # 你的编译器生成 LLVM IR再用 clang 编译链接运行时库 ./sysyc $src -o $base.ll clang $base.ll libsysy.c -o $base.mine # 参照实现复制成 .c直接用 clang 编译 cp $src $base.c clang $base.c libsysy.c -o $base.ref # 用同一份输入跑两边逐行比较 echo 1 2 3 $base.in ./$base.mine $base.in $base.out1 ./$base.ref $base.in $base.out2 if diff -q $base.out1 $base.out2 /dev/null; then echo $src: PASS else echo $src: FAIL fi done脚本有三个参数经验第一输入文件要用同一个避免比较时因输入不同产生虚假的diff失败第二clang $base.c直接编译时SysY源里如果用了getint这类库函数要把libsysy.c一并编译进去否则参照程序跑不起来第三SysY程序如果涉及未定义行为比如数组越界clang在-O2下的行为和你的编译器在-O0下的行为可能故意不同这不能算你的编译器错但要在测试样本里排除这类用例。差分测试的样本尽量覆盖算术优先级、if/else嵌套、while和for的边界、多维数组、函数递归调用、短路表达式、float与int混算。如果你还处于开发中期只对单个用例做验证会浪费大量时间。我习惯在编译器里留一个--dump-ast和--dump-ir开关AST打印成缩进树IR直接输出文本一旦某个差分测试失败能立刻定位到是语义分析错还是IR生成错。我自己在这类项目里吃过最大的亏就是控制流合并时少加了一个phi节点生成的IR用lli跑某些样例正好是碰巧正确的换到循环次数不同才暴露。后来养成了每次改完IR生成逻辑就批量回归一遍差分测试的习惯虽然一开始麻烦后面省下的排查时间远超这点成本。希望这些路径和坑能帮你把SysY编译器项目推进得更顺少走几段我已经替你走弯的路。本文还有配套的精品资源点击获取