简介编译原理课程设计全套资料覆盖词法分析、LL(1)与LR(0)/SLR(1)语法分析、四元式生成及汇编代码生成等核心实验适合计算机专业本科生完成课程设计或系统复习编译原理时参考。压缩包共14个文件以c/cpp源程序、h头文件、txt文法和doc实验报告为主总大小557KB结构紧凑。已有2349人学习下载说明该资源对做编译原理实验和报告的同学有较强参考价值。内容包含可用词法分析器、针对ii*i等简单语句的LL(1)分析实现、SLR(1)文法和对应分析程序以及一份小型编译器课程设计报告既可对照代码理解自顶向下、自底向上语法分析流程也可参考报告格式完善自己的实验文档适合用C语言完成编译原理综合设计的读者。1. 编译原理课程设计从词法分析到小型编译器的完整闭环A同学在课设答辩前一周跑测试用例发现while (i 10) { i i 1; }这段代码在小型编译器上直接死循环i永远不涨。查了一晚上问题出在词法分析器把i识别成了关键字if。这个翻车场景很典型——很多人的编译原理课设是把词法分析、语法分析分开交的单个模块跑起来没问题合在一起做小型编译器就崩。这套方案要解决的不是某个单独算法的演示而是把词法分析、语法分析、符号表和中间代码生成串成一条完整链路最后跑出一个能解释执行或生成代码的小型编译器。适合正在做编译原理课程设计的本科生也适合要交实验报告但不想只交“纸上算法”的人。核心思路是用直接编码的DFA做词法分析用递归下降做语法分析配合符号表把两者的接口打通而不是各写各的然后拼不起来。2. 总体架构设计前端四模块与符号表的核心作用2.1 模块划分词法分析、语法分析、符号表、中间代码生成一套完整的小型编译器课设通常按编译前端划分成四个模块再加一个驱动程序。模块划分不是越细越好而是要让每个模块有独立的输入输出方便单独测试和写实验报告。词法分析器Tokenizer负责把源代码字符串流切分成 token 序列输出形如(关键字, if)、(标识符, i)、(运算符, )的结构化数据。语法分析器Parser负责把 token 序列按文法规则组织成抽象语法树AST同时做语法错误检查。符号表SymbolTable在词法分析和语法分析阶段都会用到——词法阶段区分关键字和标识符靠查表语法阶段声明变量、检查作用域也要查表。中间代码生成器IRGenerator遍历 AST生成三地址码或类栈指令供解释器执行或汇编输出。驱动程序按顺序调用上述模块读入源文件 → 词法分析 → 语法分析 → 中间代码生成 → 执行。每个阶段产出的中间结果都写入独立文件方便排查。这样设计的直接好处是课设答辩时你可以分阶段演示哪个模块出了问题对着中间结果文件一眼就能定位。2.2 token 设计与数据结构定义token 是词法分析和语法分析之间的唯一通信协议它的设计直接决定 Parser 写起来舒服还是别扭。我一般会定义如下结构typedef enum { TOKEN_KEYWORD, // 关键字 if else while int return TOKEN_IDENTIFIER, // 变量名、函数名 TOKEN_NUMBER, // 整数常量 TOKEN_OPERATOR, // - * / ! TOKEN_DELIMITER, // ( ) { } ; , TOKEN_EOF // 文件结束标记 } TokenType; typedef struct { TokenType type; char lexeme[128]; // 原始字符串如 while、i、123 int line; // 所在行号错误报告用 int column; // 所在列号 int value; // 数字字面量的整数值方便后续计算 } Token;这里有两个关键设计决策。第一line 和 column 必须记录不然语法分析报错时只能报“第几行有错”却指不出具体位置答辩时分析问题会很被动。第二lexeme保留原始字符串而value单独存整数值——比如123这个 tokenlexeme是123value是整数 123后续生成中间代码时直接取值不需要重复转换。符号表的结构可以这样设计typedef struct Symbol { char name[128]; // 变量名 int type; // INT 或 VOID int scope; // 作用域层级0 为全局 int initialized; // 是否已初始化 struct Symbol *next; // 哈希冲突链 } Symbol;符号表用简单哈希表实现以变量名为 key。作用域用层级编号区分全局变量 scope0进入一个{}块后 scope1退出时删除所有该层级的符号。这里有个容易忽略的点词法分析器判断一个if是关键字还是标识符靠的是先查关键字表再查符号表——如果标识符恰好叫if词法阶段就要报错而不是到语法阶段才报。这个顺序在答辩时经常被追问提前在报告里写清楚。2.3 接口约定Token 流如何传递给 Parser两个模块之间的接口通常定义为一个函数Token nextToken()。Parser 每调用一次词法分析器就从输入缓冲区读入若干字符切出一个 token 返回。但实际工程里Parser 经常需要“向前看”一个 token 才决定如何归约所以词法分析器要提供一个peekToken()或pushback()能力。Token current_token; // 当前正在处理的 token Token lookahead; // 向前预读的一个 token Token getNextToken() { // 如果 lookahead 已经被填充先返回它并清空 // 否则调用词法分析器生成新 token }这个缓存机制是词法分析和语法分析联调时最常见的坑——如果 Parser 预读了一个 token 但没正确回推语法分析就会漏掉一个 token导致后续所有规则错位。我的做法是词法分析器内部维护一个最多 2 个 token 的缓冲队列Parser 只能通过getNextToken()和peekToken()访问禁止直接调用底层的字符读取函数。接口定死了模块之间的边界就清晰了。3. 词法分析实现直接编码DFA与关键字的识别策略3.1 为什么不用Lex/Flex自动生成很多教材讲词法分析必提 Flex自动生成工具能基于正则表达式构造 NFA、DFA再最小化。但课设场景下我建议手写直接编码的 DFA理由有两个。第一Flex 生成的代码是黑匣子你没法在实验报告里展示分析过程答辩时导师问“DFA 状态怎么迁移的”你只能答“Flex 生成的我也不知道”。第二小型编译器的词法规则不超过 20 种 token手写状态机也就两三百行代码可控性强出问题能单步调试。直接编码 DFA 的思路是把词法规则手工整理成状态转移表循环读字符、查表、转移状态。以if、else、while关键字和有字母开头的标识符为例它们共享同一个状态组的起点——首字符是字母所以 DFA 不能在一开始就区分关键字和标识符只能先把完整的字母串读进缓冲区然后查关键字表。3.2 完整词法分析器关键代码下面这个实现只处理核心的 token 类型但它展示了直接编码 DFA 的完整骨架主循环、分派状态、关键字表查询、数字和运算符处理。#include stdio.h #include ctype.h #include string.h #define MAX_LEXEME_LEN 128 // 关键字表课设要求覆盖的核心关键字 static const char *keywords[] {if, else, while, int, return}; // 判断是否为关键字是返回 token 类型中的 KEYWORD否则是 IDENTIFIER TokenType classifyKeyword(const char *word) { for (int i 0; i sizeof(keywords) / sizeof(keywords[0]); i) { if (strcmp(word, keywords[i]) 0) { return TOKEN_KEYWORD; } } return TOKEN_IDENTIFIER; } // 核心分词函数从 source 的 pos 位置开始读取返回一个 token // 这是直接编码 DFA 的主循环所有状态迁移显式写在代码里 Token nextToken(const char *source, int *pos, int *line, int *col) { Token token; char lexeme[MAX_LEXEME_LEN]; int len 0; // 跳过空白字符空格、制表、换行。换行要维护行号 while (source[*pos] || source[*pos] \t) { (*pos); (*col); } if (source[*pos] \n) { (*line); (*col) 1; (*pos); } char c source[*pos]; token.line *line; token.column *col; // 状态1字母开头 → 读完整字母/数字串 → 查关键字表 if (isalpha(c)) { while (isalnum(source[*pos])) { lexeme[len] source[*pos]; (*pos); (*col); } lexeme[len] \0; strcpy(token.lexeme, lexeme); token.type classifyKeyword(lexeme); return token; } // 状态2数字开头 → 读完整数字串同时存整数值 if (isdigit(c)) { int val 0; while (isdigit(source[*pos])) { val val * 10 (source[*pos] - 0); lexeme[len] source[*pos]; (*pos); (*col); } lexeme[len] \0; strcpy(token.lexeme, lexeme); token.type TOKEN_NUMBER; token.value val; return token; } // 状态3运算符。注意 和 的区别 // 先读当前字符若下一个也是 则连读构成 if (c || c ! || c || c ) { char first c; (*pos); (*col); if (source[*pos] ) { (*pos); (*col); token.type TOKEN_OPERATOR; sprintf(token.lexeme, %c%c, first, ); return token; } token.type TOKEN_OPERATOR; token.lexeme[0] first; token.lexeme[1] \0; return token; } // 状态4分隔符 if (c ( || c ) || c { || c } || c ; || c ,) { (*pos); (*col); token.type TOKEN_DELIMITER; token.lexeme[0] c; token.lexeme[1] \0; return token; } // 状态5无法识别 → 报错同时跳过该字符避免死循环 if (c \0) { token.type TOKEN_EOF; strcpy(token.lexeme, EOF); return token; } // 非法字符返回一个特殊的错误 token由调用方决定是否终止编译 (*pos); token.type TOKEN_EOF; // 这里简化为 EOF实际上应定义 TOKEN_ERROR sprintf(token.lexeme, unexpected char %c at line %d col %d, c, *line, *col); printf(%s\n, token.lexeme); return token; }3.3 参数设计与常见误用这段代码里有三个关键参数要重点说明也是课设报告里值得写的技术点。第一个是line和col的维护方式。很多同学用strtok切 tokentoken 切出来了行号丢了。错误报告里只能写“语法错误”写不出“第 3 行第 5 列”。别小看这个实验报告评审时带行列号的错误报告是加分的答辩演示时故意输错一个符号看编译器报错信息比口头解释十句都有说服力。第二个是关键字表的分类策略。我前面给的是先读完整字母串再查表这是推荐做法。反面做法是每读一个字符就判断是否匹配某个关键字——比如读到i就等等看看是不是if——这会让状态机多出大量状态维护成本飙升。先收集完整字符串再统一查表状态机只有一条“标识符”路径简单得多。第三个是数字字面量的value字段。如果不在词法阶段计算整数值语法分析阶段构造 AST 节点时123这个串就要重新解析一遍而且如果你在 AST 里存的是字符串后端生成三地址码时还要再转一次整数。词法阶段转好后面所有阶段直接用token.value省掉重复转换也避免“不同阶段转换结果不一致”的玄学 bug。词法分析最容易翻车的点是和的区分以及、这类双字符运算符。上面的代码用一个“预读回退”的写法处理先读第一个字符再看下一个是不是是就连读不是就回退到只读第一个字符的状态。这里注意pos已经向前移动了回退时要(*pos)--同时(*col)--否则列号会错。列号一错Parser 用行号做错误定位的“后悔药”就没了。4. 语法分析实现递归下降法与错误恢复机制4.1 文法设计与优先级处理小型编译器最常见的文法包括表达式、赋值语句、条件语句、循环语句和复合语句块。为了控制复杂度通常用优先级爬升法处理算术表达式的优先级而不是单独为每个优先级写一个函数。但课设如果时间紧直接按优先级分层写函数也够用。文法骨架如下program → statement_list statement_list → statement statement_list | ε statement → if_stmt | while_stmt | assign_stmt | block_stmt block_stmt → { statement_list } assign_stmt → identifier expression ; if_stmt → if ( expression ) statement [else statement] while_stmt → while ( expression ) statement expression → additive_expr [( | | | !) additive_expr] additive_expr → term {( | -) term} term → factor {(* | /) factor} factor → ( expression ) | number | identifier这里要特别留意if_stmt的else悬空问题。C 语言的规则是else匹配最近的未匹配if递归下降解析时if_stmt函数在解析完“then 子句”之后不要立即返回而是先 lookahead 看下一个 token 是不是else是则继续解析 else 分支。这个顺序不能反过来否则嵌套 if 的结构会解析错。4.2 Parser 核心实现表达式优先级与循环语句处理以下代码展示了递归下降法中两个最关键的部分表达式解析带优先级和 while 循环解析。#include stdio.h #include stdlib.h #include string.h // AST 节点类型 typedef enum { NODE_NUMBER, // 数字字面量 NODE_VAR, // 变量引用 NODE_ASSIGN, // 赋值表达式left 为变量right 为表达式 NODE_BINOP, // 二元运算opr 存运算符字符 NODE_IF, // if 语句 NODE_WHILE, // while 语句 NODE_BLOCK // 语句块 } NodeType; typedef struct ASTNode { NodeType type; int value; // 仅 NODE_NUMBER 使用 char name[128]; // 仅 NODE_VAR 使用 char opr; // 仅 NODE_BINOP 使用存 - * / 等 struct ASTNode *left; // 通用左子节点 / then 分支 struct ASTNode *right; // 通用右子节点 / else 分支可为 NULL struct ASTNode *next; // 仅语句列表使用下一条语句 } ASTNode; // 全局 token 流 extern Token current_token; extern Token lookahead; void advance(); // 读取下一个 token void match(TokenType type); // 匹配指定类型不匹配则报语法错误 // 前向声明因为 term 和 factor 相互调用 ASTNode* parseExpression(); ASTNode* parseTerm(); ASTNode* parseFactor(); // 解析 while 语句while ( expression ) statement // 返回值是 WHILE 节点left 是条件表达式right 是循环体语句 ASTNode* parseWhile() { match(TOKEN_KEYWORD); // 当前 token 必须是 while但这里需要验证 lexeme if (strcmp(current_token.lexeme, while) ! 0) { // 错误恢复报错并跳过本语句回到同步点 printf(line %d: expected while\n, current_token.line); synchronize(); // 跳过分号或右花括号之前的 token return NULL; } advance(); match(TOKEN_DELIMITER); // ( ASTNode *cond parseExpression(); match(TOKEN_DELIMITER); // ) ASTNode *body parseStatement(); // 解析循环体如果是复合语句则是 BLOCK 节点 ASTNode *node (ASTNode*)malloc(sizeof(ASTNode)); node-type NODE_WHILE; node-left cond; node-right body; node-next NULL; return node; } // 表达式解析先解析加法表达式再看有没有比较运算符 // 注意比较运算在 C 语言中优先级低于算术所以要放在最外层 ASTNode* parseExpression() { ASTNode *left parseTerm(); // 先解析项乘法优先级 while (current_token.type TOKEN_OPERATOR (current_token.lexeme[0] || current_token.lexeme[0] || current_token.lexeme[0] )) { // 这里要判断是 而不是 但词法分析已经把 单独归类 // 所以需要检查 lexeme 的长度是否为 2 char op current_token.lexeme[0]; current_token.lexeme[0] current_token.lexeme[1] ? (op ) : (void)0; // 统一存为 类型上标记为比较 advance(); ASTNode *right parseTerm(); ASTNode *bin (ASTNode*)malloc(sizeof(ASTNode)); bin-type NODE_BINOP; bin-opr op; bin-left left; bin-right right; left bin; } return left; }4.3 错误恢复怎么从语法错误中活过来递归下降解析器遇到第一个语法错误就终止编译这是个坏设计。因为你没法在答辩现场写对的代码——演示时故意展示编译错误处理能力比展示正确的编译过程更能体现工程意识。错误恢复的典型做法是 panic mode 同步发现错误后抛弃 token 直到找到一组同步标记再从同步点重新开始解析。实现层面要注意三点。第一同步点的选择要有意义分号;是语句结束标志右花括号}是块结束标志这两个是最常用的同步标记。第二同步前要输出清晰的错误信息包括行号、期望的 token、实际得到的 token让人一看就知道哪里错了。第三同步失败时要强制前进一个 token避免两个错误连续出现导致死循环——很多同学写的错误恢复“活不过来”就是因为遇到错误后 token 不前进永远停在同一个报错位置。// 同步恢复跳过分号或右花括号之前的 token回到可继续解析的位置 void synchronize() { while (current_token.type ! TOKEN_EOF) { if (current_token.type TOKEN_DELIMITER) { if (current_token.lexeme[0] ; || current_token.lexeme[0] }) { // 分号是语句结束花括号是块结束这两个位置适合恢复解析 advance(); // 消费掉这个同步标记 return; } } advance(); // 跳过当前 token继续找同步点 } }match函数是错误恢复的关键入口。我一般会在match里做两层策略如果期望 token 不匹配先报错然后看当前 token 是不是同步标记是则返回让上层着处理不是则调用synchronize跳完错误区域。这样既保留了错误信息又不会让错误连锁爆发。4.4 常见误用把多个优先级写在同一层最常翻车的写法是“一个函数处理所有运算符”读到一个或*就不分优先级统一建一个BINOP节点。结果是1 2 * 3被解析成(1 2) * 3运算顺序错误。优先级必须通过函数嵌套实现parseExpression调用parseTermparseTerm调用parseFactor每个层级只处理自己那一级优先级的运算符。如果只写一个解析函数无论怎么加判断条件都不可能同时满足左结合和优先级。这是递归下降法的“地基”不要为了少写代码而挖掉它。5. 联调与排查小型编译器最容易翻车的五个问题5.1 token回推失效预读的token丢了现象Parser 明明调用了peekToken()预读了一个 token但后面解析时发现 token 流少了一个所有规则错位。原因词法分析器内部没有做 token 缓冲。peekToken()从输入流直接读入下一个 token 并返回但没保存等真正的getNextToken()调用时又去读了一次预读的 token 就丢掉了。本质是“预读只读不存”。解决在词法分析器内部维护一个容量为 2 的 token 缓冲数组。peekToken()先检查缓冲中是否有可用 token有则直接返回没有才调用底层分词函数填入缓冲。getNextToken()同样先看缓冲有则弹出没有则新读。这样无论 Parser 怎么交叠调用token 流都不会乱。5.2 关键字与标识符混淆用户变量名撞了关键字现象源代码里定义int if 3;编译器没有报“关键字不能作变量名”而是接受了或者报告了一个莫名其妙的错误。原因词法分析器把if识别成TOKEN_KEYWORD但符号表没有校验“声明时变量名不能是关键字”。词法阶段已经知道if是关键字了但符号表插入时没检查。解决词法分析器中classifyKeyword返回TOKEN_KEYWORD后Parser 在解析变量声明时增加检查如果当前 token 的type TOKEN_KEYWORD直接报错“期望标识符但得到关键字 if”。更彻底的做法是在词法分析器里增加一个开关如果当前上下文是“声明位置”遇到关键字直接报错。但简单起见我通常建议在 Parser 的声明解析函数里拦截一行代码的事。5.3 错误恢复死循环报错后程序不推进现象源代码有一行int x ;Parser 报错后程序卡死或者一直在报同一行错误。原因synchronize()内部没有强制前进 token 的兜底逻辑。如果当前 token 既不是分号也不是花括号并且advance()没有正确移动位置比如遇到了 EOF 边界处理不当就会无限循环打印同一行错误。解决advance()函数必须保证至少前进一个 token并在到达 EOF 时返回TOKEN_EOF。synchronize()里加一个计数守卫连续跳转超过 100 个 token 仍找不到同步标记就直接丢弃整条语句并返回。另一个稳妥做法是每次报错后无论是否找到同步标记都强制消费一个 token用“宁可漏一个 token也不卡死”的原则保证编译器终会收敛。5.4 注释处理遗漏/* */ 和 // 没跳过现象源代码里带注释时词法分析把/当成除法运算符注释正文全被当成代码解析报出一堆错误。原因词法分析器没处理注释。很多课设要求里写了“支持注释”但学生只在文档里写了代码里没实现。解决在nextToken()开头、识别运算符之前增加注释分支。遇到/时向后看一个字符如果是//跳过整行直到换行如果是/*跳过直到*/期间要维护行号和列号注释跨行时行号必须同步更新。这个判断必须在运算符处理之前因为/既是除法运算符又是注释的起始字符先处理注释再处理运算符。注意 column 更新/*和*/里的每一个字符都要计数否则注释后面的 token 列号全错。5.5 AST内存泄漏长程序跑着跑着内存暴涨现象解释执行一个几百行的测试程序内存占用持续上升最终卡死或 OOM。原因AST 节点用malloc分配解释执行完一个节点后没有free所有节点都留在堆上。递归下降解析本身创建海量节点不释放必然爆内存。解决解释器执行完一个 AST 节点后递归释放其子树。具体做法是给每个ASTNode加一个freeNode函数后序遍历释放先释放左子树、右子树和 next 链再释放自身。一个关键点赋值节点的变量名是strdup出来的要单独判断并释放。还有一个容易被忽略的地方——错误恢复时Parser 返回NULL节点上层要判断空指针不能对NULL执行freeNode。内存问题的排查可以用valgrind跑一个短程序看泄漏的调用栈在哪个函数多半是漏了一种节点类型没释放。6. 课设验收与答辩测试用例矩阵和演示脚本6.1 怎么自验收三层测试法自验收不要“写一个程序跑通就完事”而是要有层次地测。第一层是词法分析器单测准备一个包含所有 token 类型的测试文件运行后检查 token 序列是否与预期一致。第二层是语法分析器的合法/非法测试合法程序要能生成完整 AST 并打印结构非法程序要能在指定行列报错并恢复。第三层是端到端执行测试写一个包含循环、条件、变量声明的测试源文件编译执行后检查输出值是否正确。我推荐做一份测试用例表格记录每个用例的输入、预期输出、实际输出这份表格可以直接放进实验报告的“系统测试”章节。答辩时导师问“你怎么保证你的编译器是对的”打开表格指着一行用例说“这个用例测的是 while 循环嵌套 if-else预期输出 15实际输出 15”比空口说“测试过了”有力得多。// 一个自测用的三层测试用例示例 // 源文件 test_loop.txt { int i; int sum; i 0; sum 0; while (i 5) { if (i 3) { sum sum 100; } else { sum sum i; } i i 1; } return sum; } // 预期循环结算后 sum 0 1 2 100 4 1076.2 Linux下用脚本自测如果你在 Linux 或 macOS 环境下开发写一个简单的 shell 脚本批量跑用例能省掉人工盯屏的功夫。脚本做的事很简单对每个.cmm源文件运行编译器比对输出和.expected文件不一致则打印差异。#!/bin/bash # 批量回归测试脚本遍历测试目录下的 .cmm 文件 # 执行编译器后与 .expected 文件比对退出码和输出 for src in tests/*.cmm; do base$(basename $src .cmm) ./compiler $src /tmp/out.txt 21 if [ -f tests/$base.expected ]; then if diff -u tests/$base.expected /tmp/out.txt /dev/null; then echo PASS: $base else echo FAIL: $base diff tests/$base.expected /tmp/out.txt fi else echo NO EXPECTED FILE: $base (exit code $?) fi done这个脚本的价值不在脚本本身而在于它把验收做成了可重复的过程。人工测一遍可能漏掉边界用例脚本每次跑都一样不会因为手抖跳过某个文件。我的习惯是每改完一个模块就跑一次这个脚本确保改一处没破坏其他功能——这比最后关头一次性全部测试要稳得多。6.3 答辩演示顺序先跑通再跑错最后跑设计亮点答辩演示不能只展示“编译成功然后执行出结果”那是底线而不是亮点。一个我总结的有效顺序是三步走。第一步跑通一个综合用例展示词法分析输出、语法分析输出、AST 结构和执行结果证明整条链路是通的。第二步故意输入一个语法错误的源代码展示错误报告的行列号信息和恢复能力边演示边解释“我们的编译器在遇到错误后能从下一个分号处恢复解析不会崩溃”。第三步展示你方案里最特别的设计——比如符号表的作用域分层、中间代码的打印输出、带注释的源代码处理任意一个都行。重点不是展示功能多而是展示你对某一个设计点有深入理解。导师追问“为什么这么设计”你要能答出权衡为什么用手写 DFA 而不是 Flex为什么用递归下降而不是 LR(1)。有一个小技巧答辩前把你要演示的源文件和预期输出打印出来放在手边。万一现场编译器因为某个环境原因报错你可以直接指着手里的预期输出说“这里本来应该输出 107编译器在校验阶段报出了一个环境相关错误”然后换个用例继续演示。这不是教你造假而是现场调试定位问题时能快速恢复节奏——如果你卡在一个错误上报不出来整个答辩的后半段都会笼罩在“这个项目可能没做完”的怀疑里。从那以后我每次做课设或项目演示都会强制把所有用例和预期输出整理成一张表先手工过一遍再跑脚本过一遍最后才上现场。这套习惯帮我挡掉了好几次现场翻车的尴尬希望也能帮到你顺利通过编译原理课程设计的验收。本文还有配套的精品资源点击获取
简介编译原理课程设计全套资料覆盖词法分析、LL(1)与LR(0)/SLR(1)语法分析、四元式生成及汇编代码生成等核心实验适合计算机专业本科生完成课程设计或系统复习编译原理时参考。压缩包共14个文件以c/cpp源程序、h头文件、txt文法和doc实验报告为主总大小557KB结构紧凑。已有2349人学习下载说明该资源对做编译原理实验和报告的同学有较强参考价值。内容包含可用词法分析器、针对ii*i等简单语句的LL(1)分析实现、SLR(1)文法和对应分析程序以及一份小型编译器课程设计报告既可对照代码理解自顶向下、自底向上语法分析流程也可参考报告格式完善自己的实验文档适合用C语言完成编译原理综合设计的读者。1. 编译原理课程设计从词法分析到小型编译器的完整闭环A同学在课设答辩前一周跑测试用例发现while (i 10) { i i 1; }这段代码在小型编译器上直接死循环i永远不涨。查了一晚上问题出在词法分析器把i识别成了关键字if。这个翻车场景很典型——很多人的编译原理课设是把词法分析、语法分析分开交的单个模块跑起来没问题合在一起做小型编译器就崩。这套方案要解决的不是某个单独算法的演示而是把词法分析、语法分析、符号表和中间代码生成串成一条完整链路最后跑出一个能解释执行或生成代码的小型编译器。适合正在做编译原理课程设计的本科生也适合要交实验报告但不想只交“纸上算法”的人。核心思路是用直接编码的DFA做词法分析用递归下降做语法分析配合符号表把两者的接口打通而不是各写各的然后拼不起来。2. 总体架构设计前端四模块与符号表的核心作用2.1 模块划分词法分析、语法分析、符号表、中间代码生成一套完整的小型编译器课设通常按编译前端划分成四个模块再加一个驱动程序。模块划分不是越细越好而是要让每个模块有独立的输入输出方便单独测试和写实验报告。词法分析器Tokenizer负责把源代码字符串流切分成 token 序列输出形如(关键字, if)、(标识符, i)、(运算符, )的结构化数据。语法分析器Parser负责把 token 序列按文法规则组织成抽象语法树AST同时做语法错误检查。符号表SymbolTable在词法分析和语法分析阶段都会用到——词法阶段区分关键字和标识符靠查表语法阶段声明变量、检查作用域也要查表。中间代码生成器IRGenerator遍历 AST生成三地址码或类栈指令供解释器执行或汇编输出。驱动程序按顺序调用上述模块读入源文件 → 词法分析 → 语法分析 → 中间代码生成 → 执行。每个阶段产出的中间结果都写入独立文件方便排查。这样设计的直接好处是课设答辩时你可以分阶段演示哪个模块出了问题对着中间结果文件一眼就能定位。2.2 token 设计与数据结构定义token 是词法分析和语法分析之间的唯一通信协议它的设计直接决定 Parser 写起来舒服还是别扭。我一般会定义如下结构typedef enum { TOKEN_KEYWORD, // 关键字 if else while int return TOKEN_IDENTIFIER, // 变量名、函数名 TOKEN_NUMBER, // 整数常量 TOKEN_OPERATOR, // - * / ! TOKEN_DELIMITER, // ( ) { } ; , TOKEN_EOF // 文件结束标记 } TokenType; typedef struct { TokenType type; char lexeme[128]; // 原始字符串如 while、i、123 int line; // 所在行号错误报告用 int column; // 所在列号 int value; // 数字字面量的整数值方便后续计算 } Token;这里有两个关键设计决策。第一line 和 column 必须记录不然语法分析报错时只能报“第几行有错”却指不出具体位置答辩时分析问题会很被动。第二lexeme保留原始字符串而value单独存整数值——比如123这个 tokenlexeme是123value是整数 123后续生成中间代码时直接取值不需要重复转换。符号表的结构可以这样设计typedef struct Symbol { char name[128]; // 变量名 int type; // INT 或 VOID int scope; // 作用域层级0 为全局 int initialized; // 是否已初始化 struct Symbol *next; // 哈希冲突链 } Symbol;符号表用简单哈希表实现以变量名为 key。作用域用层级编号区分全局变量 scope0进入一个{}块后 scope1退出时删除所有该层级的符号。这里有个容易忽略的点词法分析器判断一个if是关键字还是标识符靠的是先查关键字表再查符号表——如果标识符恰好叫if词法阶段就要报错而不是到语法阶段才报。这个顺序在答辩时经常被追问提前在报告里写清楚。2.3 接口约定Token 流如何传递给 Parser两个模块之间的接口通常定义为一个函数Token nextToken()。Parser 每调用一次词法分析器就从输入缓冲区读入若干字符切出一个 token 返回。但实际工程里Parser 经常需要“向前看”一个 token 才决定如何归约所以词法分析器要提供一个peekToken()或pushback()能力。Token current_token; // 当前正在处理的 token Token lookahead; // 向前预读的一个 token Token getNextToken() { // 如果 lookahead 已经被填充先返回它并清空 // 否则调用词法分析器生成新 token }这个缓存机制是词法分析和语法分析联调时最常见的坑——如果 Parser 预读了一个 token 但没正确回推语法分析就会漏掉一个 token导致后续所有规则错位。我的做法是词法分析器内部维护一个最多 2 个 token 的缓冲队列Parser 只能通过getNextToken()和peekToken()访问禁止直接调用底层的字符读取函数。接口定死了模块之间的边界就清晰了。3. 词法分析实现直接编码DFA与关键字的识别策略3.1 为什么不用Lex/Flex自动生成很多教材讲词法分析必提 Flex自动生成工具能基于正则表达式构造 NFA、DFA再最小化。但课设场景下我建议手写直接编码的 DFA理由有两个。第一Flex 生成的代码是黑匣子你没法在实验报告里展示分析过程答辩时导师问“DFA 状态怎么迁移的”你只能答“Flex 生成的我也不知道”。第二小型编译器的词法规则不超过 20 种 token手写状态机也就两三百行代码可控性强出问题能单步调试。直接编码 DFA 的思路是把词法规则手工整理成状态转移表循环读字符、查表、转移状态。以if、else、while关键字和有字母开头的标识符为例它们共享同一个状态组的起点——首字符是字母所以 DFA 不能在一开始就区分关键字和标识符只能先把完整的字母串读进缓冲区然后查关键字表。3.2 完整词法分析器关键代码下面这个实现只处理核心的 token 类型但它展示了直接编码 DFA 的完整骨架主循环、分派状态、关键字表查询、数字和运算符处理。#include stdio.h #include ctype.h #include string.h #define MAX_LEXEME_LEN 128 // 关键字表课设要求覆盖的核心关键字 static const char *keywords[] {if, else, while, int, return}; // 判断是否为关键字是返回 token 类型中的 KEYWORD否则是 IDENTIFIER TokenType classifyKeyword(const char *word) { for (int i 0; i sizeof(keywords) / sizeof(keywords[0]); i) { if (strcmp(word, keywords[i]) 0) { return TOKEN_KEYWORD; } } return TOKEN_IDENTIFIER; } // 核心分词函数从 source 的 pos 位置开始读取返回一个 token // 这是直接编码 DFA 的主循环所有状态迁移显式写在代码里 Token nextToken(const char *source, int *pos, int *line, int *col) { Token token; char lexeme[MAX_LEXEME_LEN]; int len 0; // 跳过空白字符空格、制表、换行。换行要维护行号 while (source[*pos] || source[*pos] \t) { (*pos); (*col); } if (source[*pos] \n) { (*line); (*col) 1; (*pos); } char c source[*pos]; token.line *line; token.column *col; // 状态1字母开头 → 读完整字母/数字串 → 查关键字表 if (isalpha(c)) { while (isalnum(source[*pos])) { lexeme[len] source[*pos]; (*pos); (*col); } lexeme[len] \0; strcpy(token.lexeme, lexeme); token.type classifyKeyword(lexeme); return token; } // 状态2数字开头 → 读完整数字串同时存整数值 if (isdigit(c)) { int val 0; while (isdigit(source[*pos])) { val val * 10 (source[*pos] - 0); lexeme[len] source[*pos]; (*pos); (*col); } lexeme[len] \0; strcpy(token.lexeme, lexeme); token.type TOKEN_NUMBER; token.value val; return token; } // 状态3运算符。注意 和 的区别 // 先读当前字符若下一个也是 则连读构成 if (c || c ! || c || c ) { char first c; (*pos); (*col); if (source[*pos] ) { (*pos); (*col); token.type TOKEN_OPERATOR; sprintf(token.lexeme, %c%c, first, ); return token; } token.type TOKEN_OPERATOR; token.lexeme[0] first; token.lexeme[1] \0; return token; } // 状态4分隔符 if (c ( || c ) || c { || c } || c ; || c ,) { (*pos); (*col); token.type TOKEN_DELIMITER; token.lexeme[0] c; token.lexeme[1] \0; return token; } // 状态5无法识别 → 报错同时跳过该字符避免死循环 if (c \0) { token.type TOKEN_EOF; strcpy(token.lexeme, EOF); return token; } // 非法字符返回一个特殊的错误 token由调用方决定是否终止编译 (*pos); token.type TOKEN_EOF; // 这里简化为 EOF实际上应定义 TOKEN_ERROR sprintf(token.lexeme, unexpected char %c at line %d col %d, c, *line, *col); printf(%s\n, token.lexeme); return token; }3.3 参数设计与常见误用这段代码里有三个关键参数要重点说明也是课设报告里值得写的技术点。第一个是line和col的维护方式。很多同学用strtok切 tokentoken 切出来了行号丢了。错误报告里只能写“语法错误”写不出“第 3 行第 5 列”。别小看这个实验报告评审时带行列号的错误报告是加分的答辩演示时故意输错一个符号看编译器报错信息比口头解释十句都有说服力。第二个是关键字表的分类策略。我前面给的是先读完整字母串再查表这是推荐做法。反面做法是每读一个字符就判断是否匹配某个关键字——比如读到i就等等看看是不是if——这会让状态机多出大量状态维护成本飙升。先收集完整字符串再统一查表状态机只有一条“标识符”路径简单得多。第三个是数字字面量的value字段。如果不在词法阶段计算整数值语法分析阶段构造 AST 节点时123这个串就要重新解析一遍而且如果你在 AST 里存的是字符串后端生成三地址码时还要再转一次整数。词法阶段转好后面所有阶段直接用token.value省掉重复转换也避免“不同阶段转换结果不一致”的玄学 bug。词法分析最容易翻车的点是和的区分以及、这类双字符运算符。上面的代码用一个“预读回退”的写法处理先读第一个字符再看下一个是不是是就连读不是就回退到只读第一个字符的状态。这里注意pos已经向前移动了回退时要(*pos)--同时(*col)--否则列号会错。列号一错Parser 用行号做错误定位的“后悔药”就没了。4. 语法分析实现递归下降法与错误恢复机制4.1 文法设计与优先级处理小型编译器最常见的文法包括表达式、赋值语句、条件语句、循环语句和复合语句块。为了控制复杂度通常用优先级爬升法处理算术表达式的优先级而不是单独为每个优先级写一个函数。但课设如果时间紧直接按优先级分层写函数也够用。文法骨架如下program → statement_list statement_list → statement statement_list | ε statement → if_stmt | while_stmt | assign_stmt | block_stmt block_stmt → { statement_list } assign_stmt → identifier expression ; if_stmt → if ( expression ) statement [else statement] while_stmt → while ( expression ) statement expression → additive_expr [( | | | !) additive_expr] additive_expr → term {( | -) term} term → factor {(* | /) factor} factor → ( expression ) | number | identifier这里要特别留意if_stmt的else悬空问题。C 语言的规则是else匹配最近的未匹配if递归下降解析时if_stmt函数在解析完“then 子句”之后不要立即返回而是先 lookahead 看下一个 token 是不是else是则继续解析 else 分支。这个顺序不能反过来否则嵌套 if 的结构会解析错。4.2 Parser 核心实现表达式优先级与循环语句处理以下代码展示了递归下降法中两个最关键的部分表达式解析带优先级和 while 循环解析。#include stdio.h #include stdlib.h #include string.h // AST 节点类型 typedef enum { NODE_NUMBER, // 数字字面量 NODE_VAR, // 变量引用 NODE_ASSIGN, // 赋值表达式left 为变量right 为表达式 NODE_BINOP, // 二元运算opr 存运算符字符 NODE_IF, // if 语句 NODE_WHILE, // while 语句 NODE_BLOCK // 语句块 } NodeType; typedef struct ASTNode { NodeType type; int value; // 仅 NODE_NUMBER 使用 char name[128]; // 仅 NODE_VAR 使用 char opr; // 仅 NODE_BINOP 使用存 - * / 等 struct ASTNode *left; // 通用左子节点 / then 分支 struct ASTNode *right; // 通用右子节点 / else 分支可为 NULL struct ASTNode *next; // 仅语句列表使用下一条语句 } ASTNode; // 全局 token 流 extern Token current_token; extern Token lookahead; void advance(); // 读取下一个 token void match(TokenType type); // 匹配指定类型不匹配则报语法错误 // 前向声明因为 term 和 factor 相互调用 ASTNode* parseExpression(); ASTNode* parseTerm(); ASTNode* parseFactor(); // 解析 while 语句while ( expression ) statement // 返回值是 WHILE 节点left 是条件表达式right 是循环体语句 ASTNode* parseWhile() { match(TOKEN_KEYWORD); // 当前 token 必须是 while但这里需要验证 lexeme if (strcmp(current_token.lexeme, while) ! 0) { // 错误恢复报错并跳过本语句回到同步点 printf(line %d: expected while\n, current_token.line); synchronize(); // 跳过分号或右花括号之前的 token return NULL; } advance(); match(TOKEN_DELIMITER); // ( ASTNode *cond parseExpression(); match(TOKEN_DELIMITER); // ) ASTNode *body parseStatement(); // 解析循环体如果是复合语句则是 BLOCK 节点 ASTNode *node (ASTNode*)malloc(sizeof(ASTNode)); node-type NODE_WHILE; node-left cond; node-right body; node-next NULL; return node; } // 表达式解析先解析加法表达式再看有没有比较运算符 // 注意比较运算在 C 语言中优先级低于算术所以要放在最外层 ASTNode* parseExpression() { ASTNode *left parseTerm(); // 先解析项乘法优先级 while (current_token.type TOKEN_OPERATOR (current_token.lexeme[0] || current_token.lexeme[0] || current_token.lexeme[0] )) { // 这里要判断是 而不是 但词法分析已经把 单独归类 // 所以需要检查 lexeme 的长度是否为 2 char op current_token.lexeme[0]; current_token.lexeme[0] current_token.lexeme[1] ? (op ) : (void)0; // 统一存为 类型上标记为比较 advance(); ASTNode *right parseTerm(); ASTNode *bin (ASTNode*)malloc(sizeof(ASTNode)); bin-type NODE_BINOP; bin-opr op; bin-left left; bin-right right; left bin; } return left; }4.3 错误恢复怎么从语法错误中活过来递归下降解析器遇到第一个语法错误就终止编译这是个坏设计。因为你没法在答辩现场写对的代码——演示时故意展示编译错误处理能力比展示正确的编译过程更能体现工程意识。错误恢复的典型做法是 panic mode 同步发现错误后抛弃 token 直到找到一组同步标记再从同步点重新开始解析。实现层面要注意三点。第一同步点的选择要有意义分号;是语句结束标志右花括号}是块结束标志这两个是最常用的同步标记。第二同步前要输出清晰的错误信息包括行号、期望的 token、实际得到的 token让人一看就知道哪里错了。第三同步失败时要强制前进一个 token避免两个错误连续出现导致死循环——很多同学写的错误恢复“活不过来”就是因为遇到错误后 token 不前进永远停在同一个报错位置。// 同步恢复跳过分号或右花括号之前的 token回到可继续解析的位置 void synchronize() { while (current_token.type ! TOKEN_EOF) { if (current_token.type TOKEN_DELIMITER) { if (current_token.lexeme[0] ; || current_token.lexeme[0] }) { // 分号是语句结束花括号是块结束这两个位置适合恢复解析 advance(); // 消费掉这个同步标记 return; } } advance(); // 跳过当前 token继续找同步点 } }match函数是错误恢复的关键入口。我一般会在match里做两层策略如果期望 token 不匹配先报错然后看当前 token 是不是同步标记是则返回让上层着处理不是则调用synchronize跳完错误区域。这样既保留了错误信息又不会让错误连锁爆发。4.4 常见误用把多个优先级写在同一层最常翻车的写法是“一个函数处理所有运算符”读到一个或*就不分优先级统一建一个BINOP节点。结果是1 2 * 3被解析成(1 2) * 3运算顺序错误。优先级必须通过函数嵌套实现parseExpression调用parseTermparseTerm调用parseFactor每个层级只处理自己那一级优先级的运算符。如果只写一个解析函数无论怎么加判断条件都不可能同时满足左结合和优先级。这是递归下降法的“地基”不要为了少写代码而挖掉它。5. 联调与排查小型编译器最容易翻车的五个问题5.1 token回推失效预读的token丢了现象Parser 明明调用了peekToken()预读了一个 token但后面解析时发现 token 流少了一个所有规则错位。原因词法分析器内部没有做 token 缓冲。peekToken()从输入流直接读入下一个 token 并返回但没保存等真正的getNextToken()调用时又去读了一次预读的 token 就丢掉了。本质是“预读只读不存”。解决在词法分析器内部维护一个容量为 2 的 token 缓冲数组。peekToken()先检查缓冲中是否有可用 token有则直接返回没有才调用底层分词函数填入缓冲。getNextToken()同样先看缓冲有则弹出没有则新读。这样无论 Parser 怎么交叠调用token 流都不会乱。5.2 关键字与标识符混淆用户变量名撞了关键字现象源代码里定义int if 3;编译器没有报“关键字不能作变量名”而是接受了或者报告了一个莫名其妙的错误。原因词法分析器把if识别成TOKEN_KEYWORD但符号表没有校验“声明时变量名不能是关键字”。词法阶段已经知道if是关键字了但符号表插入时没检查。解决词法分析器中classifyKeyword返回TOKEN_KEYWORD后Parser 在解析变量声明时增加检查如果当前 token 的type TOKEN_KEYWORD直接报错“期望标识符但得到关键字 if”。更彻底的做法是在词法分析器里增加一个开关如果当前上下文是“声明位置”遇到关键字直接报错。但简单起见我通常建议在 Parser 的声明解析函数里拦截一行代码的事。5.3 错误恢复死循环报错后程序不推进现象源代码有一行int x ;Parser 报错后程序卡死或者一直在报同一行错误。原因synchronize()内部没有强制前进 token 的兜底逻辑。如果当前 token 既不是分号也不是花括号并且advance()没有正确移动位置比如遇到了 EOF 边界处理不当就会无限循环打印同一行错误。解决advance()函数必须保证至少前进一个 token并在到达 EOF 时返回TOKEN_EOF。synchronize()里加一个计数守卫连续跳转超过 100 个 token 仍找不到同步标记就直接丢弃整条语句并返回。另一个稳妥做法是每次报错后无论是否找到同步标记都强制消费一个 token用“宁可漏一个 token也不卡死”的原则保证编译器终会收敛。5.4 注释处理遗漏/* */ 和 // 没跳过现象源代码里带注释时词法分析把/当成除法运算符注释正文全被当成代码解析报出一堆错误。原因词法分析器没处理注释。很多课设要求里写了“支持注释”但学生只在文档里写了代码里没实现。解决在nextToken()开头、识别运算符之前增加注释分支。遇到/时向后看一个字符如果是//跳过整行直到换行如果是/*跳过直到*/期间要维护行号和列号注释跨行时行号必须同步更新。这个判断必须在运算符处理之前因为/既是除法运算符又是注释的起始字符先处理注释再处理运算符。注意 column 更新/*和*/里的每一个字符都要计数否则注释后面的 token 列号全错。5.5 AST内存泄漏长程序跑着跑着内存暴涨现象解释执行一个几百行的测试程序内存占用持续上升最终卡死或 OOM。原因AST 节点用malloc分配解释执行完一个节点后没有free所有节点都留在堆上。递归下降解析本身创建海量节点不释放必然爆内存。解决解释器执行完一个 AST 节点后递归释放其子树。具体做法是给每个ASTNode加一个freeNode函数后序遍历释放先释放左子树、右子树和 next 链再释放自身。一个关键点赋值节点的变量名是strdup出来的要单独判断并释放。还有一个容易被忽略的地方——错误恢复时Parser 返回NULL节点上层要判断空指针不能对NULL执行freeNode。内存问题的排查可以用valgrind跑一个短程序看泄漏的调用栈在哪个函数多半是漏了一种节点类型没释放。6. 课设验收与答辩测试用例矩阵和演示脚本6.1 怎么自验收三层测试法自验收不要“写一个程序跑通就完事”而是要有层次地测。第一层是词法分析器单测准备一个包含所有 token 类型的测试文件运行后检查 token 序列是否与预期一致。第二层是语法分析器的合法/非法测试合法程序要能生成完整 AST 并打印结构非法程序要能在指定行列报错并恢复。第三层是端到端执行测试写一个包含循环、条件、变量声明的测试源文件编译执行后检查输出值是否正确。我推荐做一份测试用例表格记录每个用例的输入、预期输出、实际输出这份表格可以直接放进实验报告的“系统测试”章节。答辩时导师问“你怎么保证你的编译器是对的”打开表格指着一行用例说“这个用例测的是 while 循环嵌套 if-else预期输出 15实际输出 15”比空口说“测试过了”有力得多。// 一个自测用的三层测试用例示例 // 源文件 test_loop.txt { int i; int sum; i 0; sum 0; while (i 5) { if (i 3) { sum sum 100; } else { sum sum i; } i i 1; } return sum; } // 预期循环结算后 sum 0 1 2 100 4 1076.2 Linux下用脚本自测如果你在 Linux 或 macOS 环境下开发写一个简单的 shell 脚本批量跑用例能省掉人工盯屏的功夫。脚本做的事很简单对每个.cmm源文件运行编译器比对输出和.expected文件不一致则打印差异。#!/bin/bash # 批量回归测试脚本遍历测试目录下的 .cmm 文件 # 执行编译器后与 .expected 文件比对退出码和输出 for src in tests/*.cmm; do base$(basename $src .cmm) ./compiler $src /tmp/out.txt 21 if [ -f tests/$base.expected ]; then if diff -u tests/$base.expected /tmp/out.txt /dev/null; then echo PASS: $base else echo FAIL: $base diff tests/$base.expected /tmp/out.txt fi else echo NO EXPECTED FILE: $base (exit code $?) fi done这个脚本的价值不在脚本本身而在于它把验收做成了可重复的过程。人工测一遍可能漏掉边界用例脚本每次跑都一样不会因为手抖跳过某个文件。我的习惯是每改完一个模块就跑一次这个脚本确保改一处没破坏其他功能——这比最后关头一次性全部测试要稳得多。6.3 答辩演示顺序先跑通再跑错最后跑设计亮点答辩演示不能只展示“编译成功然后执行出结果”那是底线而不是亮点。一个我总结的有效顺序是三步走。第一步跑通一个综合用例展示词法分析输出、语法分析输出、AST 结构和执行结果证明整条链路是通的。第二步故意输入一个语法错误的源代码展示错误报告的行列号信息和恢复能力边演示边解释“我们的编译器在遇到错误后能从下一个分号处恢复解析不会崩溃”。第三步展示你方案里最特别的设计——比如符号表的作用域分层、中间代码的打印输出、带注释的源代码处理任意一个都行。重点不是展示功能多而是展示你对某一个设计点有深入理解。导师追问“为什么这么设计”你要能答出权衡为什么用手写 DFA 而不是 Flex为什么用递归下降而不是 LR(1)。有一个小技巧答辩前把你要演示的源文件和预期输出打印出来放在手边。万一现场编译器因为某个环境原因报错你可以直接指着手里的预期输出说“这里本来应该输出 107编译器在校验阶段报出了一个环境相关错误”然后换个用例继续演示。这不是教你造假而是现场调试定位问题时能快速恢复节奏——如果你卡在一个错误上报不出来整个答辩的后半段都会笼罩在“这个项目可能没做完”的怀疑里。从那以后我每次做课设或项目演示都会强制把所有用例和预期输出整理成一张表先手工过一遍再跑脚本过一遍最后才上现场。这套习惯帮我挡掉了好几次现场翻车的尴尬希望也能帮到你顺利通过编译原理课程设计的验收。本文还有配套的精品资源点击获取
