简介面向编译原理课程的 C-MIPS 编译器实验资源围绕精选的 C 语言子集实现完整编译链路借助 Flex 与 Bison 完成词法/语法分析通过语义分析构建符号表随后生成中间代码并利用 DAG 算法进行优化最终生成可供 MARS 汇编并在自制 CPU 上执行的 MIPS 目标代码适合计算机专业学生完成课程设计、撰写实验报告或复盘关键算法时使用。资源共 26 个文件压缩包约 1.26MB包含实验报告 PDF、Flex 词法文件.l、Bison 语法文件.y、C 源程序与头文件以及大量运行结果截图便于对照各阶段输出和验证测试过程。已有 533 人学习下载。从源码、报告到图片说明一应俱全既能帮助理解编译器各模块的工程实现也可为组合计组成原理的联动实验提供直观参考。1. C-MIPS 编译器实验把精简 C 语言一路编译到能在 MARS 里跑的 MIPS 汇编如果你正卡在编译原理实验的“目标代码生成”这一步或者想找一个能完整走通词法、语法、语义、中间代码、优化到目标代码的参考实现这份基于精简 C 语言的 C-MIPS 编译器项目值得你花一个晚上拆开看。它不是教学 PPT 里那种只解析到语法树就停的玩具而是真正把“for 循环 数组 函数调用 结构体”翻译成 MIPS 汇编并且能在 MARS 模拟器里跑出和原 C 程序一致结果的完整编译器。全套代码由词法分析器 lex.l、语法分析器 parser.y、抽象语法树 ast.c、语义分析 Analysis.c、目标代码生成 TargetCode.c 和 DAG 优化器组成测试程序最终还能落到计算机组成原理课设的 CPU 上执行。适合正在做华中科技大学编译原理实验的学生也适合想快速理解一个最小编译器各阶段之间数据流怎么衔接的从业者。2. 先看懂四份核心文件这套编译器各阶段之间到底怎么衔接2.1 从 lex.l 到 parser.yFlex/Bison 生成的不仅有语法树还有符号表素材打开压缩包先别急着找 README直接看 lex.l 和 parser.y 这两个文件的规模就能判断这个实验的完成度。lex.l 里定义了运算符、关键字、标识符、数字常量、字符串常量、注释的识别规则Bison 的 parser.y 里则写了完整的 C 语言子集文法。这里有一个容易看漏的设计实验要求选定一个“合适的 C 语言子集”这个子集的边界直接决定你后面语义分析的工作量。你会在 parser.y 里看到声明、函数定义、表达式、语句块、if-else、while、for、return、break、continue、数组声明与访问、结构体定义、函数调用、类型转换这些典型规则。Flex 和 Bison 的配合逻辑是lex.l 负责把源文件拆成 token每个 token 带行号和值返回给 parser.yparser.y 里的文法规则在归约时执行语义动作构建抽象语法树节点。这里有个关键点——symbol 表不需要在语法分析阶段就完整填字段只需要在声明节点里挂上变量名字符串真正的符号表构建放在后面的 Analysis.c 里统一做。这样设计的好处是语法分析阶段只管结构合法性语义阶段才管声明与使用的一致性。// lex.l 中一段常见的标识符与关键字识别规则精简示意 int { return INT; } char { return CHAR; } if { return IF; } while { return WHILE; } return { return RETURN; } [a-zA-Z_][a-zA-Z0-9_]* { yylval.str strdup(yytext); return IDENTIFIER; } [0-9] { yylval.intval atoi(yytext); return NUMBER; }这里yylval.str和yylval.intval是 Bison 的联合类型成员你在 parser.y 里用%union定义它们。遇到 IDENTIFIER 时用strdup拷贝字符串指针而不是直接存yytext因为yytext是 Flex 内部的缓冲区下一次匹配后内容就变了。这个坑几乎每个写编译器的都会踩一次strdup之后记得在 AST 节点释放时配套 free。2.2 AST 节点设计一个节点类型三类不同作用ast.c 里的节点定义是整个项目的脊柱。你会在 def.h 中找到节点结构体它通常包含节点类型、行号、操作符、左子节点、右子节点、额外子节点列表以及存储值或字符串的字段。实验要求“生成抽象语法树并打印之”所以你还会看到一套打印 AST 的函数——把括号嵌套的树形结构输出成文本方便验证语法分析是否正确。typedef enum { NODE_PROGRAM, NODE_FUNC_DEF, NODE_PARAM_LIST, NODE_DECL_LIST, NODE_STMT_LIST, NODE_IF, NODE_WHILE, NODE_FOR, NODE_RETURN, NODE_ASSIGN, NODE_ADD, NODE_SUB, NODE_MUL, NODE_DIV, NODE_IDENT, NODE_NUMBER, NODE_STRING, NODE_CALL, NODE_ARG_LIST, NODE_ARRAY_ACCESS, NODE_STRUCT_DEF, NODE_MEMBER_ACCESS } NodeType; typedef struct Node { NodeType type; int lineno; struct Node *left, *right; struct NodeList *extra; // 用于存储多条声明或语句 char *strval; int intval; // 符号表指针在语义分析阶段回填 struct Symbol *sym; } Node;节点里预留的struct Symbol *sym指针是语义分析阶段回填符号表用的。这意味着语法分析构建 AST 时不需要频繁查表只需要把标识符名字挂在节点上等到 Analysis.c 遍历 AST 时每进入一个作用域就把变量名和类型绑定关系填入符号表然后把符号表项指针写回 AST 节点。这样设计的好处是如果同一个变量名在不同作用域出现AST 节点各自持有自己作用域的符号表项生成目标代码时不会搞混地址。实验报告里你可以看到作者把 AST 打印结果截图并对比源程序结构这一步是验证语法规则正确性的最快手段。2.3 报告与 README十分钟定位实验要求和评分点压缩包里有一份《编译原理实验报告》和 README.md这是你理解作业要求的最短路径。报告里通常包含实验环境和运行方法Linux 下用 make 编译 lex.l parser.y Analysis.c TargetCode.c、文法说明、AST 打印结果、中间代码示例、优化前后对比、MARS 执行结果截图。README 会告诉你每个源文件的作用以及运行命令。提示先读 README 最后一段的运行命令再回头读 lex.l 和 parser.y。很多同学一上来就啃文法定义结果浪费了大量时间在理解函数声明规约上其实先用一段简单 C 程序跑通整个链路再回头对比文法会发现容易很多。3. 语义分析与符号表遍历 AST 时这三类检查最容易翻车3.1 符号表的作用域链同一变量名在不同函数里不能串Analysis.c 实现语义分析器核心数据结构是符号表。这个阶段你需要遍历 AST遇到函数定义时新建一层作用域遇到声明语句时在当前作用域插入变量。实验中要求检查“上下文是否有语义错误”常见检查包括变量未声明就使用、函数重复定义、形参和实参数量不匹配、数组下标类型非法等。作用域用链表实现就够了——每进入一个函数或一个语句块就压一个新的作用域栈当前查找时从栈顶往下找这样内层变量会遮蔽外层同名变量。typedef struct Symbol { char *name; TypeInfo type; // int / char / int* / struct 类型 int is_array; int array_size; int is_func; int param_count; TypeInfo *param_types; // 布局信息在目标代码生成阶段回填 int stack_offset; int is_global; } Symbol; typedef struct Scope { Symbol **symbols; int count; struct Scope *parent; } Scope; // 遍历 AST 时进入函数定义节点后 push 新作用域 void push_scope(Scope **current) { Scope *s calloc(1, sizeof(Scope)); s-parent *current; *current s; }这里的 TypeInfo 需要支持基本类型和自定义结构体类型。如果实验要求支持结构体你还需要维护一个“结构体名 → 成员列表”的全局映射否则解析struct point p; p.x时找不到和 x 对应的偏移量。我一般建议在符号表里单独开一个结构体定义表不跟普通变量混在一个作用域里因为结构体定义不受作用域限制。3.2 类型检查的三个常见漏洞隐式 int、数组下标、函数实参类型检查这步很多人写得太简略导致目标代码生成阶段反复出问题。我总结了三个最容易漏掉的检查点这也是实验评分时老师爱挑刺的地方。第一C 语言允许隐式 int但实验子集如果没有明确要求建议强制所有声明写类型遇到没有类型的声明直接报错否则后面寄存器分配时根本不知道要加载 8 位还是 32 位。第二数组访问要检查下标类型和数组维度a[1][2]在子集里如果不支持二维数组遇到就报错第三函数调用时要核对实参和形参数量一致并且类型匹配。这里给你一段语义检查的辅助函数骨架展示如何遍历表达式树同时查符号表和类型信息TypeInfo check_expr(Node *n, Scope *scope) { if (n-type NODE_IDENT) { Symbol *s lookup_symbol(scope, n-strval); if (!s) { fprintf(stderr, Error at line %d: undefined identifier %s\n, n-lineno, n-strval); exit(1); } n-sym s; // 回填符号表指针 return s-type; } if (n-type NODE_ADD) { TypeInfo lt check_expr(n-left, scope); TypeInfo rt check_expr(n-right, scope); if (lt.base_type ! TYPE_INT || rt.base_type ! TYPE_INT) { fprintf(stderr, Error at line %d: operands of must be int\n, n-lineno); exit(1); } return int_type; } // 其他表达式类型检查省略... }你注意我把类型检查结果和符号表回填放在同一个递归函数里这个设计是成功的。因为后续中间代码生成还要再遍历一次 AST那时直接读n-sym拿到符号表项不需要再查一次表。很多网上流传的版本在这里会写两遍遍历一遍做类型检查一遍生成中间代码导致符号表指针在 AST 节点上反复查找而且容易产生“同一变量在不同地方解析出的符号表项不一致”的隐蔽 bug。3.3 打印语义分析结果在生成中间代码前救你一命实验报告里通常要求展示符号表内容这看着像走形式其实非常有用。在 Analysis.c 里加一个 dump 函数把当前作用域的所有变量按顺序打印出来包括名字、类型、函数标记、参数个数。当源程序用了int a; int a;重复声明时符号表会立即暴露两层结构是否被正确维护。我还习惯在每次 push_scope 和 pop_scope 时打印一条缩进日志这样能直观看到作用域嵌套关系还不影响最终输出。void dump_scope(Scope *s, int depth) { for (int i 0; i s-count; i) { Symbol *sym s-symbols[i]; for (int j 0; j depth; j) printf( ); printf(%s type%d array_size%d is_func%d\n, sym-name, sym-type.base_type, sym-array_size, sym-is_func); } }这段代码没出现在你要交的正式输出里但它帮你排查了 80% 的语义错误。例如声明int a;后 a 的 array_size 应该为 0如果是垃圾值说明符号表结构体里存在未初始化字段目标代码阶段数组变量和普通变量会混在一起分配栈空间最后运行结果面目全非。4. 中间代码生成与 DAG 优化四元式设计和子表达式提取的取舍4.1 四元式四元式op, arg1, arg2, result 怎么安排临时变量中间代码生成器在语义分析器之后继续遍历同一棵 AST只是这次不再做类型检查而是生成四元式。实验要求“在语义分析器的基础上在同一遍遍历语法树的基础上利用当下的符号表生成中间代码”所以你需要维护一个四元式数组每个元素包含操作符、两个操作数和一个结果。typedef enum { OP_ADD, OP_SUB, OP_MUL, OP_DIV, OP_ASSIGN, OP_LABEL, OP_GOTO, OP_IF_FALSE_GOTO, OP_RETURN, OP_CALL, OP_PARAM, OP_FUNC_START } OpCode; typedef struct { OpCode op; char *arg1; // 操作数名字或临时变量名 char *arg2; char *result; // 目标操作数 int lineno; } Quad; Quad quads[MAX_QUADS]; int quad_count 0; char *new_temp() { static int temp_id 0; char buf[32]; sprintf(buf, t%d, temp_id); return strdup(buf); }表达式a b * c生成的中间代码大致是t1 b * c t2 a t1这里操作数有两种来源一是源程序里的变量名二是临时变量名 t1、t2。所有临时变量都不进入符号表它们的“类型”需要额外维护一个临时变量类型数组因为a b如果是 char 加 int目标代码生成时要决定加载宽度。我建议临时变量的类型在生成四元式时就推导好比如t1的基类型等于乘法结果的类型避免目标代码阶段再去猜。4.2 DAG 优化公共子表达式提取和死代码删除的实际操作优化器要求“接收中间代码利用 DAG 算法生成图并在此基础上进行代码重构和优化”。DAG 节点表示四元式中的运算或变量相同运算和相同操作数的节点合并这样公共子表达式只保留一个计算。例如x a b; y a b;在 DAG 里a b只算一次。typedef struct DAGNode { OpCode op; char *name; // 如果是叶子节点存变量名 struct DAGNode *left, *right; char *temps[MAX_USES]; // 记录有哪些新变量依赖该节点 int temp_count; } DAGNode; DAGNode *find_or_create_node(OpCode op, DAGNode *l, DAGNode *r) { // 遍历已有节点若存在同 op 且 left/right 相同的节点则返回它 for (int i 0; i dag_node_count; i) { DAGNode *n nodes[i]; if (n-op op n-left l n-right r) { return n; // 命中公共子表达式直接复用 } } // 没有则新建节点 DAGNode *n calloc(1, sizeof(DAGNode)); n-op op; n-left l; n-right r; nodes[dag_node_count] n; return n; }注意find_or_create_node比较的是指针而不是字符串值这就要求同一变量在任何地方出现都指向同一个 DAG 叶子节点。整个优化阶段一个叶子节点代表一个变量名而不是变量的某一次取值。这个细节直接决定了a a能否被正确识别为公共子表达式——如果你为取变量 a 建了两个叶子节点DAG 就完全失效了。死代码删除在 DAG 上的实现方式是构建完整的 DAG 后重新生成中间代码时只保留那些被外部引用或最终被输出使用的节点。如果一个节点的temps列表为空且不是函数返回值说明它计算出来的临时变量没人用就在输出时跳过。DAG 优化效果最明显的场景是循环里的重复计算例如for循环内每次计算i * 4这个乘法在循环中结果不变就能提到循环外——虽然实验不要求做循环不变式外提但 DAG 会自然消除同一基本块内的重复表达式。4.3 中间代码生成后怎么自查三地址码直接和 C 源码逐行对照中间代码是最容易“看起来没问题实际上错得离谱”的阶段。我的做法是打印中间代码时带上四元式原始行号然后和 C 源程序逐行对照每个 for 循环的初始化、条件判断、增量表达式都应该有对应的 label 和 goto每个函数调用应该出现 PARAM CALL 组合每个 return 应该生成 RETURN 四元式。典型翻车现场条件语句处理中if (a b)翻译成中间代码时需要先计算a b得到一个布尔值然后if_false goto else_label。有些实现会把比较操作直接编码成if_goto而不是先算布尔值这会导致目标代码里出现纯bgt指令寄存器分配阶段反而更难处理。我建议的统一模式是所有比较都先t a b再if_false t goto label——先生成比较结果到临时变量后续优化可以根据上下文把这两条四元式合并成条件跳转指令实验没要求但也为后续扩展留了路。5. 目标代码生成与寄存器分配的实战细节MIPS 汇编里的那些坑5.1 寄存器分配状态机优先用临时寄存器还是变量寄存器TargetCode.c 接收中间代码序列根据中间代码节点的类型为临时变量和存储变量分配寄存器生成规范的 MIPS 汇编。MIPS 有 32 个通用寄存器实验通常限定用$t0至$t9十个临时寄存器和$s0至$s7八个保存寄存器。临时变量适合用$t系列寄存器因为调用者负责保存源程序变量和全局变量则使用$s系列在函数调用边界进行保存与恢复。typedef struct { char *var_name; int reg_num; int is_temp; } RegAllocEntry; RegAllocEntry reg_table[MAX_REGS]; int reg_count 0; // 为一个交互四元式分配寄存器 int alloc_reg(char *var) { // 先在已分配列表中查找 for (int i 0; i reg_count; i) { if (strcmp(reg_table[i].var_name, var) 0) return reg_table[i].reg_num; } // 分配一个新的优先使用 $t 系列 int reg -1; for (int i 0; i 10; i) { if (!reg_in_use_t[i]) { reg i; reg_in_use_t[i] 1; break; } } reg_table[reg_count].var_name strdup(var); reg_table[reg_count].reg_num reg; reg_count; return reg; }这个分配策略有一个粗糙但致命的边界问题如果同一个变量在很长的表达式链中反复出现单个寄存器可能被占用过长。更强的做法是在四元式结果不再被引用后立即释放寄存器但实验子集规模下基本不需要。你要注意的是 MIPS 的$t0到$t9在函数调用时不会被保存所以跨函数调用的变量绝对不能放在$t寄存器里必须放到$s或者栈上。5.2 栈偏移与帧结构所有变量都有的后悔药是栈偏移MIPS 目标代码中局部变量通常分配在栈帧里通过$sp相对偏移访问。函数入口先addiu $sp, $sp, -frame_size函数出口addiu $sp, $sp, frame_size再加jr $ra。frame_size 由局部变量数量和临时变量溢出数量决定。最省事的做法是在符号表里为每个变量分配栈偏移int current_stack_offset 0; int alloc_stack_space(Symbol *s, int size) { current_stack_offset - size; s-stack_offset current_stack_offset; return current_stack_offset; }这里必须对齐到 4 字节边界即使变量是char类型也要分配 4 字节MIPS 内存访问按字对齐更省指令但实验子节允许用sb和lb访问字节。经验之谈是所有变量统一按 4 字节对齐分配char 变量也只使用低 8 位这样数组寻址base index * 4更规整不折腾大小端和位宽转换。5.3 如果你的测试程序出现“编译器堆空间不足”或 MARS 报错MARS 报错和编译器内存不足是两个层面的问题但学生在实验中常常混为一谈。MARS 运行汇编代码时如果申请数组或递归调用过深导致栈溢出它不会提示“堆空间不足”而是直接停在某个lw或sw指令处不更新寄存器状态。真正的“编译器的堆空间不足”问题发生在你的 C-MIPS 编译器进程里——c 语言写编译器时大量strdup产生内存碎片如果中间阶段不释放 AST 节点和符号表项几万行输入就可能耗尽堆内存。我的建议是在每完成一个阶段的处理后把不再使用的 AST 子树交给 free 函数释放尤其是语法分析阶段构建了全文 AST 的情况下语义分析和中间代码生成各遍历一遍之后就可以逐节点释放了。实验子节不测超大程序但如果你的测试程序用了大数组比如 1000 个 int中间代码临时变量数会指数级增长这时 DAG 优化器尝到甜头的同时也扛着内存压力——四元式数组上限开大一点老实用#define MAX_QUADS 65536而不是 4096。6. 编译运行与验证的完整流程MARS 模拟器下最后的 20 个坑6.1 从源码到 MARS 运行一条命令之外还要盯着三样东西实验要求用 MARS 汇编器将汇编代码汇编后运行结果需和 C 程序功能预期相符。MARS 不是 Linux 原生工具你需要单独下载 MARS.jar用java -jar MARS.jar启动。在命令行里可以这样批量运行# 假设你的编译器可执行文件叫 cmips ./cmips test.c test.asm # MARS 批量运行不打开图形界面 java -jar MARS.jar test.asm ncnc参数表示不加载默认启动指令适合纯汇编代码。MARS 默认从main标签开始执行所以你的目标代码生成器必须在汇编开头输出main:标签。如果运行结果不对先看寄存器窗口里$v0的值再看数据段里全局变量区域内容这样可以区分是寄存器分配问题还是内存布局问题。6.2 避坑常见问题清单现象 → 原因 → 解决第一个高频问题.data段声明数组后MARS 运行时报 address out of range。这种现象的根源是目标代码里数组访问用了错误寻址方式。解决方法是检查数组地址加载是否用了la指令而不是直接把标签名当作地址寄存器。数组元素访问时lw $t0, array($t1)的语法要求$t1是偏移量很多初版代码写成lw $t0, array8MARS 不认这种伪指令之外的复杂表达式。第二个高频问题函数调用后所有保存寄存器里的全局变量值全乱了。原因在于目标代码生成时没有在jal调用前保存$s寄存器调用结束后没有恢复。解决办法是在函数序言里把用到的$s寄存器全部sw到栈里结语中lw恢复。如果你的目标代码只用了$t寄存器则完全没有这个问题因为$t由调用者保存——但这是两种设计看你的中间代码生成器用了哪类寄存器。第三个高频问题if条件判断错误跳转方向刚好相反。根因是中间代码里的布尔表达翻译和 MIPS 条件跳转语义的负负得正。比如if (a b)翻译成四元式时先算出t a b再生成if_false t goto else_labelMIPS 里对应bge指令这会天然反直觉。排查时直接打印出中间代码找到IF_FALSE_GOTO这条四元式再检查生成的bge/blt指令是否互补。第四个高频问题递归函数里局部变量互相覆盖。原因是所有函数共用同一个栈帧偏移方案没有在调用子函数前把局部变量压栈。在递归场景下main里分配给局部变量的$sp偏移出的位置在被main调用的函数里被复写。解决方法是每个函数拥有自己独立的帧偏移区调用者要在函数序言中保存返回地址$ra和寄存器在结语中恢复。6.3 验证方法做对了的编译器应该长什么样做完以上步骤你需要一个自动化的验证脚本把多个测试程序分别用 C 编译器和你的 C-MIPS 编译器处理比较结果。在你自己的 Linux 环境里写一个循环测试脚本for f in test1.c test2.c test3.c; do echo $f # 原生 gcc 编译并跑出结果 gcc $f -o ${f%.c}_gcc ./${f%.c}_gcc # 你的 C-MIPS 编译产生汇编 ./cmips $f ${f%.c}.asm # MARS 汇编并提取输出值 java -jar MARS.jar ${f%.c}.asm nc | grep ^OUTPUT: done注意 MARS 里打印一个整数需要调用 syscall目标代码生成器必须在汇编代码里包含一个输出函数或者直接生成li $v0, 1syscall序列。如果你的测试程序用printf那还需要实现一个是否支持printf格式串的决定——大多数实验子节只允许putint(int)这类自定义输出而不是真正翻译printf调用。我见过很多同学把 C 标准库函数硬编码进目标代码生成器最后 MARS 里printf的字符串格式化处理炸掉实际上实验要求只测“程序功能预期”完全可以用输出数值来比别给自己找麻烦。最后一条习惯我现在一直保留着每次改完代码强制走一遍test → dump_ast → dump_quad → MARS run → diff的完整流程中间任何一步输出异常就立即停下查数据。从那以后我再也没有在目标代码生成阶段花一天时间“玄学调参”——其实九成情况都是前一级的结构信息在代码生成时没被正确传递而不是生成器本身的问题。希望帮到你。本文还有配套的精品资源点击获取