简介北京交通大学编译原理课程实验项目完整源码集合面向计算机科学与技术专业学生及编译器初学者覆盖编译器前端六大核心模块词法分析、递归下降语法分析、LL(1)文法分析、算符优先文法分析、基于SLR(1)分析法的语法制导翻译及中间代码生成可系统学习从源程序到中间代码的完整处理流程。资源共94个文件以33个cpp源文件、29个h头文件为主辅以21个txt测试数据、6个makefile构建脚本压缩包仅66KB结构按Lab01至Lab06模块划分各模块均配有独立Makefile方便单独构建运行。已有92人学习浏览适合作为课程实验、期末复习或编译器前端入门参考。示例代码与测试用例完整配合README及说明文件能帮助理解词法规则、语法分析表构建及语义动作触发等难点是一套即取即用的编译原理实践材料。1. 从词法到中间代码六个模块怎么把编译器前端完整串起来多数人学编译原理败在“概念都懂手上一行代码写不出来”。词法分析、语法分析、语法制导翻译、中间代码生成每个名词在课本里都讲得清楚但真让你从空白文件开始搭一个能跑的前端第一反应往往是“从哪下手”。北京交通大学这套编译原理实验源码包正好把这条线完整走了一遍词法分析、递归下降语法分析、LL(1) 文法分析、算符优先文法、基于 SLR(1) 的语法制导翻译、中间代码生成六个核心实验模块互相衔接前一个模块的输出是后一个模块的输入。无论你是课程设计验收前补进度还是刷题面试前想把手写解析器练熟这套源码都能当作可复现的路线图来用。这篇笔记我会按“每个模块怎么设计、参数怎么设、坑在哪”的顺序拆开讲尽量让你下载之后能照着跑通并改出自己的版本。2. 词法分析与递归下降语法分析先扫出 Token再按文法向下钻2.1 词法分析种别码设计和扫描循环的实现思路词法分析是整个前端的地基它输出的 Token 流是所有后续模块的输入契约。实验一通常会要求手写一个扫描器不用 flex而是逐字符读入源程序根据字符类别拼出单词符号。这个模块的核心设计决策有两个种别码怎么编号以及标识符与关键字的区分逻辑放在哪一层。种别码编号的常见做法是分段管理比如把 0 留给错误1 到 20 放标识符和常量21 到 50 放运算符和分隔符51 以后才放关键字。这样区分的好处是语法分析阶段判断“当前 Token 是不是一个算术运算符”时不需要逐个关键字比对只看种别码是否落在 21 到 50 区间内即可。关键字放在后面还有一个现实原因关键字集合可能随文法扩展而增加把编号空间预留出来后面加保留字时不需要重排前面的编号避免整份源码的常量定义全部跟着改动。扫描循环的实现一般长这样C 风格写法如下typedef struct { int type; // 种别码见 token_types.h int val; // 整型常量的数值标识符则为 0 int line; // 所在行号供报错定位 char lexeme[64]; // 原始单词字符串调试用 } Token; Token next_token(FILE *fp) { int c; while ((c fgetc(fp)) ! EOF) { if (isspace(c)) { continue; // 跳过空白符 } if (isalpha(c) || c _) { int len 0; char buf[64]; buf[len] (char)c; while (isalnum(c fgetc(fp)) || c _) { if (len 63) buf[len] (char)c; } ungetc(c, fp); // 多读的字符还回去 buf[len] \0; return make_ident_or_keyword(buf, line); } if (isdigit(c)) { int v 0; while (isdigit(c fgetc(fp))) { v v * 10 (c - 0); } ungetc(c, fp); return make_int_token(v, line); } switch (c) { case : return make_token(TOKEN_PLUS, line); case -: return make_token(TOKEN_MINUS, line); case *: return make_token(TOKEN_MUL, line); case /: return make_token(TOKEN_DIV, line); case (: return make_token(TOKEN_LPAREN, line); case ): return make_token(TOKEN_RPAREN, line); // 其他运算符继续补 default: return make_token(TOKEN_ERROR, line); } } return make_token(TOKEN_EOF, line); }这个实现里最有讲究的是ungetc的使用。读到标识符末尾时循环会多读入一个不属于标识符的字符如果不把它退回输入流下一个 Token 的首字符就会凭空消失产生“拼错单词”的假象。另一个值得注意的细节是make_ident_or_keyword把“标识符还是关键字”的判断集中在一处而不是在扫描循环里边读边比对。原因是关键字集合的判定依赖完整单词边读边比会造成“读三个字符发现可能是关键字再读两个字符发现不是又得推翻重来”的尴尬局面。先按普通标识符读完整个词再到哈希表或线性表里查一次逻辑最干净这一步也是后续几个实验里“关键字被识别成普通标识符”问题的主要根源。种别码表的设计要考虑扩展性。我一般会把运算符连续编号常量和标识符放前面关键字放最后并在注释里预留一段“扩展区”。这样当你从实验一的简单算术表达式扩展到实验六的控制流语句时只需要在关键字区追加新条目不用动前面已经调通的部分回归测试的改动面会小很多。2.2 递归下降消除左递归后按产生式逐个写函数实验二进入语法分析通常要求手写递归下降。递归下降的核心思想很直接每个非终结符对应一个函数函数体按产生式右部逐个匹配终结符或调用其他非终结符函数。但直接照搬教材文法会立刻翻车因为教材里常见的E - E T带有左递归翻译成函数就是parse_E() 先调用 parse_E()第一行就无限递归栈直接爆掉。必须在写函数之前先消除左递归。以最简表达式文法为例原始文法是E - E T | T T - T * F | F F - ( E ) | num消除左递归后变成右递归形式E - T E E - T E | ε T - F T T - * F T | ε F - ( E ) | num改写后的文法保证每个非终结符的 First 集合不再包含自身。仔细观察会发现 E 和 T 的 First 集合都收敛为{ (, num }也就是说无论下一个 Token 是左括号还是数字解析器都能立即确定该走哪个分支这正是递归下降能工作下去的前提不回溯每个符号只看一次。对应的三个函数如下void parse_E() { parse_T(); // 先解析乘除法优先级更高的部分 parse_E_prime(); // 再处理后续的 或空 } void parse_E_prime() { if (lookahead.type TOKEN_PLUS) { match(TOKEN_PLUS); parse_T(); parse_E_prime(); // 右递归继续消化后续的加号 } // 否则产生式 E - ε直接返回 } void parse_F() { if (lookahead.type TOKEN_LPAREN) { match(TOKEN_LPAREN); parse_E(); // 括号内重新是一个完整表达式 match(TOKEN_RPAREN); } else if (lookahead.type TOKEN_NUM) { match(TOKEN_NUM); } else { syntax_error(F 位置期望数字或左括号); } }match函数的职责是检查当前 Token 类型与期望值是否一致一致就推进到下一个 Token不一致就报错。这里最容易漏写的是parse_E_prime里的 ε 分支表面上“什么都不做”好像无关紧要但如果你把else分支漏了当表达式读完后lookahead指向结束符程序会默认继续寻找加号结果报出“期望 实际是 EOF”的伪错误让合法的输入串也无法通过。递归下降的调试技巧是逐步跟踪函数调用栈。常见做法是在每个解析函数入口打印一行日志例如enter parse_E at line 10退出时再打印一行。遇到非法输入时观察最后进入的函数名和当时的 lookahead Token基本就能定位到文法里哪条产生式出了问题。这套源码里同样保留了类似的调试日志开关打开后可以直观看到1 2 * 3完整走过了哪些函数这对理解“优先级由文法层级保证”很有帮助。3. LL(1) 与算符优先文法两套自顶向下策略的落表和选型3.1 LL(1) 和算符优先的适用边界怎么判断实验三和实验四通常分别是 LL(1) 和算符优先很多同学会问已经学了递归下降为什么还要再学一种自顶向下的方法这其实是对“手写解析器”和“表驱动解析器”这两条路线在认识上产生了混淆。递归下降是手写代码灵活但难以自动化LL(1) 是可形式化构建预测分析表的表驱动方法自动生成工具如 ANTLR 背后就是这个原理。算符优先则专门面向表达式用终结符之间的优先关系直接指导归约不需要为非终结符建立复杂的 First 和 Follow 集合。对比项LL(1)算符优先文法限制无左递归、无公共左因子文法中任意产生式右部不能出现两个相邻非终结符分析表规模以非终结符为行、终结符为列以终结符为行、终结符为列分析过程自上而下推导替换非终结符自下而上归约比较栈顶与输入符号的优先级出错定位能报出“栈顶非终结符和当前输入”的具体冲突报出“栈顶算符与输入算符之间无比对关系”最适用场景语句级语法、表达式文法算术表达式的快速求值、语法分析器里处理表达式子模块选型经验可以总结为如果你的文法里非终结符之间存在明显层级关系语句包含表达式表达式包含项LL(1) 更合适语法错误能定位得更准确如果你只想为表达式单独做一个高效分析器或者需要频繁处理优先级不同的运算符组合算符优先的代码更精简性能也好。实践中很多编译器的手写前端会在语句层用递归下降在表达式层用算符优先或普拉特解析也就是把两种思路结合起来。3.2 LL(1) 预测分析表的构造First、Follow、select 三件套LL(1) 分析表驱动的前提是算出每个产生式的 select 集合。select 集合的计算依赖 First 和 Follow这里用一个实际例子走一遍。文法如下E - T E E - T E | ε T - F T T - * F T | ε F - ( E ) | numFirst 集合的计算几乎没有任何歧义First(E) First(T) First(F) { (, num } First(E) { , ε } First(T) { *, ε }Follow 集合稍复杂它规定了一个非终结符“后面可能跟哪些终结符”。最基础的两条规则起始非终结符的 Follow 必须包含结束符$形如A - α B β时First(β)去掉 ε要并入 Follow(B)形如A - α B且β能为空时Follow(A) 要并入 Follow(B)。逐条推下去Follow(E) 里首先有$和)——前者因为 E 是起始符后者来自F - ( E )这条产生式E 后面直接跟右括号。Follow(E) 与 Follow(E) 相同因为 E 是 E 末尾的延续部分能被 E 跟的终结符同样能跟在 E 后面。Follow(T) 需要从E - T E看E 的 First 集合是{ , ε }去掉 ε 后留下所以 Follow(T) 至少包含又因为 E 可推导出 εFollow(E) 也并入 Follow(T)于是得到Follow(T) { , ), $ }。同理可得Follow(T) { , ), $ }Follow(F) { , *, ), $ }。select 集合的定义是如果产生式右部不能推导出 εselect 就是右部 First 集合如果能推导出 ε则 select 是右部 First 集合去掉 ε 再并上左部非终结符的 Follow 集合。这个“并上 Follow”的步骤是整个计算里最容易出错的位置一旦漏掉预测分析表里就会出现多个空入口程序跑到某些合法输入时直接报“分析表无入口”。分析表本身可以用二维数组存储行标是非终结符列标是终结符加$值是产生式编号/** * 分析表局部示意完整版本见 resources/table_ll1.txt * M[E][] 2 表示栈顶是 E、当前 Token 是 时用第 2 条产生式 E - T E */ int ll1_table[NT_COUNT][TERM_COUNT] { // ( ) * num $ /* E */ {1, -1, -1, -1, 1, -1}, /* E */{-1, -1, 2, -1, -1, 3}, /* T */ {4, -1, -1, -1, 4, -1}, /* T*/ {-1, -1, 6, 5, -1, 6}, /* F */ {7, -1, -1, -1, 8, -1}, };表驱动分析的主循环并不复杂核心逻辑是“栈顶是终结符就直接比对输入是非终结符就查表找产生式”。查表得到的产生式右部需要逆序压栈因为栈是后进先出为了让右部第一个符号先弹出被处理压栈时必须从右到左。很多人在这一步把顺序写反症状很典型程序从第二个 Token 开始就一直对不上而且报错位置完全随机看不出规律。解决方法是打印每一步的栈状态和剩余输入对照手工模拟一遍逆序压栈的问题一眼就能暴露。3.3 算符优先分析三种优先关系与归约过程跟踪算符优先分析走的是另一条路它不关心非终结符只关心终结符之间的优先关系。构造分析表前先计算每个非终结符的 FirstVT 和 LastVT 集合。FirstVT 的定义是一个非终结符经过一步或多步推导可能出现在右部最左边的终结符集合LastVT 则是最右边的终结符集合。构造算符优先关系表分三步。第一步对所有形如... a b ...或... a A b ...的产生式右部在 a 和 b 之间填入。第二步对形如... a A ...的产生式右部把 a 与 FirstVT(A) 中的每个终结符配对填。第三步对形如... A b ...的右部把 LastVT(A) 中的每个终结符与 b 配对填。推导完成后得到一个终结符之间的矩阵 * ( ) num * ( ) - - num - -分析过程用符号栈实现。栈顶终结符与当前输入终结符查优先关系表当前栈顶输入说明输入符号优先级更高需要移进当前栈顶输入通常是括号配对或同级符号的边界移进当前栈顶输入说明栈顶已经可以归约在栈中找到最左素短语的边界并规约。实验三经常要求把归约过程打印出来格式类似栈: # num num * num 输入: #结束符 动作: 用 T - F - num 归约跟踪归约过程能直观看到最左素短语的概念。对num num * num第一个归约动作发生在num * num中的乘法处因为栈顶*与输入$之间存在关系所以在乘法那一段先归约这正是算符优先保证“乘法先于加法”的机制。从这份源码包的实际代码里可以看到算符优先分析器只需要维护一个栈和一张优先关系表不涉及 First/Follow 的递归计算代码量通常比 LL(1) 分析表驱动要短三分之一左右。4. SLR(1) 语法制导翻译与中间代码生成从识别语法到产出四元式4.1 LR(0) 项目集族构造与 SLR(1) 分析表的消解方式实验五的难度通常会跳一个台阶因为 SLR(1) 分析表不像 LL(1) 那样直白。构建过程分三层先把文法变成 LR(0) 项目集族再根据项目集之间的跳转关系生成 DFA最后结合 Follow 集合填出 ACTION 表和 GOTO 表。LR(0) 项目是带圆点的产生式圆点表示分析位置。例如产生式E - E T有四个项目E - . E T E - E . T E - E . T E - E T .构造项目集族时闭包计算的规则是如果项目A - α . B β在集合中那么 B 的每条产生式B - . γ都要加入集合。比如项目E - T . E在集内E 的产生式是E - T E和E - ε那么E - . T E和E - . ε也要进集合。这段逻辑用代码写出来是这样的void closure(vectorItem items) { bool changed true; while (changed) { changed false; vectorItem snapshot items; for (const Item it : snapshot) { if (it.is_at_end()) continue; Symbol s it.symbol_after_dot(); if (!s.is_nonterminal()) continue; for (int pid : productions_of(s)) { Item new_item make_item(pid, 0); if (!contains_item(items, new_item)) { items.push_back(new_item); changed true; } } } } }关键在contains_item的比较逻辑必须同时比较产生式编号和圆点位置。如果只比较产生式编号同一个产生式的不同项目会被误判为重复闭包收敛后项目集会少掉很多状态生成的 DFA 直接是错的。这种错误很隐蔽因为程序能跑只是分析表比标准表小遇到特定输入串时才突然卡住。SLR(1) 的核心改进是解决 LR(0) 的归约冲突。LR(0) 在项目A - α .处不假思索地归约完全不看下一个输入是什么。SLR(1) 则在该状态查看当前输入终结符是否在 Follow(A) 中不在就不归约继续移进。以文法S - L R和S - R为例经典状态下会遇到移进-归约冲突SLR(1) 通过 Follow(S) 和 Follow(L) 的区分能在部分情况下消解但无法覆盖全部。当分析表出现双重入口时比较规范的处理是保留一个动作并记录冲突来源在实验报告里写明“该冲突由文法特性导致SLR(1) 无法消解这里选择保留移进动作以避免错误归约”。SLR(1) 分析表的 ACTION 和 GOTO 可以直接复用算符优先分析里的栈驱动框架只是栈里同时存符号和状态号归约时按产生式右部长度弹出对应栈帧再根据左部非终结符查 GOTO 表跳转。跑通这个流程后你会发现自己已经能理解 Bison 生成工具输出分析表时的很多行为这是手写 SLR 的最大收获。4.2 语法制导翻译在归约的同时发射四元式实验六是前五个模块的会合点。语法制导翻译的核心思想是给每条产生式挂一个语义动作分析器在规约到该产生式时执行动作。以表达式赋值语句为例文法可以写成S - id E E - E T T - T * F F - ( E ) F - num对每个非终结符维护两个属性place表示存放结果的变量或临时变量名code表示累积的中间代码序列。产生式E - E1 T的语义动作是E.place new_temp(); E.code E1.code || T.code || emit(E.place, , E1.place, , T.place)从这份源码包的实际实现来看属性传递用的是属性栈方式。分析栈每个位置除了符号还挂一个属性指针规约发生时右部各符号的属性从栈里取出计算出的左部属性写回新栈帧。这个方案的优点是和 SLR(1) 分析表的栈操作天然同步不需要额外维护一棵语法树缺点是对属性栈的长度变化要格外小心否则归约时取属性会取错位置。四元式是中间代码里最容易验证的格式每条指令四个字段(op, arg1, arg2, result)对a b c * d的输出序列是(*, c, d, t1) (, b, t1, t2) (, t2, _, a)临时变量名由计数器生成从 t1 开始依次递增。这里有个实现细节值得注意临时变量编号建议从 1 开始并在每次分析开始时重置不然连续分析多个表达式时编号会持续膨胀后一个表达式的四元式序号和前一个衔接不上对比结果时会造成困惑。很多同学在这个实验用 Java 重写时会遇到属性栈实现不一致的问题。Java 端没有 C/C 的指针运算常见做法是用ArrayListSymbolAttribute充当属性栈归约时按右部长度从栈尾倒序取出属性计算后 push 回左部属性。需要注意栈尾顺序和产生式右部书写顺序的对应关系E - E1 T归约时栈尾依次是 E1 的属性和 T 的属性取属性时先取到的是 T别把位置搞反。这一条在排错过程中的出现频率极高几乎每个手写属性栈的人都会在这踩一次。5. 六个实验的常见问题排查现象、原因与解决5.1 Token 流里少了第一个字符现象输入1 2词法分析输出的第一个 Token 是 2数字1凭空消失。原因扫描循环里读数字时判断isdigit(c)的循环条件在读取到第一个非数字字符后退出但退出前没有ungetc将那个字符退回输入流导致下一个 Token 从错误的位置开始读。解决所有“读一个超长词”的分支在循环结束后都补上ungetc(c, fp)。这条规则对标识符、数字、字符串常量都适用。最稳妥的自检方法是打印每个 Token 的原始 lexeme 字段肉眼比对输入与输出任何错位都会在第一时间暴露。5.2 关键字被当成普通标识符处理现象输入if (a 0) b 1;Token 流里if被识别为 IDN 而不是 IF 关键字递归下降在语句入口处直接报语法错误。原因make_ident_or_keyword判断关键字时用的是线性查找但关键字表里if与int存在公共前缀匹配逻辑按“前缀匹配”而不是“全字匹配”导致if匹配到int的条目或直接落空。解决关键字判断必须做完整字符串比较可以先用哈希表把关键字集合索引起来再逐字比较或者直接构造一个包含全部关键字的unordered_setstring查成员。前缀匹配问题比想象中常见尤其是关键字表里同时存在if和int这样的词对时很容易翻车。5.3 LL(1) 分析表的空入口导致合法输入被拒现象对输入1 * (2 3)做 LL(1) 分析跑到T状态时查表入口为 -1报“分析表无入口”但该输入显然是合法文法。原因select 集合计算时把 ε 产生式的处理顺序弄错了。T - ε是一条产生式它的 select 集合是 Follow(T)如果你在前面把 Follow(T) 算少了或者漏掉了某个终结符分析表里(T, )就可能是空入口。解决把每个产生式的 select 集合同步输出到一个文本文件与参考表逐行对照。这套资源里附带的select_set.txt是一个很好的标准答案代码算出的结果与它不一致时优先检查 Follow 集合的递归传递方向其次检查 ε 是否被错误地从 First 集合中删除。5.4 SLR(1) 状态数异常膨胀现象项目集闭包算完状态总数比参考数据多了几十个分析表局部出现明显重复的行。原因闭包去重逻辑里只比较了产生式编号忽略了圆点位置导致同一个产生式的不同项目被当作同一个对象合并时丢失了必要的状态分叉。另一种可能原因是 GOTO 表构造时对同一符号生成了多条重复边。解决打印每个状态的项目列表人工抽样验证几个关键状态。如果发现“状态 5 和状态 12 长得一样”优先检查项目集的相等性判断函数确认是否同时比较了 produce_id 和 dot_pos以及是否比较了左部符号。5.5 四元式生成的临时变量序号错乱现象同一个表达式分析两次输出的四元式里临时变量有时从 t1 开始有时从 t3 开始结果无法对照。原因临时变量计数器是全局变量上一次分析的残留值没有在每次分析开始时重置。另一个可能是在归约动作里直接用了计数器的当前值导致同一产生式被归约两次时拿到不同编号。解决在begin_parse()入口处将计数器显式归零。更稳妥的做法是让计数器和分析器对象绑定而不是作为文件级全局变量这样即使在同一个程序里多次调用分析过程也不会互相干扰。5.6 算符优先归约时栈底残留终结符现象num num * num归约完成后栈里是# E #但中间某一步出现了# E #的滞留状态后续无法继续归约。原因算符优先关系表里加法与结束符之间的优先关系填反了。$作为结束符应该比所有运算符的优先级都低即所有运算符对$都取关系这样栈顶运算符才能在输入结束时正常归约。一旦填反加号会一直留在栈顶等一个永远不来的输入符号。解决检查关系表中$所在行与列的值初始#对所有输入终结符取所有终结符对收尾$取。这两条边界值错了整个归约过程都会在收尾阶段卡住。6. 验收前必做的三层对照验证从 Token 流到四元式这套源码包里的六个模块虽然各自独立但运行时存在严格的前后依赖。如果只在最后一个模块里看到预期结果很可能是前面模块的错误被后续模块“侥幸兜住”了换一组输入就会翻车。我自己的验收习惯是分三层做交叉验证每一层都有明确的输出物。第一层是词法对照。取一段带全部运算符和至少两个关键字的示例代码打印 Token 流人工核对每个 Token 的种别码与 lexeme。这是最容易被跳过的步骤但跳过的代价是后面所有模块的错误定位成本成倍上升。词法层出错语法层报错位置通常与实际错误严重偏离查起来非常痛苦。第二层是语法交叉验证。对同一输入用递归下降和 SLR(1) 分析器各跑一遍两个分析器的判定结果必须一致。发现不一致时以递归下降的结果为基准因为递归下降代码可读性最高逐行对照产生式能快速找到文法层面的分歧。很多 SLR 分析表的隐蔽错误都是在这种交叉验证中被揪出来的。第三层是中间代码语义验证。对表达式(a b) * (a - b)输出四元式应该看到临时变量在加法、减法、乘法三个位置分别产生数量与文法归约层级严格对应。一个简单而有效的校验指标是四元式总数 产生式归约次数中“带运算动作的数量”多一个临时变量意味着某处多算了少一个则意味着语义动作被跳过。下图是(a b) * (a - b)的完整四元式输出格式(, a, b, t1) (-, a, b, t2) (*, t1, t2, t3)临时变量数量在这一层是有明确预期的一旦对不上优先检查E - E T这类产生式对应的语义动作是否附加在正确的位置。如果动作挂错了产生式四元式数量和顺序都会出现系统性的漂移。最后分享一个让我少熬好几晚的小习惯每个模块建立一个“最简回归用例”文件。词法用一个a 1就够递归下降用1 2 * 3算符优先用(1 2) * 3SLR(1) 用带括号和两个运算符的表达式四元式生成则用a b c * d。每改完一次代码先跑这组最简用例通过后再跑大型测试。这个回归清单能从第一次实验一直用到最后一个模块遇到难定位的 bug退回最简用例做二分排查效率比在长表达式里盲找高得多。从那以后我每次接手编译原理相关的课程设计或小型解释器都会强制自己先写回归脚本再做功能改动。希望这份源码资源和这篇拆解能帮你把编译原理实验从“能过”做到“真懂”。本文还有配套的精品资源点击获取
