编译原理实验全解析：词法分析、NFA转DFA、递归下降与LL(1)语法分析

简介编译原理是计算机科学的核心课程编译器前端由词法分析和语法分析构成。词法分析基于有限自动机将源代码转换为记号流语法分析则依赖上下文无关文法验证程序结构。针对非确定性自动机子集构造法利用ε闭包与move函数实现NFA到DFA的转换而递归下降和LL(1)分析分别代表手写解析器与表驱动解析器的典型实现。围绕一套完整的杭电编译原理实验详细剖析SysY语言中八进制/十六进制数字识别、注释状态转移、FIRST集与FOLLOW集计算等工程细节并结合常见错误给出调试与避坑指南帮助读者快速打通从源代码到语法树的完整链路掌握编译器前端核心算法的实践方法。1. 拿到一个能跑起来的杭电编译原理实验C 源码与四个可执行程序这套杭电编译原理实验源代码拿到手就是四个可以直接打开的 C 工程词法分析、子集构造法NFA 转 DFA、递归下降分析、LL(1) 语法分析。每个工程都是 .cpp 配 .exe外加 test.sy 和 result.txt 两个样例文件把编译器前端最核心的四个算法一次凑齐了。对正在赶实验报告的人来说它的价值不是某段源码多惊艳而是四个算法件套齐全、能编译能运行连测试输入都给你备好了可以先跑一遍看结果再对照代码理解每一层在做什么。对想弄懂编译前端的读者这四个程序正好覆盖从字符串到语法结构的完整链路动手改几处输入就能直观看到状态转换和推导过程的变化。需要提醒的是摘要里把 LL(1) 说成“自底向上”是笔误LL(1) 属于自顶向下分析后面第 4 章会专门讲清楚。2. 词法分析环节读懂 SysY 的记号识别从 test.sy 跑到 result.txt2.1 先读懂五个状态八进制、十六进制和两种注释是重点词法分析器本质是一个确定性有限自动机每个 token 类别对应一组状态转移实验中用到的语言是 SysY一种 C 语言风格的教学语言。和普通 C 语言子集相比实验特别强调三件事以 0 开头的八进制数、以 0x 开头的十六进制数、//行注释和/* */块注释。拿到词法分析.cpp 后先别急着看整个文件直接从状态转移函数入手通常核心就一个 while 循环加一个 state 变量。// 词法分析核心状态转移简化0初态 1行注释 2块注释 3数字 4标识符 int state 0; char buf[64]; int len 0; while ((ch nextChar()) ! EOF) { if (state 0) { // 初态先判断是不是注释再看是不是数字或标识符 if (ch / peek() /) { state 1; // 行注释读到换行再回初态 } else if (ch / peek() *) { state 2; // 块注释可能跨行 } else if (isdigit(ch)) { buf[len] ch; state 3; // 进入数字扫描 } else if (isalpha(ch) || ch _) { buf[len] ch; state 4; // 进入标识符扫描 } else { output(ch); // 运算符和界符直接输出 } } else if (state 1) { if (ch \n) state 0; // 行注释结束 } else if (state 3) { if (isxdigit(ch) || ch x || ch X) { buf[len] ch; // 吸收 0x 前缀或十六进制字符 } else if (isdigit(ch)) { buf[len] ch; // 普通数字字符 } else { state 0; // 碰到非数字字符回退并输出 token ungetc(ch, stdin); outputToken(buf, len); len 0; } } }这段代码里最值得注意的点是peek()它在初态向前多看一个字符目的是区分“除号”和“注释开始”。很多人在写词法分析时图省事先匹配到/就直接当运算符输出等读到下一个字符才发现是注释这时再回退状态就非常别扭。用peek()提前判断初态的逻辑会清爽很多。块注释的部分没有写全因为实际代码里它是 2 到 3 个状态的循环普通注释态遇到*先进入“可能结束”的暂态再判断下一个字符是不是/是才回到初态。这个细节很容易写错比如只判断到*就退出注释态会把后面所有代码都吞掉第 5 章会重点讲。八进制和十六进制是另一个坑。数字进入 state 3 后buf里第一个字符是0这时要看第二个字符才能决定进制// 数字收尾时的进制判定逻辑在 outputToken 中完成 int radix 10; if (buf[0] 0) { if (buf[1] x || buf[1] X) { radix 16; // 0x 开头按十六进制 } else { radix 8; // 0 开头按八进制 for (int i 1; i len; i) { if (buf[i] 8 || buf[i] 9) { error(非法八进制数); } } } } int value strtol(buf, NULL, radix); // 按对应进制转换判断顺序是先看0x前缀再看纯0开头。如果buf[0]是0但第二位不是x就是八进制后续出现 8 或 9 应该直接报词法错误而不是继续累加。实验里要求识别八进制和十六进制意味着052转出来应该是十进制 420x1f应该是 31如果 result.txt 里输出的是 52就是这里漏了分支。2.2 跑通第一个实验从 test.sy 到 result.txt拿到压缩包后建议先别打开编辑器看代码直接把自带的 exe 跑一遍确认环境没问题。在 Windows 的 cmd 里切到解压目录用输入输出重定向运行cd /d D:\experiments\编译原理实验 词法分析.exe test.sy result.txt表示从 test.sy 读入源码表示把结果写到 result.txt这样程序不会进入交互模式结果可以反复对比。很多同学直接双击 exe窗口一闪而过什么都看不到后面第 5 章第一条就是这个坑。自带的 test.sy 是一个 SysY 样例内容类似下面的结构/* 块注释声明两个变量 */ int a; int b 052; // 八进制十进制是 42 a 0x1f; // 十六进制十进制是 31跑完之后打开 result.txt常见格式是每行一个 token比如类型, 值, 行号也可能用int、ident、num这样的类别名。先看前几行是不是把int、a、b正确分开再重点检查052这一行输出的值是不是 420x1f是不是 31。如果这两个数不对说明数字状态转移有问题直接跳到第 5 章的 5.2。这个环节涉及的文件不多列一下方便对照文件作用test.sySysY 源代码改它来换测试用例词法分析.cpp词法分析器源码词法分析.exe编译好的可执行文件result.txt运行后生成的 token 序列想改源码重新编译的在 vs code 里配好 c/c 环境之后用 g 一条命令就能编g 词法分析.cpp -o 词法分析.exe。需要注意编码问题Windows 下如果源码里有中文注释要把编辑器默认编码设成 ANSI 或 GBK否则控制台输出会出现乱码但不影响 token 结果。3. 子集构造法环节从 NFA 到 DFA状态图怎么生成才不丢规则3.1 NFA 转 DFA 的核心是 closure 和 move 两个函数子集构造法的原理一句话能说清DFA 的每一个状态对应 NFA 状态的集合。剩下的工作就是反复计算两个函数——eps_closure(T)求从集合 T 出发沿 ε 边能到达的所有状态move(T, a)求从 T 出发吃掉一个字符 a 后能一步到达的状态集合。这两个函数交替执行新产生的集合不断加入 DFA 状态表直到没有新集合出现为止。move的实现很直接就是遍历集合 T 里每个状态查转移表里吃字符 a 能到哪些状态全部收进去。真正容易写错的是eps_closure它必须做传递闭包不能只收集一轮直接可达的 ε 转移setint epsClosure(setint T) { setint result T; // 集合自身也在闭包内 queueint q; for (int s : T) q.push(s); while (!q.empty()) { int cur q.front(); q.pop(); for (int nxt : epsTrans[cur]) { // epsTrans每个状态的 ε 转移表 if (result.find(nxt) result.end()) { result.insert(nxt); q.push(nxt); // 新加入的状态还能继续走 ε 边 } } } return result; }为什么必须用队列迭代因为 ε 转移可以连续发生比如状态 0 走 ε 到状态 1状态 1 还能走 ε 到状态 2。如果只扫描一轮状态 2 就丢了。用队列的目的就是让每一次新加入的状态都有机会继续扩展直到集合不再变大为止。我见过不少初学版本只写一个 for 循环结果是 DFA 状态表缺了一大块后面图怎么对都对不上。主循环是另一个容易乱的地方。一般的做法是维护一个“未处理的 DFA 状态”队列每个状态是一个 setmapsetint, int stateId; // NFA 状态集合 - DFA 状态编号 queuesetint unprocessed; setint startSet epsClosure({nfaStart}); stateId[startSet] 0; unprocessed.push(startSet); while (!unprocessed.empty()) { setint T unprocessed.front(); unprocessed.pop(); for (char a : alphabet) { // 逐个字符计算转移 setint U epsClosure(move(T, a)); if (U.empty()) continue; // 没有可达状态就跳过 if (stateId.find(U) stateId.end()) { int newId stateId.size(); stateId[U] newId; unprocessed.push(U); // 新状态还要继续展开 } addDfaEdge(stateId[T], stateId[U], a); } }这里最关键的一步是stateId用mapsetint, int做去重。同一个 NFA 状态集合如果再次出现必须映射到已有的 DFA 状态编号否则会出现大量重复状态。每次从队列里取出集合 T都要重新算一遍所有字符的 move 和闭包工作量看起来不小但实验给的 NFA 规模一般都控制在十几个状态以内这个循环几乎瞬间完成。3.2 输入 NFA 和输出 graph.txt怎么验证结果对不对实验里的子集构造法.cpp 通常支持两种输入方式一种从文件读 NFA 状态表另一种在命令行交互输入。常见做法是用文本定义状态表格式大致如下字段含义示例状态数NFA 总状态数4字符集参与转移的字母表a b转移规则每行s c t从 s 吃字符 c 到 t0 a 1ε 转移用 e 表示 ε 边0 e 2初态起始状态编号0终态接受状态集合3我把上面这些字段手动填到一个文本里然后运行子集构造法.exe程序会输出 graph.txt里面每一行是一条 DFA 边格式类似0 a 1表示 DFA 的 0 状态吃字符 a 到 1 状态最后再标记哪些状态是终态。验证结果有个笨但有效的办法选一个不含 ε 的小路径手工在纸上推一遍再对照 graph.txt。比如输入一个匹配a(a|b)*b的 NFA最终 DFA 状态数应该在 3 到 4 个左右。如果跑出来十几个状态基本可以断定是 ε 闭包只做了一层或者状态去重失效。还有一个检查技巧graph.txt 里不应该出现 ε 边因为 DFA 的定义里每个字符的转移是确定的ε 边一旦出现说明闭包没有提前算完把 ε 转移漏进了输出。4. 递归下降分析和 LL(1) 环节先消除左递归再动手写函数4.1 每个非终结符一个函数怎么设计才不会乱递归下降分析的写法非常固定文法里每个非终结符对应一个 C 函数函数体按照产生式右侧的符号顺序去读 token。实验里的 test.sy 是 SysY 的一个子集包括变量声明、赋值、if、while 这类结构对应的非终结符通常有 program、decl、stmt、expr、term、factor 等七八个每个都拆成一个函数入口从 program 开始。看下面这个经典的表达式文法E - T E E - T E | ε T - F T T - * F T | ε F - ( E ) | id对应的递归下降代码骨架是这样的int pos 0; // 当前 token 下标 vectorToken tokens; // 词法分析输出的 token 序列 void parse_E() { parse_T(); // E 的产生式右侧先是一个 T parse_E1(); // 再跟 E } void parse_E1() { if (pos tokens.size() tokens[pos].type TOK_PLUS) { pos; // 吃掉 parse_T(); // 递归处理 后面的 T parse_E1(); // 继续看还有没有 } // 否则按 ε 处理什么都不做直接返回 } void parse_T() { parse_F(); parse_T1(); } void parse_F() { if (tokens[pos].type TOK_ID) { pos; } else if (tokens[pos].type TOK_LPAREN) { pos; parse_E(); // ( 后面是整个表达式 if (tokens[pos].type ! TOK_RPAREN) { error(pos, 缺少右括号); } pos; } else { error(pos, 期待标识符或左括号); } }这段代码里最核心的设计是pos作为全局下标所有函数共享同一个 token 流位置谁吃掉 token 谁负责推进。每个函数开头先判断当前 token 是否属于自己要处理的 FIRST 集属于才继续不属于就直接返回或报错。E的处理是递归下降的典型写法先看当前 token 是不是是就吃掉并递归进入右部不是就按空串处理。这种“先判断再决定走哪个分支”的模式贯穿整个实验代码。错误提示功能在实验里是硬性要求报错时要带行号和当前 token 类型方便定位到 test.sy 的具体行。我在写这类代码时一般会让 error 函数同时打印pos和tokens[pos].line这样语法错误出现时一眼就能看到是第几行出了问题而不是只给一个笼统的“syntax error”。4.2 递归下降和 LL(1) 的差别手写函数与查表驱动很多同学做完递归下降再做 LL(1) 实验会感觉两个东西很像甚至觉得重复。其实递归下降就是手工实现 LL(1) 预测分析一个字节能说清两者的区别一个用函数调用栈模拟推导一个用显式分析栈加预测分析表驱动。LL(1) 实验里的 LL1.cpp 就是把文法规则整理成一张二维表横轴是非终结符纵轴是终结符表项是下一步要用的产生式。建表之前必须先算 FIRST 集和 FOLLOW 集。FIRST 集的迭代计算是这类实验最容易翻车的地方// 计算所有非终结符的 FIRST 集简化伪代码 mapstring, setstring FIRST; while (集合还有变化) { for (每个产生式 A - Y1 Y2 ... Yn) { for (int k 0; k n; k) { FIRST[A].insert(FIRST[Yk]); if (ε 不属于 FIRST[Yk]) break; // Yk 不可空后面符号不再贡献 } } }内层循环的 break 是整个算法的关键产生式右侧是一个符号序列只有前面的符号都能推导出空串后面符号的 FIRST 才能进入 A 的 FIRST。这个“可空性”判断漏掉之后FIRST 集会变大预测分析表里同一格会出现多个产生式文法就被判定成不是 LL(1)。我调试这类代码时习惯把每个非终结符的 FIRST 集打印出来拿纸笔推一遍两边对不上就说明迭代或 break 写错了。两个实验的对比可以从这个角度理解对比点递归下降LL(1) 分析器驱动方式函数调用栈显式分析栈 预测表实现难度低适合小文法建表繁琐适合程序生成出错定位函数边界处直接抛出依赖栈顶与表的匹配适用场景手写小语言文法规模较大时用工具生成摘要里“LL(1) 自底向上”的说法不准确LL(1) 的全称是 Left-to-right scan, Leftmost derivation, 1 token lookahead从名字就能看出它构造的是最左推导属于自顶向下分析。真正自底向上的代表是 LR 系列不在这个实验范围内。递归下降和 LL(1) 都属于自顶向下区别只在于一个是手写逻辑一个是查表驱动。5. 避坑与排错五个最容易翻车的环节5.1 双击 exe 一闪而过看不到任何结果现象在资源管理器里双击词法分析.exe窗口闪一下立即关闭什么也没看清。原因程序运行完控制台窗口自动关闭Windows 的默认行为就是这样不是程序报错。如果程序内部存在读取输入的死循环还可能表现为卡顿后强制退出但常见情况只是窗口关闭太快。解决不要用鼠标双击打开 cmd 切换到 exe 所在目录用重定向方式运行。词法分析.exe test.sy result.txt把结果写进文件再打开文件看内容。如果需要交互输入就先在 cmd 里直接输入程序名运行。想在 IDE 里调试时可以在 main 末尾加system(pause)但这不是好习惯那只是看结果的后悔药真正调试还是要用命令行重定向配合 printf 检查中间状态。5.2 052 被识别成 52八进制数没有按八进制处理现象test.sy 里写b 052result.txt 输出 52 而不是十进制 42。原因数字状态没有根据首字符区分进制。扫描进入数字分支后只把后续数字字符累加保存没有在 token 收尾时检查buf[0] 0这个条件052 被当作十进制字符串直接转换。解决在数字收尾函数里先判断前缀。0x或0X开头按十六进制转换0开头按八进制转换而且要检查 8 和 9 是否为非法字符。改完重新编译跑第 2 章那个 test.sy确认 result.txt 中 052 对应 42、0x1f 对应 31。数值识别错误影响的不只是显示后续语义分析拿到的常数表全是错的所以这一步必须验。5.3 块注释吃掉了后续所有代码现象文件里有/* xxx */后面还有正常代码但 result.txt 里后面内容全部消失。原因块注释的结束条件写错最常见的是遇到*就直接退出注释态没有判断下一个字符是不是/。还有一种是注释态恢复初态时没有正确消费/导致注释结束符只消费了一半程序一直停在注释状态。解决注释处理要拆成至少两个状态普通注释态收到*进入“可能结束”的暂态暂态里再看下一个字符是/才恢复初态不是则退回普通注释态继续扫描。改完后用一个包含/* ... */且在注释后还有 int 声明的 test.sy 验证确认注释后面的代码能正常产出 token。5.4 子集构造法跑出来一堆重复 DFA 状态现象NFA 只有四五个状态生成的 graph.txt 里 DFA 状态编号却有十几个而且多条边的起点终点完全重复。原因ε 闭包没有迭代到不动点只扫描了一层就返回导致闭包集合不完整或者闭包本身是对的但每次生成集合后没有和已有集合合并直接在状态表里新增了记录。解决闭包函数用队列反复扩展直到集合不再变化。DFA 状态去重必须用mapsetint, int让相同的集合映射到同一个 DFA 状态编号。跑完后肉眼检查一遍边列表如果出现两条一样的边说明去重逻辑失效重新检查 map 的 key 是不是每次都能正确比较集合内容。验证时拿一个已知的小正则比如a(a|b)*b手工推导 DFA 状态数再对比程序输出。5.5 递归下降一跑就死循环或者栈溢出现象输入合法的 test.sy 也会卡死或报 stack overflow程序无响应。原因文法存在左递归比如E - E T这种直接左递归递归下降函数进入parse_E后又调parse_E永远没有终止条件也可能是两个函数互相间接左递归A 调用 B、B 又调用 A。解决先消除文法中的左递归把E - E T | T改写成E - T E、E - T E | ε的右递归形式。写完递归下降函数列表后逐个检查每个函数开头是否有终止判断确保当前 token 不属于该函数的 FIRST 集时能正常返回。调试阶段先喂一个只有四五行的 test.sy不要一上来就跑完整程序这样栈溢出发生时能快速定位到具体是哪个函数。6. 把四个程序串成一条小前端流水线验证一个改动只花三十秒四个实验单独跑是四个程序但把它们串起来看其实就是一个小型编译前端词法分析把 test.sy 变成 token 序列递归下降或 LL(1) 分析器再拿这个 token 序列做语法检查。我在自己电脑上会给它们写一个简单的批处理省得每次都手动敲命令:: Windows cmd 下一次跑完词法分析和语法分析 cd /d D:\experiments\编译原理实验 词法分析.exe test.sy result.txt 递归下降分析法.exe result.txt parse_result.txt type parse_result.txt需要注意的是第二行的输入到底用 result.txt 还是直接用 test.sy取决于递归下降分析法.cpp 里是怎么读数据的。部分实现里它内部已经包含了词法扫描输入参数是源码路径如果这样第二行应该改成递归下降分析法.exe test.sy parse_result.txt不要画蛇添足把 token 文本再喂一遍。拿到代码后先看 main 函数的输入读取部分再决定批处理怎么写。我在验证改动时习惯用固定三连击在 test.sy 末尾加一行int x 0xFF;确认 result.txt 里数值是 255再加一个括号不匹配的表达式看语法分析器报错位置是不是正确行号最后把/* */注释和//注释同时放进去确认词法阶段没有吞代码。这三个用例覆盖了数字进制、注释、语法报错三个最容易出错的地方任何修改都能在三十秒内完成回归。这几次跑下来我最大的收获是每次拿到新实验代码先别急着改功能把自带的 test.sy 原样跑一遍把 result.txt 和 graph.txt 留下当基线再动手改代码。改完立刻用上面的三个用例回归确认基线结果没有被破坏。从那以后我不管换哪个工程都强制先跑通自带样例再动代码这套习惯帮我省掉了大量排查时间希望帮到你。本文还有配套的精品资源点击获取