简介：编译原理是计算机科学的核心课程，编译器前端由词法分析和语法分析构成。词法分析基于有限自动机将源代码转换为记号流，语法分析则依赖上下文无关文法验证程序结构。针对非确定性自动机，子集构造法利用ε闭包与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.txt

2.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转出来应该是十进制 42，0x1f应该是 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这一行输出的值是不是 42，0x1f是不是 31。如果这两个数不对，说明数字状态转移有问题，直接跳到第 5 章的 5.2。

这个环节涉及的文件不多，列一下方便对照：

想改源码重新编译的，在 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，它必须做传递闭包，不能只收集一轮直接可达的 ε 转移：

set<int> epsClosure(set<int> T) { set<int> result = T; // 集合自身也在闭包内 queue<int> 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 状态”队列，每个状态是一个 set：

map<set<int>, int> stateId; // NFA 状态集合 -> DFA 状态编号 queue<set<int>> unprocessed; set<int> startSet = epsClosure({nfaStart}); stateId[startSet] = 0; unprocessed.push(startSet); while (!unprocessed.empty()) { set<int> T = unprocessed.front(); unprocessed.pop(); for (char a : alphabet) { // 逐个字符计算转移 set<int> 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用map<set<int>, int>做去重。同一个 NFA 状态集合如果再次出现，必须映射到已有的 DFA 状态编号，否则会出现大量重复状态。每次从队列里取出集合 T，都要重新算一遍所有字符的 move 和闭包，工作量看起来不小，但实验给的 NFA 规模一般都控制在十几个状态以内，这个循环几乎瞬间完成。

3.2 输入 NFA 和输出 graph.txt，怎么验证结果对不对

实验里的子集构造法.cpp 通常支持两种输入方式：一种从文件读 NFA 状态表，另一种在命令行交互输入。常见做法是用文本定义状态表，格式大致如下：

我把上面这些字段手动填到一个文本里，然后运行子集构造法.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 下标 vector<Token> 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 集（简化伪代码） map<string, set<string>> 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) 的全称是 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 = 052，result.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 状态去重必须用map<set<int>, 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 留下当基线，再动手改代码。改完立刻用上面的三个用例回归，确认基线结果没有被破坏。从那以后我不管换哪个工程，都强制先跑通自带样例再动代码，这套习惯帮我省掉了大量排查时间，希望帮到你。

本文还有配套的精品资源，点击获取