简介：这是中国科学技术大学2020年秋季学期编译原理课程的满分实践项目，面向编译原理课程学生与编译器开发者，完整实现了一个C-MinusF编译器，覆盖词法分析、语法分析、LLVM中间代码生成，并集成循环不变式外提、常量传播、活跃变量分析等优化。资源共245个文件，压缩包大小仅3.69MB，包含数量丰富的C-MinusF测试用例、C++/C源码、语法树文件、LLVM中间代码、词法单元输出以及Markdown与文本文档，目录划分清晰，便于按编译流程检索。目前已有86人学习。通过这套资源可以系统对照词法token生成、语法树构建、中间代码产出与优化前后差异，测试用例覆盖条件判断、循环、函数调用等多种控制流场景，能帮助理解编译器从前端到优化的完整实现路径，也可作为课程设计或实验报告的结构参考。
1. 一次搞定编译原理课设：这份 C-MinusF 编译器实现能拿来即用
编译原理大作业最难受的不是写不出代码，而是不知道自己写的阶段到底哪一步断了线。这份来自中科大 2020 年秋季学期的满绩实践项目，能帮你把整条链路对清楚：从词法分析、语法分析，到 LLVM IR 生成，再到循环不变式外提、常量传播、活跃变量分析三类典型优化，全部围绕 C-MinusF 语言实现，不是那种只跑通一个 hello.c 的演示版。压缩包里是 main.c、syntax_tree.c 等核心源码，还有 testcase-4.cminus 这类验收测试样例，覆盖函数、数组、while、assign、if 的常见组合。适合课设做到一半卡在某个 pass 上的本科生，也适合想快速查一遍小型编译器如何组织优化代码的老手。
2. 词法与语法分析：手写扫描器与递归下降解析器的落地要点
2.1 词法 token 的结构与扫描规则
C-MinusF 的词法范围比完整 C 小得多：没有浮点数、没有字符串字面量，基本就是标识符、整数、保留字和运算符。但范围小不意味着可以随意编码，token 结构直接决定后面 parser 的写起来是否顺。用整型枚举而不是字符串常量，能省掉全项目到处strcmp的麻烦，也方便在报错里直接映射成可读文本。
下面是我在这个项目里常用的 token 结构，和 C-MinusF 的语法范围对应，你抄进 scanner.c 基本就能跑：
// token.h —— C-MinusF 的词法单元定义 typedef enum { TK_IDENT, TK_NUMBER, TK_INT, TK_VOID, TK_RETURN, TK_IF, TK_ELSE, TK_WHILE, TK_PLUS, TK_MINUS, TK_STAR, TK_SLASH, TK_LPAREN, TK_RPAREN, TK_LBRACKET, TK_RBRACKET, TK_LBRACE, TK_RBRACE, TK_SEMI, TK_COMMA, TK_ASSIGN, TK_LT, TK_GT, TK_LE, TK_GE, TK_EQ, TK_NE, TK_EOF, TK_ERROR } TokenKind; typedef struct { TokenKind kind; int line, col; union { int intVal; char ident[32]; } u; } Token;这样设计有两个落地原因：一是后续语法分析遍历 token 流时不需要回看原始字符，二是错误信息能精确定位到行号列号。intVal和ident放进 union 是为了省结构体空间，这个量级的项目不差这点内存，但 token 拷贝时确实更轻。
扫描器主循环的边界很简单：跳过空白和注释后，按首字符分类。数字要手动完整吞掉，因为while (i<n)里的<和<=必须靠第二位字符区分。很多人在这一步直接按字符切，遇到<=就得到一个<和一个=，语法分析阶段直接被坑。项目里处理方式是 peek 一位：是=归为TK_LE，否则TK_LT。逻辑土，但直白且不会漏操作符。
2.2 递归下降解析与优先级处理
C-MinusF 的表达式层级不复杂，但这不代表可以在 parser 里搞一个无限循环的优先级判断。对赋值、比较、加减乘除，要用独立 parse 函数把优先级串起来，而不是写一个巨型 stack 机去猜。常见做法是经典的分层嵌套：
// parser.c —— 表达式按优先级分层 static ASTNode* parse_assign_expr() { ASTNode* lhs = parse_lower_priority(); if (peek() == TK_ASSIGN) { get_token(); ASTNode* rhs = parse_assign_expr(); // 右结合 return make_node(NODE_ASSIGN, lhs, rhs); } return lhs; } static ASTNode* parse_lower_priority() { ASTNode* lhs = parse_additive(); while (is_compare_op(peek())) { Token op = get_token(); ASTNode* rhs = parse_additive(); lhs = make_node(NODE_BINARY, lhs, rhs); lhs->opKind = op.kind; } return lhs; }注意parse_assign_expr里赋值是右结合，这是为了处理a = b = 3这种连续赋值。如果按左结合实现，生成 IR 时临时变量顺序会反掉，活跃变量分析也会跟着偏。每个解析函数职责要单一：parse_primary只处理数字、标识符和括号，parse_unary只处理负号，加减、乘除各占一层。这样任何报错都能定位到优先级层的具体位置，不用顺着栈瞎猜。
2.3 AST 节点内存管理与生命周期
syntax_tree.c里最容易被低估的是节点内存。项目走递归下降，节点生命周期和递归栈保持一致：整个 parse 结束后 AST 定型，之后 IR 生成阶段只读不写。常见做法是设置一个统一的节点构造入口，把所有分配集中到一处，避免有的节点从 token 直接建、有的节点从子节点拼，最后释放时互相不认账：
ASTNode* make_node(NodeType type, ASTNode* left, ASTNode* right) { ASTNode* n = (ASTNode*)calloc(1, sizeof(ASTNode)); if (!n) { fprintf(stderr, "calloc failed\n"); exit(1); } n->type = type; n->left = left; n->right = right; return n; }等到 IR 生成结束后，再统一递归释放整棵语法树。这种“整体申请、整体释放”的粗粒度内存管理，在课设规模下反而比到处手动 free 更不容易漏。有些同学觉得程序马上结束不释放也无所谓，测试用例少时能蒙混过去，一旦样例扩到几百行、优化阶段反复遍历 AST，内存增长就会变得很难看。
3. LLVM IR 生成：把 AST 翻译成中间代码的关键写法
3.1 为什么优先选择文本 IR 而不是直接接 LLVM API
课程编译器大多选择直接输出 LLVM IR 文本，而不是链接 LLVM 库来构造 IR 对象。原因是后者会把调试复杂度转移到 C++ API 上，而文本 IR 可读、可 diff、可直接用lli跑，还能在优化前后做人工对比。对验收场景来说，你的老师最可能看的就是优化前后两份 IR 的差别。
这里的核心是维护一个临时变量编号器。每遇到一个需要求值的表达式，就申请一个新的临时寄存器号，按顺序累加：
// emit.c —— 整数加法的 IR 文本输出 static int tmp_seq = 0; static int emit_expr(ASTNode* node) { if (node->type == NODE_NUMBER) { return emit_imm(node->intVal); // 直接生成常量 } if (node->type == NODE_IDENT) { return emit_load(node->ident); // 从局部变量加载 } // 二元运算：先出左操作数，再出右操作数 int lhs = emit_expr(node->left); int rhs = emit_expr(node->right); int dst = tmp_seq++; fprintf(out, " %%%d = add i32 %%%d, %%%d\n", dst, lhs, rhs); return dst; }这一小段已经能覆盖整数常量和变量相加的主路径。注意fprintf里%%转义，LLVM IR 的变量名以%开头，C 的 printf 需要双写。生成结果类似%3 = add i32 %1, %2。如果你在这里漏写了i32类型，后面优化 pass 解析 IR 时会直接按格式错误拒绝。
3.2 控制流生成：if 和 while 的 label 插入时机
控制流的难点不在“生成跳转指令”，而在 label 的编号和插入顺序。顺序错了，IR 语法没错但语义不符合预期。常见的做法是维护一个全局 label 计数器，每次新块拿到一个新编号，然后严格按“条件块 → 分支 → 目标块”的顺序落盘。
下面这段是 while 循环的典型生成过程：
// emit.c —— while 语句的 IR 结构 static void emit_while(ASTNode* cond, ASTNode* body) { int L_cond = label_seq++; int L_body = label_seq++; int L_exit = label_seq++; fprintf(out, " br label %%L%d\n", L_cond); fprintf(out, "L%d:\n", L_cond); int t = emit_expr(cond); fprintf(out, " br i1 %%%d, label %%L%d, label %%L%d\n", t, L_body, L_exit); fprintf(out, "L%d:\n", L_body); emit_stmt(body); fprintf(out, " br label %%L%d\n", L_cond); fprintf(out, "L%d:\n", L_exit); }先发出一个无条件跳转进入条件块，每次循环从L_cond开始重新求值条件，条件为真进L_body，为假直接出循环。while(1)之类的死循环在 C-MinusF 里允许，但要注意生成时L_exit虽然没被引用，也要照常发出来，否则 LLVM 后端会报 “block has no predecessors” 的警告。
3.3 SSA 临时变量编号与 phi 的使用边界
严格按 SSA 形式生成的 IR，每个变量只会被赋值一次。最简单的做法是用一个单调递增的临时变量编号，从 0 开始往后发。遇到 if-else 合并时，需要在 merge 块里插入 phi 节点来合并两个分支的值：
// emit.c —— if-else 合并块的 phi 生成 fprintf(out, "L_merge:\n"); fprintf(out, " %%t%d = phi i32 [ %%%d, %%L_then ], [ %%%d, %%L_else ]\n", dst, val_then, val_else);phi 的参数格式是[value, label]，两边必须一一对应，label 必须是那个值来自的基本块。很多初学项目栽在这里：值对了，label 写错，lli加载 IR 时直接报 verification failed。如果你不想处理 phi，可以退化为每次变量更新都alloca一个槽、再用 load/store 兜底，但那样做循环不变式外提和常量传播的效果会大打折扣，因为这些优化依赖 SSA 的单一赋值特征。
4. 优化 Pass 实现：循环不变式外提、常量传播与活跃变量分析
4.1 循环不变式外提的安全条件
循环不变式外提的目标是把循环内每次迭代结果都相同的计算挪到循环外执行。前提有三条：指令操作数在循环内不被修改，指令本身没有副作用，循环体是自然循环且有明确的 preheader。前两条是安全条件，第三条是结构条件，缺一个都不能移动。
判断“能否外提”时，我一般用一个专门的can_hoist函数做状态限制：
// licm.c —— 判断指令是否可安全外提 static bool can_hoist(IRInstr* insn) { switch (insn->op) { case OP_CALL: return false; // 函数调用可能有副作用 case OP_STORE: return false; // 写内存不可提 case OP_LOAD: return false; // 指针指向的位置不确定 case OP_PHI: return false; // phi 依赖基本块结构 default: return true; } }这里最常见的问题是初学者只判断操作数是否被定值，而放过了call。假设循环体里有个gcd()调用，函数内部逻辑可能依赖全局变量，就算返回值在迭代间不变，把它提出循环也会改变函数被调用的次数，进而改变程序行为。所以can_hoist第一步先按 opcode 过滤，再查操作数。
移动目标通常是 preheader，即循环头的前置基本块。移动顺序要保持原顺序，避免把先后有依赖关系的一条指令拆散。项目里的写法是：先收集所有可外提指令，按原顺序排序，再统一插到 preheader 末尾。
4.2 常量传播的工作列表算法
常量传播的核心是维护变量到常量的映射表，并用工作列表驱动。每次发现某条指令的右操作数全是常量，就把计算结果折叠成一个新的常量，替换进映射表，再更新依赖它的所有使用点。顺序敏感，所以天然适合工作列表而不是简单的 for 循环。
// const_prop.c —— 工作列表迭代常量传播 static void run_const_prop(IRFunction* fn) { WorkList wl; for (int i = 0; i < fn->instr_count; i++) { IRInstr* insn = &fn->instrs[i]; if (all_operands_constant(insn)) wl.push(insn); } while (!wl.empty()) { IRInstr* insn = wl.pop(); if (insn->op == OP_ADD || insn->op == OP_MUL || insn->op == OP_ICMP) { Constant c = constant_fold(insn); if (c.defined) { replace_with_constant(insn->dst, c); update_users_of(insn->dst, &wl); } } } }关于replace_with_constant，真正要处理的是删除指令后把这条指令从所有后继的 use 集合里清掉。update_users_of负责遍历使用该寄存器的其他指令，重新判断它们是否满足全常量条件，是则加入工作列表。这样一轮轮迭代，直到没有任何新的可折叠指令出现。
4.3 活跃变量分析与寄存器分配的衔接
活跃变量分析解决的问题简单说就是：某个变量在程序点之后还会不会被使用。它的数据流方程是反向的，常用位向量实现，每个变量占一个 bit。方程不复杂，麻烦的是初始化。如果遗漏了 call 指令对实参的使用，整个分析结果都会偏。
// liveness.c —— 活跃变量分析的核心方程 // OUT[B] = ∪ IN[S] 对所有后继 S // IN[B] = use[B] ∪ (OUT[B] − def[B]) // 位向量方向：第 i 位代表 variables[i] 是否活跃实现时先为每个基本块建立use和def两个位向量，再反复迭代所有块，直到IN和OUT都不再变化。这里的隐藏成本是方程中的相对补集运算，变量数量到上百个时，每次循环都要做整数位移和掩码操作，性能会明显下降。
活跃变量分析本身不做优化，它是寄存器分配和死代码消除的前置分析。在课设项目里，一般用它来判断alloca出来的局部变量在函数返回后还有没有被使用，从而决定是否能安全删除一段赋值代码。若发现一个变量在定义处之后完全没有活跃点，就可以触发死代码删除，这个优化在 testcase 里很有效。
5. 避坑记录：改造这套编译器时最常翻车的三个场景
5.1 循环不变式外提把函数调用搬出了循环体
现象：优化后的 IR 里，原本在循环内的foo()调用只剩下一次，被提到了 preheader。程序输出结果完全变了，原本每次迭代都会打印一行，现在只打一行。
原因：外提判断只看“操作数是否在循环内被重新定义”，没有检查指令是否是 call。foo()的返回值确实不依赖循环变量，但函数本身有副作用，甚至可能修改全局变量，外提后副作用被跳过。
解决：can_hoist里显式拦截OP_CALL和所有涉及内存访问的 op（包括OP_LOAD、OP_STORE）。只有纯算术指令add/sub/mul/icmp才允许外提。再贪心一点的做法是允许纯读且指针在循环内不发生变化的 load，但我建议课设不要碰，收益低且验证成本高。
5.2 活跃变量分析把函数实参误判为死值
现象：lli加载生成的 IR 时报verification failed，具体信息指到一条调用指令，说参数数量或参数格式不匹配。检查发现活跃变量分析把%r = call i32 @gcd(i32 %a, i32 %b)里的%a和%b标记成了死值。
原因：分析初始化阶段，use集合里只收集显式出现的变量，而 call 指令的操作数没有被收集进去。写数据流方程时，把 call 的返回寄存器归到了def，却把实参忽略掉了。这一步看似微小，却直接破坏后续清洗代码阶段的正确性。
解决：构建use[B]时，把 call 指令的所有操作数都加入使用集合，再单独处理返回寄存器。这个顺序不能反过来，否则def会吞掉实参的使用信息。
5.3 常量传播把指针比较折叠成固定值
现象：while (p != NULL)在优化后被折叠成br label %0，循环体变成不可达，testcase-4 运行结果彻底出错。
原因：常量传播把null当普通常量 0 处理，而对p的地址来源没有做类型区分。一旦p是通过alloca分配的指针对变量，拿它跟 0 比较就不能当作恒真或恒假折叠。这个坑很隐蔽，因为改动只发生在一行常量表查询里。
解决：为常量映射表增加类型标记，只有i32或i1类型的整型运算结果允许折叠。指针类型、地址空间相关的操作（包括空指针比较）全部标记为不可折叠，除非你能在语义上证明比较的是普通整型变量。加一个type字段成本很低，但能挡住一整类语义错误。
6. 进阶验证：用 testcase-4.cminus 把编译全链路跑通一遍
拿到这份资源后，不要急着改优化代码，先把整条链路跑通一次，确认 baseline 行为和预期一致。我一般会准备一个临时目录，按“生成 IR → 单测 → 优化 → 回归”的顺序走一遍。下面是基础流程：
# 1. 构建编译器主体 gcc -O0 main.c syntax_tree.c -o cminusf # 2. 不做任何优化，直接生成原始 IR ./cminusf testcase-4.cminus -emit-ir -o base.ll # 3. 依次关闭/打开单个优化 pass，对比 IR 差异 ./cminusf testcase-4.cminus -O0 -emit-ir -o noopt.ll ./cminusf testcase-4.cminus -licm -emit-ir -o licm.ll ./cminusf testcase-4.cminus -constprop -emit-ir -o cp.ll ./cminusf testcase-4.cminus -liveness -emit-ir -o live.ll # 4. 用 lli 直接执行 IR，对比运行结果 lli noopt.ll lli licm.ll重点核对两份文件：优化前和优化后的 IR 是否在lli下输出一致，以及每个 pass 的开关是否真正改变了 IR 内容。若某个 pass 开启后 IR 完全没变化，大概率是 pass 的触发条件写死了，或者分析阶段没找到可优化点。
| 观察项 | 判断标准 |
|---|---|
| 循环不变式外提 | 循环体内相同加法是否被移动到 preheader |
| 常量传播 | a = 1; b = a + 2是否折叠为b = 3 |
| 活跃变量分析 | 有无死代码被识别并删除，lli是否报验证错误 |
验证时我会故意构造三个边界例子：一个是 500 次迭代的循环，一个是包含函数调用的循环，一个是指针比较的 while。这三个例子基本能覆盖上面避坑章节提到的全部翻车点。
从那次改完活跃变量分析没跑回归、直接交上去结果在 testcase-4 上炸掉以后，我养成了习惯：每次动 pass，不管改动多小，都强制把 baseline、单 pass、全量优化三份 IR 全部生成一遍，再用lli跑一次确认行为没变。这样折腾看起来慢，但比半夜查一条被错误折叠的跳转要快得多。希望帮到你。
本文还有配套的精品资源，点击获取
