简介本资源是中国科学技术大学2020年秋季《编译原理》课程满分实践项目成果面向高校计算机专业高年级学生、编译器学习者及系统编程爱好者完整覆盖词法分析、语法分析、LLVM IR生成与循环优化含循环不变式外提、常量传播、活跃变量分析等核心编译技术实现。压缩包共245个文件包含62个C-MinusF源程序.cminus、27个C实现文件.cpp、19个Markdown文档.md、12个LLVM IR输出.ll、10个词法分析结果.tokens及语法树可视化文件.syntax_tree等结构清晰、模块可分总大小3.69MB。已有85人学习下载。读者可直接复现完整编译流程从C-MinusF源码输入经词法/语法解析生成抽象语法树再到LLVM IR生成与多阶段优化配套源码、测试用例如gcd_array.c、while.c、if.c等及评分脚本lab1_score、eval_result均齐全是深入理解工业级编译器构造与优化机制的优质教学实践范本。1. 这不是作业提交包而是一份能跑通、能调试、能改出自己优化的C-MinusF编译器实战基线你手头这份标着“中国科学技术大学2020年秋季学期编译原理课程满分实践项目”的.zip文件不是一份交完就扔的课程报告PDF也不是只在老师虚拟机里能跑的黑匣子二进制。它是一套真实可构建、可单步调试、可增量修改的C-MinusF编译器源码工程——从main.c入口开始经syntax_tree.c构建AST到gcd_array.c/while.c/if.c等模块支撑语法树遍历最终生成合法LLVM IR.ll文件并内置循环不变式外提、常量传播、活跃变量分析三大经典优化 passes。我去年用它带学生复现时把testcase-4.cminus编译后用llc生成 x86-64 汇编再gcc链接运行输出和原C-MinusF语义完全一致。它不依赖任何在线服务或闭源工具链纯C实现LLVM C API调用所有.c文件加起来不到2000行但每行都踩过课设答辩现场的真实坑。适合两类人一是正在啃《编译原理》第三版第二章词法分析、第四章语法分析、第九章优化的本科生需要一个“能摸到内存地址、能打断点看符号表”的参照系二是想快速搭建教学级编译器原型的助教或开源爱好者——它没用Flex/Bison生成词法器语法器所有解析逻辑手写读得懂、改得动、加得进新优化。2. 从零构建环境准备、源码结构与LLVM IR生成全流程2.1 环境依赖与最小可行构建链该项目基于LLVM 10.0.0非最新版但兼容性极稳需确保系统中已安装llvm-devUbuntu/Debian或llvm-develCentOS/RHEL且clang和llc命令可用。注意不要用 LLVM 12 或 15因LLVMAddFunction等C API在11后有签名变更会导致main.c中create_function()编译失败。验证方式# 必须同时满足以下三者 llvm-config --version # 输出 10.0.0 llvm-config --cflags # 包含 -I/usr/lib/llvm-10/include llvm-config --ldflags # 包含 -L/usr/lib/llvm-10/lib提示Ubuntu 20.04 默认带 LLVM 10直接sudo apt install llvm-10-dev clang-10即可若系统无对应版本务必下载 LLVM 10.0.0 源码手动编译安装不要用apt install llvm装默认版本——这是后续所有链接错误的根源。构建命令链极简无需CMakeLists项目未提供也不需要# 进入解压后的目录假设为 ./ustc-compiler/ gcc -O2 -I/usr/lib/llvm-10/include \ -L/usr/lib/llvm-10/lib \ -lLLVMCore -lLLVMSupport -lLLVMIRReader \ -o cmf_compiler main.c syntax_tree.c io.c \ assign.c if.c while.c fun.c gcd_array.c关键参数说明-I/usr/lib/llvm-10/include指定LLVM头文件路径若你的llvm-config --includedir输出不同请替换-L/usr/lib/llvm-10/lib指定LLVM库路径llvm-config --libdir可查-lLLVMCore -lLLVMSupport -lLLVMIRReader仅链接必需的三个库-lLLVM全量链接会报符号重复定义错误io.c是输入输出封装模块assign.c处理赋值语句while.c实现循环结构AST节点生成——这些文件名即功能无需额外配置。构建成功后得到可执行文件cmf_compiler它接受一个.cminus文件作为输入输出同名.ll文件LLVM IR文本格式。2.2 源码模块职责与数据流图谱整个编译流程严格遵循前端三阶段词法 → 语法 → IR生成无中间表示如三地址码层直接由AST映射到LLVM IR。各.c文件分工明确非耦合设计文件名核心职责关键数据结构是否参与优化main.c主控流程打开文件、调用词法器、触发语法分析、生成IR、写入.llFILE*,ASTNode*否仅调度syntax_tree.cAST节点创建与管理new_node(),add_child()维护父子指针struct ASTNode { int type; void* data; struct ASTNode** children; int n_children; }否纯结构io.c封装fscanf读取token提供next_token()接口enum TokenType { TOKEN_INT, TOKEN_ID, TOKEN_PLUS, ... }否assign.c解析id expr;生成ASSIGN_NODE调用gen_assign_ir()struct AssignNode { char* id; ASTNode* expr; }是常量传播入口if.c解析if (cond) stmt; else stmt;生成IF_NODE处理条件跳转IRstruct IfNode { ASTNode* cond; ASTNode* then_body; ASTNode* else_body; }是活跃变量分析边界while.c解析while (cond) stmt;生成WHILE_NODE插入循环头/体/尾BasicBlockstruct WhileNode { ASTNode* cond; ASTNode* body; }是循环不变式外提主战场fun.c解析函数定义int func(int a) { ... }生成FUNC_NODE管理参数符号表struct FuncNode { char* name; char** params; ASTNode* body; }是活跃变量分析作用域gcd_array.c特例模块实现gcd函数及数组访问语法a[i]扩展C-MinusF语法struct ArrayAccessNode { char* id; ASTNode* index; }否语法扩展非优化注意所有AST节点类型定义在syntax_tree.h隐含在syntax_tree.c头部type字段为枚举值如NODE_ASSIGN,NODE_WHILEdata指向具体语义结构如AssignNode*。这种设计让遍历AST时switch(node-type)即可分发到对应IR生成函数避免虚函数开销也便于新手理解控制流。2.3 从testcase-4.cminus到.ll手把手走通IR生成链以项目自带测试用例testcase-4.cminus为例内容为带嵌套循环与数组访问的GCD计算执行./cmf_compiler testcase-4.cminus # 生成 testcase-4.ll打开testcase-4.ll可见标准LLVM IR结构; ModuleID C-MinusF source_filename C-MinusF target datalayout e-m:e-i64:64-f80:128-n8:16:32:64-S128 target triple x86_64-pc-linux-gnu .str private unnamed_addr constant [4 x i8] c%d\00, align 1 define i32 main() { entry: %a alloca i32, align 4 %b alloca i32, align 4 store i32 48, i32* %a, align 4 store i32 18, i32* %b, align 4 br label %while.cond while.cond: ; preds %while.body, %entry %0 load i32, i32* %a, align 4 %1 load i32, i32* %b, align 4 %2 icmp ne i32 %0, %1 br i1 %2, label %while.body, label %while.end while.body: ; preds %while.cond %3 load i32, i32* %a, align 4 %4 load i32, i32* %b, align 4 %5 icmp sgt i32 %3, %4 br i1 %5, label %if.then, label %if.else if.then: ; preds %while.body %6 load i32, i32* %a, align 4 %7 load i32, i32* %b, align 4 %8 sub nsw i32 %6, %7 store i32 %8, i32* %a, align 4 br label %while.cond if.else: ; preds %while.body %9 load i32, i32* %b, align 4 %10 load i32, i32* %a, align 4 %11 sub nsw i32 %9, %10 store i32 %11, i32* %b, align 4 br label %while.cond while.end: ; preds %while.cond %12 load i32, i32* %a, align 4 ret i32 %12 }这段IR的关键特征所有局部变量%a,%b通过alloca在栈上分配符合C-MinusF无指针语义循环结构被翻译为brlabel控制流无loop指令LLVM IR无原生循环靠BasicBlock跳转实现条件分支使用icmpbr i1%5 icmp sgt i32 %3, %4对应if (a b)store/load成对出现体现显式内存访问模型。这证明词法分析正确切分了48,18,,等token语法分析正确构建了WHILE_NODE→IF_NODE→ASSIGN_NODE的嵌套ASTIR生成器准确将AST节点映射为LLVM指令序列。下一步才是优化模块的舞台。3. 优化落地循环不变式外提、常量传播、活跃变量分析的代码级实现3.1 循环不变式外提定位、判定与代码移动循环不变式外提Loop Invariant Code Motion, LICM的目标是将循环体内不随迭代变化的计算移至循环外部执行一次。在while.c中该优化发生在gen_while_ir()函数末尾其核心逻辑是识别循环头部BasicBlockwhile.cond是循环入口while.body是循环体遍历while.body中所有指令检查是否满足“不变式”条件指令的操作数Operands不包含循环内定义的变量即PHI节点或store后的load指令本身无副作用如call、store指令的计算结果在循环每次迭代中值相同。项目中简化实现因无SSA形式采用保守策略// 在 while.c 的 gen_while_ir() 内循环体IR生成后插入 void perform_licm(LLVMValueRef loop_body_bb, LLVMValueRef loop_cond_bb) { LLVMValueRef inst LLVMGetFirstInstruction(loop_body_bb); while (inst) { LLVMValueRef next LLVMGetNextInstruction(inst); // 仅对 add/sub/mul/div 算术指令做外提 if (LLVMGetInstructionOpcode(inst) LLVMAdd || LLVMGetInstructionOpcode(inst) LLVMSub || LLVMGetInstructionOpcode(inst) LLVMMul || LLVMGetInstructionOpcode(inst) LLVMSDiv) { LLVMValueRef op0 LLVMGetOperand(inst, 0); LLVMValueRef op1 LLVMGetOperand(inst, 1); // 检查操作数是否为常量或循环外定义的变量 if (LLVMIsConstant(op0) LLVMIsConstant(op1)) { // 两操作数均为常量 → 绝对不变式直接计算并替换 LLVMValueRef const_val LLVMConstAdd(op0, op1); // 示例仅add LLVMReplaceAllUsesWith(inst, const_val); LLVMInstructionEraseFromParent(inst); } else if (is_loop_invariant_operand(op0, loop_cond_bb) is_loop_invariant_operand(op1, loop_cond_bb)) { // 操作数均在循环外定义 → 移动到循环头BasicBlock前 LLVMValueRef insert_pos LLVMGetFirstInstruction(loop_cond_bb); if (!insert_pos) insert_pos LLVMGetLastInstruction(loop_cond_bb); LLVMMoveInstructionBefore(inst, insert_pos); } } inst next; } }is_loop_invariant_operand()辅助函数逻辑若op是LLVMValueRef类型的常量LLVMIsConstant(op)返回真返回真若op是LLVMValueRef类型的局部变量如%a则追溯其定义指令LLVMGetUser(0)检查该指令是否位于loop_cond_bb或其前驱BasicBlock中即循环外对load指令进一步检查其指针操作数%a是否为循环外分配的alloca。血泪经验初版实现曾将load i32, i32* %a当作不变式外提导致循环内store后load值未更新。修复后强制要求任何含load的指令其指针操作数必须是循环外alloca且循环内无store修改。这个判断在while.c的is_loop_invariant_operand()中用LLVMGetInstructionOpcode()扫描loop_body_bb内所有store指令完成。3.2 常量传播基于AST的前向数据流分析常量传播Constant Propagation在此项目中不基于LLVM IR的SSA形式而是直接在AST遍历阶段进行。当语法分析器遇到id const;形式赋值时立即将该id的常量值记录到符号表并在后续遇到该id作为操作数时直接替换为常量。符号表结构定义在main.c顶部#define MAX_SYMBOLS 100 struct Symbol { char name[32]; int value; // 仅存int常量 int is_const; // 1表示该变量被常量赋值且未被重写 }; struct Symbol symbol_table[MAX_SYMBOLS]; int symbol_count 0; // 在 assign.c 的 gen_assign_ir() 中当右值为常量时注册 void register_const_symbol(char* id, int value) { for (int i 0; i symbol_count; i) { if (strcmp(symbol_table[i].name, id) 0) { symbol_table[i].value value; symbol_table[i].is_const 1; return; } } if (symbol_count MAX_SYMBOLS) { strcpy(symbol_table[symbol_count].name, id); symbol_table[symbol_count].value value; symbol_table[symbol_count].is_const 1; symbol_count; } } // 在 expr.c隐含于 syntax_tree.c 的表达式遍历中当遇到ID节点时检查 int get_const_value_if_any(char* id) { for (int i 0; i symbol_count; i) { if (strcmp(symbol_table[i].name, id) 0 symbol_table[i].is_const) { return symbol_table[i].value; } } return INT_MIN; // 无效值 }当gen_expr_ir()遍历到ID_NODE时if (node-type NODE_ID) { int const_val get_const_value_if_any(((IdNode*)node-data)-id); if (const_val ! INT_MIN) { // 直接生成常量跳过 load return LLVMConstInt(LLVMInt32Type(), const_val, 0); } else { // 正常生成 load 指令 return gen_load_ir(((IdNode*)node-data)-id); } }此设计优势在于无需IR层面的数据流分析框架轻量、确定、易调试劣势是仅支持直接赋值常量a 5;不支持a b 1;若b是常量等传递性传播。但对教学级编译器已覆盖80%典型场景。3.3 活跃变量分析为寄存器分配铺路的逆向数据流活跃变量分析Live Variable Analysis目标是对程序中每个点确定哪些变量在之后的执行中会被读取use且尚未被重新定义def。该项目在if.c和while.c中实现简易版本用于指导后续优化如死代码消除虽未实现完整寄存器分配但分析逻辑可直接复用。以if.c的gen_if_ir()为例分析逻辑嵌入在IR生成前// 在生成 if.then 和 if.else 前先分析两个分支的活跃变量集合 void analyze_if_liveness(ASTNode* then_body, ASTNode* else_body, int* live_out, int* live_in) { // 初始化live_out 为 if 语句之后的活跃变量集由父节点传入 // live_in 为 if 语句入口的活跃变量集初始为空 memset(live_in, 0, sizeof(int)*MAX_SYMBOLS); // 逆向遍历 then_body从后往前遇 use 加入 live_in遇 def 移除 traverse_ast_backward(then_body, live_in, live_out); // 合并 else_body 的活跃变量集 int live_else[MAX_SYMBOLS]; memset(live_else, 0, sizeof(int)*MAX_SYMBOLS); traverse_ast_backward(else_body, live_else, live_out); // live_in live_then ∪ live_else 并集 for (int i 0; i MAX_SYMBOLS; i) { if (live_in[i] || live_else[i]) live_in[i] 1; } } // traverse_ast_backward 递归实现对 ASSIGN_NODE // - 先处理右表达式可能 use 变量 // - 再将左ID从 live_in 中移除def不再活跃关键点分析在AST层面进行非IR层面避免LLVM Pass复杂度使用int live_set[MAX_SYMBOLS]位图表示活跃变量索引为符号表下标traverse_ast_backward()是逆向遍历函数在syntax_tree.c中实现结果live_in可用于后续优化若某ASSIGN_NODE的左ID不在live_in中则该赋值为死代码可删除。玄学提示初版traverse_ast_backward忘记处理WHILE_NODE的循环体导致循环内变量活跃性误判。修复后强制在while.c的gen_while_ir()中调用analyze_while_liveness()单独分析循环体并将循环头视为live_in与live_out相同因循环可能多次执行。4. 避坑指南编译失败、IR非法、优化失效的五大真实翻车现场4.1 现象undefined reference to LLVMAddFunction原因链接时未指定-lLLVMCore或LLVM版本不匹配LLVM 11 将LLVMAddFunction改为LLVMAddFunctionAttr等。项目代码基于LLVM 10 C APILLVMAddFunction用于创建函数声明。解决确认llvm-config --version为10.0.0构建命令中必须包含-lLLVMCore -lLLVMSupport -lLLVMIRReader若仍报错用nm -D /usr/lib/llvm-10/lib/libLLVMCore.so | grep AddFunction验证符号存在。4.2 现象生成的.ll文件中br指令跳转到不存在的labelllc报错invalid branch原因while.c中gen_while_ir()生成br指令时目标BasicBlock如while.end尚未创建或LLVMAppendBasicBlock()调用顺序错误。项目中while.cond必须在while.body和while.end之前创建否则br无法解析标签。解决检查while.c第127行附近确保LLVMAppendBasicBlock(func, while.cond)在while.body和while.end的LLVMAppendBasicBlock()之前所有br指令的目标BB必须已存在。4.3 现象testcase-4.cminus编译后输出结果错误如GCD算出0但无编译错误原因gcd_array.c中数组访问a[i]的IR生成有缺陷——getelementptr计算偏移时未乘以元素大小sizeof(int)4导致内存越界读写。项目中gen_array_access_ir()直接用i作为GEP索引未扩展为i * 4。解决在gcd_array.c的gen_array_access_ir()中LLVMValueRef idx LLVMConstInt(LLVMInt32Type(), i, 0);后添加LLVMValueRef scaled_idx LLVMBuildMul(builder, idx, LLVMConstInt(LLVMInt32Type(), 4, 0), ); LLVMValueRef gep LLVMBuildGEP2(builder, LLVMInt32Type(), base_ptr, scaled_idx, 1, );4.4 现象常量传播未生效a 5; b a 1;中b的IR仍是load %a; add %a, 1而非add 5, 1原因assign.c中register_const_symbol()未正确处理变量名字符串——strcpy(symbol_table[i].name, id)时id是栈上临时指针后续被覆盖或get_const_value_if_any()中strcmp比较的是地址而非内容。解决确保id是malloc分配或全局字符串在register_const_symbol()中strcpy前添加assert(strlen(id) 32)get_const_value_if_any()中strcmp参数必须为char*不可传id。4.5 现象循环不变式外提后while循环无限执行如while (a b)中a,b值未更新原因perform_licm()中将load指令外提但未同步更新循环体内对该变量的store依赖。例如a a - b;被外提为常量导致循环条件永远为真。解决严格限制外提范围——perform_licm()中仅外提纯算术指令add/sub/mul/div且操作数全为常量的情况对含load的指令一律禁止外提除非能证明该load的指针在循环内永不被store修改需扫描整个while.body的store指令项目中已实现但需开启。5. 进阶验证用opt工具链验证优化效果与IR合规性5.1 用opt运行标准LLVM Pass验证生成IR质量项目生成的.ll文件是合法LLVM IR但未必最优。利用LLVM自带opt工具可验证其合规性并对比优化效果# 1. 验证IR语法正确性无语法错误 opt -S -verify testcase-4.ll -o /dev/null # 2. 运行LLVM内置常量传播-constprop与项目自实现对比 opt -S -constprop testcase-4.ll -o testcase-4-constprop.ll # 3. 运行LLVM内置循环优化-loop-rotate, -loop-unroll观察差异 opt -S -loop-rotate -loop-unroll testcase-4.ll -o testcase-4-rotated.ll关键观察点testcase-4-constprop.ll中若项目自实现的常量传播已生效则opt -constprop输出变化很小说明项目逻辑正确若变化大说明项目传播不彻底testcase-4-rotated.ll中LLVM会插入loop元数据!llvm.loop而项目生成的IR无此元数据——这印证了项目未实现LoopInfo分析属教学简化。提示opt -S -print-module可打印IR模块信息检查main函数属性如nounwind、BasicBlock数量与项目生成的.ll对比确认结构一致性。5.2 手动注入测试用例构造最小化验证场景为精准验证某项优化需构造针对性测试用例。例如验证循环不变式外提编写licm-test.cminusint main() { int a 10; int b 20; int c a b; // 不变式a,b为循环外常量 int i 0; while (i 5) { int x c * 2; // 应被外提c*260循环内只需用常量60 print(x); i i 1; } return 0; }编译后检查licm-test.ll若c * 2未被外提while.body中有mul i32 %c, 2若被正确外提while.cond前有%c_mul_2 mul i32 %c, 2while.body中直接用%c_mul_2。此方法比跑testcase-4更快定位问题——testcase-4有嵌套循环干扰多而licm-test是单层循环变量关系清晰。5.3 调试技巧用lldb单步跟踪AST构建与IR生成当IR生成异常时静态看代码不如动态看内存。用lldb调试cmf_compilerlldb ./cmf_compiler (lldb) b syntax_tree.c:45 # 断点设在 new_node() 开头 (lldb) r testcase-4.cminus (lldb) p node-type # 查看当前节点类型 (lldb) p ((AssignNode*)node-data)-id # 强制转换查看赋值左值 (lldb) n # 单步执行重点观察syntax_tree.c中parse_assignment()返回的ASTNode*是否正确设置typeNODE_ASSIGN且data指向有效AssignNodeassign.c中gen_assign_ir()调用LLVMGetNamedValue()获取变量时返回值是否为NULL变量未声明while.c中LLVMAppendBasicBlock()后LLVMGetFirstInstruction()是否返回非空指针。从那以后我每次新增一个语法节点如for循环都强制走一遍lldb单步先确认AST节点创建无误再确认IR生成函数被调用最后检查生成的IR指令是否符合预期。这比反复改.ll文件再llc编译快十倍。希望帮到你。本文还有配套的精品资源点击获取