Cminusf编译原理课设：词法到中间代码完整实现与避坑指南

简介面向重庆大学计算机学院编译原理课程学习者这份资料完整收录了围绕Cminusf语言从实验一到实验三的工程实现覆盖词法分析、语法分析、语义分析与中间代码生成四个核心编译阶段。压缩包内共361个文件约1.52MB以out、sy、tk、json等编译器中间产物与结果输出为主同时包含h/cpp源码、测试输入in、Python脚本、简易说明txt及可执行文件便于对照实验步骤复现调试过程。资源中除每阶段的完整代码实现外还附有详尽调试记录记录了关键步骤、问题诊断与解决方案帮助学生理解理论与实践差异并积累排错经验说明文件与主目录结构也降低了环境搭建和运行测试的门槛。目前已有78人学习下载。适合正在修读编译原理、需要完成Cminusf系列实验或希望梳理各编译阶段实现思路的本科生参考可作为课程设计、复习答辩与二次开发的起点。1. 编译原理课设三连击Cminusf 从词法到中间代码的完整闭环如果你以为编译原理课设最耗时间的是写代码那就错了。Cminusf 这门精简到极致的教学语言恰好把词法分析、语法分析、语义分析和中间代码生成四个实验串成一条完整的编译流水线而多数人真正卡住的是实验二之后递归下降的栈溢出、左递归死循环、符号表作用域错乱一调就是两三天。这套实验集合把实验一到实验三的完整代码实现和调试记录打包在一起每个实验怎么设计、在哪一步丢过分都有记录。适合正在跟 Cminusf 课设较劲的同学对照排查也适合想看一套可运行实现来理解编译流程的从业者。2. 先把 Cminusf 的底摸清一条流水线上的三个实验2.1 Cminusf 的语法子集为什么课设语言都长这样Cminusf 的定位是「刚好够讲完编译原理」的 C 语言子集。它保留了 int/void 两种类型、函数定义、变量声明、if/while/return 控制流以及带优先级和括号的算术、比较表达式砍掉了指针、struct、switch、for 这类会分散注意力的特性。有的版本会额外加数组和 float但核心骨架不变。这样一份语法规范足够覆盖词法分析里的关键字识别、语法分析里的表达式优先级、语义分析里的类型与作用域、中间代码生成里的控制流转换任何一个环节都不缺素材。比如下面这个阶乘程序就是一份典型的 Cminusf 源文件/* * Cminusf 样例循环求阶乘 */ int fact(int n) { int result; int i; result 1; i 1; while (i n) { result result * i; i i 1; } return result; }这段程序虽然短但词法上要处理关键字、标识符、数字、运算符、注释和空白语法上要用非终结符区分加减和乘除的优先级语义上要检查 n、result、i 都声明过、类型是 int中间代码生成则要把 while 循环拆成 label、条件跳转和无条件跳转。语言小但每个实验的难度都没缩水。2.2 三个实验的分工与产出物这套实验集合里的三个实验本质上是同一份语言规范的三次递进加工每一级的输入是上一级的输出。词法分析产出的 token 流是语法分析的原料语法分析产出的 AST 又是语义分析和中间代码生成的原料任何一个环节的产出格式变了下游都要跟着返工。可以先用一张表把分工列清楚实验输入输出核心数据结构难度点实验一 词法分析Cminusf 源文件token 序列DFA 状态表、Token 结构体最长匹配与回退、注释跳过实验二 语法分析token 序列语法分析树AST 节点、递归下降子程序左递归消除、优先级层级实验三 语义分析与中间代码生成语法分析树三地址码符号表、类型检查器、临时变量编号器作用域、回填、类型检查词法分析负责把字符流变成有含义的记号流语法分析负责把记号流整理成树语义分析和中间代码生成负责在树上标注信息并把它拍平成接近汇编的三地址码。你在实验一里偷的懒会在实验二以「token 类型对不上」的形式连本带利还回来你在实验二里没建好的 AST 节点信息实验三里符号表想查也没得查。2.3 三个实验的接口约定为什么说它们不是三个独立项目很多第一次做编译课设的人会把三个实验当成三个独立程序来写实验一输出一个 token 文件实验二自己再解析一遍这个文件。这样做不是不行但一旦 token 枚举定义、AST 节点字段在三个实验里各写一份调试效率会非常低。这套实验集合的组织方式是典型的工程做法把公共头文件抽出来三个实验共享同一份接口定义。实验集合/ ├── common/ │ ├── token.h /* token 类型枚举与 Token 结构体 */ │ ├── ast.h /* AST 节点类型与构造函数 */ │ └── symtab.h /* 符号表接口 */ ├── lab1_lexer/ │ ├── lexer.c │ └── lexer_test.c ├── lab2_parser/ │ ├── parser.c │ └── ast_dump.c ├── lab3_codegen/ │ ├── codegen.c │ └── symtab.c └── tests/ ├── fact.cm ├── gcd.cm └── ...token.h 里放的是词法分析器和语法分析器都要引用的 TokenType 枚举ast.h 里放的是语法分析和代码生成都要操作的 AST 节点symtab.h 是实验三符号表的对外接口。这样实验一单独可以编译出 lexer把实验一接进实验二时只需要 include 同一份 token.h从根上避免了「两边枚举值对不上」的接口问题。我第一次做编译课设时是三个实验各写各的结果实验二的 token 枚举和实验一的值对不齐定位了一天一夜那种翻车经历至今记得。3. 实验一实现手写词法分析器的状态表与驱动循环3.1 记号表设计先定 token 类型再写状态机词法分析的第一步不是写代码是把语言规范里所有能出现的「词」列成一张记号表。这份资源里的 Cminusf 记号表大致如下类别token 类型匹配内容示例关键字TOKEN_KEYWORDint void if while returnwhile标识符TOKEN_ID字母开头后续字母或数字fact数字常量TOKEN_NUM十进制整数42运算符TOKEN_OP - * / ! 界符TOKEN_SYM; , ( ) [ ] { };文件结束TOKEN_EOF物理 EOF-词法错误TOKEN_ERROR非法字符这张表直接对应实验输出里的 token 流每个 token 记录它的类型、原始字符串和所在行号。行号是调试的重灾区语法分析器报错时要准确告诉你第几行出了问题所以词法阶段就必须把 line 存进 Token 结构体不要等到实验二再重新数行。对应的 Token 结构体是这个样子的/* token.h词法分析输出与语法分析输入共用 */ typedef enum { TOKEN_KEYWORD, TOKEN_ID, TOKEN_NUM, TOKEN_OP, TOKEN_SYM, TOKEN_EOF, TOKEN_ERROR } TokenType; typedef struct { TokenType type; /* token 类别用于语法分析器的 switch 分支 */ char* lexeme; /* 原始字符串strdup 分配的堆内存 */ int line; /* 行号从 1 开始报错信息靠它 */ int value; /* 仅 TOKEN_NUM 有效存整数值 */ } Token;lexeme 用 strdup 是常见做法好处是 token 流和源文件缓冲区解耦坏处是每解析完一个 token 都要 free否则长时间跑会漏内存。如果用的是 MSVC 环境strdup 要换成 _strdup或者自己写一个 mallocstrcpy 的辅助函数这是词法代码移植时最常见的编译报错。value 字段只对数字常量有意义语法分析器在生成 AST 的数字节点时直接拿 value不用再走一遍 atoi。3.2 状态机驱动核心字符预读、匹配与回退这套实验的词法分析器没有依赖 Flex是手写的状态机驱动核心逻辑是一个不断读字符、按状态转移、在合适的时机提交 token 的循环。下面这段代码是标准的手写词法骨架我在实验包里看的就是这个套路/* lexer.c状态机驱动一次调用返回一个 token */ static int next_token(FILE* fp, Token* tok) { int c, state 0; char buf[TOKEN_BUF_SIZE]; int len 0; while (1) { c fgetc(fp); if (c \n) line; switch (state) { case 0: /* 初始状态跳过空白识别首字符类别 */ if (c || c \t || c \n) break; if (c EOF) { tok-type TOKEN_EOF; return 0; } if (isalpha(c)) { buf[len] (char)c; state 1; } else if (isdigit(c)) { buf[len] (char)c; state 2; } else if (c /) { buf[len] (char)c; state 3; /* 可能是除号也可能是注释起点 */ } else { buf[0] (char)c; buf[1] \0; tok-type classify_op_sym(c); tok-lexeme strdup(buf); tok-line line; return 0; } break; case 1: /* 标识符/关键字字母开头后续字母或数字 */ if (isalnum(c)) { buf[len] (char)c; } else { ungetc(c, fp); /* 多读的一个字符退回输入流 */ buf[len] \0; tok-type is_kw(buf) ? TOKEN_KEYWORD : TOKEN_ID; tok-lexeme strdup(buf); tok-line line; return 0; } break; case 2: /* 数字只处理十进制整数 */ if (isdigit(c)) { buf[len] (char)c; } else { ungetc(c, fp); buf[len] \0; tok-type TOKEN_NUM; tok-value atoi(buf); tok-lexeme strdup(buf); tok-line line; return 0; } break; case 3: /* 读到一个 /需要区分除法和注释 */ if (c *) { state 4; } else if (c EOF) { tok-type TOKEN_OP; tok-lexeme strdup(/); tok-line line; return 0; } else { ungetc(c, fp); tok-type TOKEN_OP; tok-lexeme strdup(/); tok-line line; return 0; } break; case 4: /* 块注释内部等待 * */ if (c *) { state 5; } else if (c EOF) { tok-type TOKEN_ERROR; return -1; } break; case 5: /* 已遇到 *若下一个是 / 则注释结束 */ if (c /) { state 0; } else if (c *) { state 5; /* 连续星号仍保持等待 */ } else if (c EOF) { tok-type TOKEN_ERROR; return -1; } else { state 4; } break; } } }这个循环的要点有三个。第一每次只有一个字符被 fgetc 读进来但标识符、数字这种变长词在读到不属于它的字符时要把这个字符通过 ungetc 退回输入流否则下一个 token 就会丢字符。第二/*的判断放在「下一字符 *」所以单独的除号a / b不会误判成注释而a b /*p;这种写法在 Cminusf 里本身就不合法因为语言规范里没有指针。第三行号计数在循环里统一维护注释跨行时行号照常递增等到实验二、实验三里报错就不会出现「行号全对不上」的玄学问题。3.3 测试把 token 流打印出来手动核对一遍词法分析的调试手段很朴素写一个测试驱动把源文件里每个 token 的类型、词汇、行号逐行打出来然后拿这份输出和手推的结果对照。实验包里 lexer_test.c 做的事情就是这样# 编译并运行词法测试 gcc -o lexer lexer.c lexer_test.c -I ../common ./lexer tests/fact.cm期望输出片段Line 1: KEYWORD int Line 1: ID fact Line 1: SYM ( Line 1: KEYWORD int Line 1: ID n Line 1: SYM ) Line 2: SYM { ... Line 4: ID result Line 4: OP Line 4: NUM 1 Line 4: SYM ;如果打印结果和手推的不一致别急着去改语法分析器先回去看状态机和记号表。特别是、这种双字符运算符这段骨架代码里还没有处理双字符运算符的完整逻辑实际实验包里会在 state 0 对、做预读判断再决定提交单字符还是双字符 token。这是词法分析最典型的边界最长匹配要求你必须多看一个字符再决定回退多少。4. 实验二实践递归下降分析器与语法树构建4.1 选型理由手写递归下降而不是 YACC语法分析器的实现路线通常有三条手写递归下降、FlexBison 生成器、Python PLY。这套实验包选的是第一条路线。原因不难理解递归下降的每个产生式对应一个 C 函数代码结构和语法规则一一对应出错了能直接在函数调用栈里看到是「哪个非终结符在等哪个 token」对课程实验来说调试成本最低。Bison 生成的 LR 分析器效率高但冲突报文、action 嵌入点对新手很不友好而且生成代码的可读性差答辩时也很难讲清楚。对比项手写递归下降Bison/YACCPLY环境依赖无纯 C需要 bison/flex 工具链需要 Python 环境代码结构产生式对应函数生成表驱动分析器类似 YACC 的声明式优先级实现函数层级控制直观需要 %left/%right 声明需要 token 优先级声明错误恢复自己写但可控默认机制不直观需要额外代码课程契合度多数课程要求手写偏生产工具依赖解释器如果你的课程明确禁止使用生成器递归下降是唯一稳妥路线如果课程允许 FlexBison我仍建议先用递归下降把语法跑通再考虑用生成器对照结果。实验二的核心产出是语法树不是分析器本身所以生成器和手写在最终得分上差异不大但手写代码能在答辩时被问到任何一层。4.2 核心代码表达式优先级靠函数层级实现Cminusf 的表达式优先级从低到高是赋值 比较 加减 乘除 因子。递归下降处理优先级的标准做法是让每个优先级级别对应一个函数高层函数调用低层函数底层函数处理括号、数字和标识符。下面是这份实验里乘除和因子的核心代码/* parser.c乘除级别对应 factor 之上的一个优先级层次 */ ASTNode* parse_mul(Parser* p) { ASTNode* left parse_factor(p); while (p-tok.type TOKEN_OP (p-tok.lexeme[0] * || p-tok.lexeme[0] /)) { char op p-tok.lexeme[0]; next(p); /* 消费运算符 */ ASTNode* right parse_factor(p); left make_binop(op, left, right); /* 左结合新节点成为左子树 */ } return left; } ASTNode* parse_factor(Parser* p) { if (p-tok.type TOKEN_NUM) { ASTNode* n make_num(p-tok.value); next(p); return n; } if (p-tok.type TOKEN_ID) { ASTNode* n make_var(p-tok.lexeme); next(p); return n; } if (p-tok.type TOKEN_SYM p-tok.lexeme[0] () { next(p); ASTNode* inner parse_expr(p); /* 括号内完整表达式 */ expect_sym(p, )); return inner; } error(parse_factor: unexpected token %s, p-tok.lexeme); return NULL; }整个链路的调用顺序是 parse_assign - parse_expr - parse_additive - parse_mul - parse_factor每一层只处理自己这一级优先级的运算符其余交给下一层。比如2 3 * 4parse_additive 先拿到 2发现下一个 token 是于是右子树去调用 parse_mulparse_mul 内部先处理了 3 * 4整体结果就变成 2 (3 * 4)。这种函数层级就是语法的骨架改优先级比在 Bison 里调声明更直白也更容易在答辩时讲清楚。代码里的两个小细节值得注意。make_binop 返回的节点在 while 循环里会被反复作为 left 传给下一次迭代这是左结合运算a - b - c能正确变成(a - b) - c的关键。parse_factor 里遇到(时递归调用 parse_expr 而不是 parse_factor 再传参是为了让括号内的内容可以包含整个低优先级表达式而不是只允许括号里有一个因子。4.3 语法树可视化把 AST 打印成缩进文本语法分析器写完第一件事不是接着写语义分析而是把 AST 打出来核对。实验包里专门有一个 ast_dump.c作用就是用缩进直观地呈现树的形状/* ast_dump.c递归打印语法树缩进表示树深度 */ void dump_ast(ASTNode* n, int depth) { for (int i 0; i depth; i) printf( ); switch (n-kind) { case NODE_NUM: printf(NUM(%d)\n, n-val); break; case NODE_VAR: printf(VAR(%s)\n, n-name); break; case NODE_BIN: printf(BIN(%c)\n, n-op); dump_ast(n-left, depth 1); dump_ast(n-right, depth 1); break; default: printf(UNKNOWN\n); break; } }对a 2 3 * 4;这样一条赋值语句打印出来的树形应该是BIN() VAR(a) BIN() NUM(2) BIN(*) NUM(3) NUM(4)如果看到 BIN() 的右子树不是 BIN(*) 而是 NUM(4)十有八九是 parse_additive 里右子树调成了 parse_additive 而不是 parse_mul递归下降和优先级层级是对应关系这一步错后面全错。AST 形状确认无误后再进入语义分析和中间代码生成可以省掉大量来回排查的时间。5. 避坑指南三个实验里最容易翻车的五个检查点下面的每一条都来自真实调试现场。编译原理课设的坑通常是隐性的——代码能编译通过跑出来的结果却是错的于是只能在 token 流、AST、中间代码三层之间反复横跳。这套实验集合的调试记录里最值得反复读的就是这些边界情况很多坑在正常用例上根本不会触发。5.1 双字符运算符被切成两个单字符现象a 1; if (a 2) return 0;的 token 流里出现OP()、OP()两个相邻运算符语法分析器在表达式解析时报错。原因词法分析器在状态 0 读到时直接把它当作单字符运算符合法提交了没有预读下一个字符是否。语法分析器期望一个比较运算符实际拿到的是两个独立的运算符 token自然无法匹配产生式。解决在初始状态处理、、、!时先预读一个字符若下一个字符是则提交双字符运算符否则把预读字符退回。关键点是用完预读字符要 ungetc否则下一个 token 会少一个字符。5.2 块注释没到结束就 EOF分析器不报错现象源文件最后忘写了*/但实验一测试程序没有报错实验二却读到一串莫名其妙的标识符。原因状态机在注释状态里遇到 EOF 时有的实现直接返回 0 当作文件结束把注释内容泄漏给了语法分析器。语法分析器把注释里的字符当成代码来解析自然报出一堆位置诡异、内容诡异的错。解决状态 4 和状态 5 里遇 EOF 应该返回 TOKEN_ERROR 并打印「未闭合的注释」。测试程序要专门构造一个缺*/的用例验证错误路径。词法分析不只是认对合法的词也要对非法的输入给出明确报错这是评分标准里常见的一条。5.3 表达式写成左递归运行直接栈溢出现象解析a - b - c时程序段错误gdb 显示 parse_additive 无限调用自己。原因产生式写成了expr - expr term对应到函数里 parse_additive 第一行就调用 parse_additive形成无终止递归。每递归一层就压一次栈输入稍微长一点直接把栈耗尽。解决把左递归改写为循环。标准写法是 parse_additive 先调用 parse_mul 拿左操作数再在 while 循环里反复读取同一优先级的运算符每读一个运算符就生成一个新节点挂到左子树。教科书里说的「消除左递归」在递归下降里就是用 while 替代递归。5.4 符号表作用域退出函数后全局变量找不到了现象main 里定义了一个局部变量 i调用函数后回到 main再访问 i 报「未声明」。原因符号表是语义分析阶段的核心数据结构。Cminusf 的语义分析要做两件事声明检查和类型检查而这两个检查都依赖作用域正确的符号表。如果符号表在实现时只有一张哈希表插入局部变量时直接覆盖了全局同名变量作用域信息就没有分层。解决符号表改成作用域栈。进入复合语句或函数时 push 一个新层声明变量时只插入栈顶层查找时从栈顶向下遍历退出作用域时整层弹出。接口上一般提供 push_scope()、pop_scope()、insert_sym()、lookup_sym() 四个函数语义分析器只需在语法树的块节点进出时调用前两个插入和查找逻辑不需要感知作用域深度。5.5 三地址码的临时变量编号冲突现象两个表达式独立生成时都用 t1合并到同一段代码后互相覆盖运行结果错乱。原因代码生成器在递归处理每个表达式时把临时变量计数器局部化了每次从 t1 重新开始。两个并列的赋值语句各自生成一组 t1、t2但它们最终落在同一段中间代码里。解决在代码生成器里维护一个全局唯一的 temp_index通过 newtemp() 函数返回 t%d 并自增。另一个常见做法是按函数重置编号因为 Cminusf 的函数体是独立的作用域层次只要保证同一函数内不重号即可。按函数重置编号更贴近真实编译器读起来也简洁。6. 答辩前的最后一道工序用回归脚本验证三地址码6.1 手工对照一组三地址码先证明代码生成器方向对中间代码生成器的调试比前两个实验更微妙因为三地址码不像 token 流和 AST 可以直观检查容易出现「代码跑完了、结果也对、但中间代码长得别扭」的情况。先用一组最简单的样例手工推导是成本最低的验证方式。下面这段 Cminusf 程序int main(void) { int a; int b; a 2 3 * 4; b a * 2; return b; }期望生成的三地址码是t1 3 * 4 t2 2 t1 a t2 t3 a * 2 b t3 return b手工推导的关键依据是优先级和遍历顺序乘法先于加法所以 t1 先算 3 * 4赋值语句先生成右操作数再写左变量return 直接引用 b 的值。如果跑出来 t1 是 2 3说明 parse_additive 和 parse_mul 的调用层级接反了这个错误在 AST dump 阶段就该查出来如果 t2 之外还有多余的临时变量说明代码生成器给赋值运算多包了一层不影响正确性但会让后续实验的中间代码体积膨胀。6.2 把测试用例串成自动回归防止改一处坏一处中间代码生成器改到后期最怕的是加了一个功能点回头把之前生成正确的算术表达式又搞坏了。解决办法是在 tests/ 下为每个用例配一个基准输出文件用脚本批量跑 diff#!/bin/bash set -u for src in tests/*.cm; do base$(basename $src .cm) ./cmc -ir $src out/$base.ir if diff -q out/$base.ir expect/$base.ir /dev/null 21; then echo PASS $base else echo FAIL $base fi done脚本里的 -ir 参数表示只生成中间代码不继续做后续的汇编或解释执行out/ 放本次运行输出expect/ 放自己手工核对过的基准文件。因为递归下降生成的三地址码按固定的 AST 遍历顺序输出临时变量编号在同一函数内也是稳定的所以可以直接逐字符 diff。如果课程改动导致编号规律变化就在 codegen 里加一个 -normalize 参数把输出中的 tN 全部替换成 t再做语义比较这样能过滤掉编号对 diff 的干扰。我在实验三后期就是靠这个脚本活下来的。当时给 while 循环的代码生成加回填逻辑改完一个用例回头一跑发现之前能通过的算术表达式全部 FAIL一查是回填时把跳转目标地址递增逻辑改了影响到了所有控制流代码如果没有基准比对这个改动带来的隐患可能要拖到答辩当天才暴露。从那以后我每次改完代码生成器都强制跑一遍回归把中间代码和上一版逐行 diff 一次再继续动下一处。希望帮到你。本文还有配套的精品资源点击获取