简介：面向高校编译原理课程设计场景，这份资料包完整实现了NFA确定化、DFA最小化以及First、Follow集合计算等核心算法，并附带实验报告，适合需要完成课设、准备考试或理解自动机理论的本科生参考。包内共有160个文件，以C++源代码（.cpp/.h）、Visual Studio工程文件、可执行程序及Word报告为主，同时包含编译过程生成的中间文件、调试符号与工程缓存，压缩包整体约81.15MB，目录结构完整，便于直接打开运行和定位关键代码。已有266人学习下载。通过对照源码与报告，读者既能掌握从NFA到DFA转换的状态集构造思路、DFA状态合并原理，也能理解预测分析表构建所需的First/Follow求解流程；结合报告中的问题记录与解决方案，还可迁移到语法分析器或简易编译器的开发中，是理解编译器前端工作原理的实用参考。 这题目我太熟了，每年都有学生卡在“不知道这几个模块为什么凑在一起”上。NFA确定化、DFA最小化、First/Follow集合，表面看是三个孤立的算法题，实际上对应的是编译器前端两条最核心的链路：词法分析器的自动机构造，和语法分析器的预测分析表构造。如果你只是照着教材伪代码敲一遍交差，那这门课设就白做了——它真正想锻炼的，是你把离散数学里的集合操作、图论里的状态转换，翻译成能跑、能测、能演示的工程代码。这篇文章我会按照自己做课设和带项目的经验，把这三块从原理到实现再到报告写作，完整拆开讲一遍，适合正在做课设的本科生，也适合想把这几个基础模块彻底理清的初学者。
1. 这题目为什么值得认真做：把NFA确定化和First/Follow放进编译前端全貌
先解决一个最常见的困惑：为什么课设要把NFA和First/Follow放在一起？很多教材把这两块内容拆在不同章节，导致学生以为它们是并列的两个独立知识点，其实完全不是。
正则表达式到NFA再到DFA，这条链解决的是词法分析问题。源代码先要被切成token，也就是关键字、标识符、数字、运算符这些最小单位。而每种token都可以用一个正则表达式描述，比如C语言标识符就是[A-Za-z_][A-Za-z0-9_]*。计算机没法直接执行正则表达式，所以要把正则表达式转换成NFA，再确定化成DFA，最后用DFA去匹配输入的字符流。非确定性的NFA在匹配时需要回溯，而确定性的DFA每一步只有唯一路径，效率高得多。DFA最小化则是为了去掉冗余状态，减少内存和匹配时间。
First/Follow集合解决的是语法分析问题。拿到token流之后，语法分析器要判断这个token序列是否符合文法规则。自顶向下的LL(1)分析法需要用预测分析表来指导推导，而预测分析表的每个表项，正是根据产生式的First集合和Follow集合填出来的。如果没有First/Follow，自顶向下分析根本无从下手。
所以你看，NFA/DFA是词法分析阶段的自动机理论，First/Follow是语法分析阶段的集合运算理论，两者合在一起，恰好覆盖了编译前端从字符流到语法树的完整过程。课设把它们放在同一份题目里，就是要你走一遍编译器构造的完整链路，而不是孤立地背算法。
从代码实现的角度，这两部分还有一层隐形关联：它们的核心都在做集合运算。NFA确定化要做状态的ε-闭包集合，DFA最小化要做状态划分，First/Follow要做终结符集合的累积。如果你能用好std::set、std::vector、std::map这类容器，三个模块可以共用一套集合运算的基础代码，整体工程结构会非常干净。
我见过不少同学把这当成三个独立小作业，每个模块单独建一个文件，连数据结构都不统一。结果就是代码量看着很大，但模块之间完全没有协同，老师一问三不知。聪明的做法是先设计统一的状态表示方式，再写一套公共的集合工具函数，三个模块逐步搭上去。
2. NFA确定化：子集构造不是背算法，是理解“状态集合”这个抽象
2.1 用对数据结构，NFA就不难写
NFA的标准定义是一个五元组：状态集合Q、输入字母表Σ、转移函数δ、初始状态q0、终止状态集合F。但课设里一般不会让你直接处理完整的正则表达式到NFA转换，而是给你一个现成的NFA，让你做确定化。这就省掉了Thompson构造法那部分，核心就两个操作：ε-闭包和move。
我建议NFA用下面这种方式存储：
map<pair<int, char>, vector<int>>：从当前状态读入某个字符，可能转移到多个状态，所以值是状态数组。vector<vector<int>>：ε转换表，也就是读入空串时的转移关系，NFA的ε边单独存。
DFA的状态是NFA状态的一个子集，所以DFA状态编号可以直接用int，但每个DFA状态内部记录一个vector<int>，存它由哪些NFA状态组成。这样后面做最小化时才知道每个DFA状态的原始成分。
2.2 三步走：ε-闭包、move、子集构造
子集构造的核心逻辑可以用一个BFS描述，我把关键伪代码写出来：
1. 初始DFA状态 = ε-闭包({NFA初始状态}) 2. 把初始DFA状态加入队列 3. 循环直到队列为空： 取出一个DFA状态 S 对于字母表中的每个字符 c： 计算 T = ε-闭包(move(S, c)) 如果 T 非空： 如果 T 是新状态，加入队列 添加DFA转移：S --c--> T 4. 如果S包含NFA终止状态，标记S为DFA终止状态其中ε-闭包的求法就是从一个状态集合出发，把所有能通过ε边到达的状态全部加进来。这里有个容易写错的地方：闭包过程是传递的，所以必须用栈或队列做遍历，而不能只查一层。我见过有人用递归写ε-闭包，状态一多就栈溢出，改成显式栈就好了。
move(S, c)就简单了：遍历S中的每个状态，查转移函数表里有没有c这条边，把所有目标状态收集起来。
2.3 手推一个例子，你才知道代码在干嘛
用一个经典正则表达式a(b|c)*的NFA来做确定化演示。假设NFA有状态0到4，状态0通过a到状态1，状态1通过ε到状态2，状态2通过b到状态3，状态3通过ε回到状态2，状态2通过c到状态4，状态4也通过ε回到状态2，状态1和状态4都是终止状态。
这个NFA的DFA化过程如下表：
| DFT状态 | 包含的NFA状态 | 读入a | 读入b | 读入c |
|---|---|---|---|---|
| A | {0} | B | 死 | 死 |
| B | {1,2,4} | 死 | B | B |
你没看错，确定化之后可能只有两个有效状态。因为(b|c)*的部分通过ε闭包把1、2、4全部合并到同一个DFA状态里了，读入b或c之后通过ε边又回到同一个集合。这个例子的关键收获是：NFA里的循环在DFA里不一定产生新状态，因为ε闭包会把它们粘在一起。
2.4 死状态到底要不要画出来
确定化算法里，如果某个DFA状态对某个字符没有转移，有的教材会补一个死状态（死状态读任何字符都回到自己，非终止）。课设实现时我的建议是：可以补，但不用太过纠结。如果整个DFA存在死状态，最小化后它通常会被单独保留，但你画的DFA状态图会多一个永远到不了终止状态的挂起分支，老师看起来会觉得冗余。更优雅的做法是“隐式死状态”，也就是转移表里对应项留空，匹配时发现没有转移就直接拒绝。
我个人偏向隐式死状态，因为后续做DFA最小化时不用特殊处理死状态，逻辑更简单。如果题目要求必须画出完整DFA，再补上死状态也不迟。
3. DFA最小化：抱负划分不是难点，难在写对状态合并
3.1 抱负划分算法其实是一段“重复二分”逻辑
DFA最小化最经典的算法是Moore的划分细化算法，也常被叫成“抱负划分”。核心思想：先把状态分成两个大组——终止状态和非终止状态，然后反复检查，如果同一组内的两个状态对某个输入字符的转移落到了不同组，就把它们拆开。直到任何一组都无法再拆，组内的状态就是等价的，合并成同一个最小化状态。
伪代码是这个样子：
初始化：partition = {终止状态集合, 非终止状态集合} 循环： 对每个组group，尝试按照“转移后的组编号”再细分成子组 如果所有组都没变，跳出循环 最后，每组合并为一个状态说它“难在写对”，是因为实现细节很容易出错。我在课设验收时看过不少代码，算法思路都对，但状态合并后一团糟，典型的坑有三个。
3.2 合并状态的三个经典坑
第一个坑：合并时没有保留初态和终态信息。DFA的初始状态在合并后必须是初始状态所在组合并的新状态，终止状态同理。有人合并时只重建了转移表，没处理初始状态，导致最小化后的DFA没有初始状态，测试直接崩。解决办法就是合并时记录每个原状态属于哪个新组，然后用原初态对应的新组作为新的初始状态。
第二个坑：转移表重映射时用错了编号。合并后你得到一个组编号到新状态的映射，但有人直接在旧转移表上遍历，拿旧状态编号去填新表，结果新表里全是旧编号，状态集合对不上。正确做法是：先建一个旧状态 -> 新状态的映射数组，然后遍历旧转移表，把每个旧迁移通过映射改写到新状态。
第三个坑：划分循环条件写成了无限循环。如果你每次循环都新建一个partition数组，但忘记在循环结束时更新当前partition，或者更新了又用来判断“是否变化”，就会陷入死循环。我一般用一个changed布尔变量标记本轮是否发生过分裂，没分裂就终止，简单可靠。
3.3 最小化后别急着庆祝，先验证等价性
算法跑通后，我强烈建议做一步等价性验证：把最小化前后的DFA用同一个测试串集合去跑，要求接受状态一致。这在代码里实现起来非常简单，就是写一个simulate(dfa, input_string)函数，返回布尔值。用这个函数自动化验证，而不是肉眼比对状态图，能省掉大量调试时间。
这一步也有实际工程价值：后续做词法分析器时，你会反复修改正则表达式或字面量，如果每次都能自动验证最小化没有改变语言，改代码才敢放开手脚。
4. First/Follow集合：一套递归框架两处用，注意空串和左递归
4.1 First集合：终结符的“开头集合”
First集合的定义，简单说就是：从某个非终结符或产生式右侧，能推导出的所有终结符的集合，若还能推导出空串，就把ε也放进去。它的用途是填LL(1)预测分析表：当非终结符A面对输入符号a时，如果a在某个产生式A→α的First集合里，就用这个产生式去推导。
实现上最稳妥的方式是迭代法，不断循环直到所有集合不再变化：
初始化：所有非终结符的First集合为空 循环直到无变化： 对于每个产生式 A → X1 X2 ... Xn： 遍历右部每个符号Xi： 如果Xi是终结符：把Xi加入First(A)，break 如果Xi是非终结符： 把First(Xi)中除了ε之外的所有元素加入First(A) 如果ε不在First(Xi)：break 如果Xi是最后一个符号（前面全为ε）：把ε加入First(A)有个细节经常会漏：如果产生式右部是空串（ε产生式），那么直接把ε加入First(A)。另外，A → B这种单非终结符产生式，First(A)要完全包含First(B)，不能只拷非ε部分。这里也体现了为什么推荐迭代法——它把这种依赖关系通过多轮更新自然解决了。
4.2 Follow集合：非终结符后面的“跟随后续”
Follow集合要配合“开始符号”的概念：文法的开始符号S，我们规定Follow(S)里必须包含#（代表输入串结束符）。对每个产生式A → αBβ，B的Follow集合要加入First(β)中除ε以外的元素；如果β能推导出ε，还要把Follow(A)也并入Follow(B)。
这个“如果β能推出ε，还要继续传播Follow(A)”是新手最容易写漏的逻辑。我写过一版迭代实现，当时为了省事把ε判断写丢了，结果正确性差得离谱。后来学乖了，统一用迭代直到集合稳定的框架，把所有规则写成“每轮要执行的更新动作”，不容易漏判。
4.3 左递归文法必须先处理
这里有个前置条件经常被忽略：如果文法有左递归，或者有间接左递归，First/Follow集合的计算会出问题。因为左递归会让非终结符的First集合无限自引用。严格来说，First/Follow集合对任意上下文无关文法都存在且可以计算，但LL(1)要求文法必须无左递归、无公共左因子，否则后面构建预测分析表会出现冲突。
课设如果允许自定义文法输入，我建议做两个预处理：消除左递归，提取公共左因子。这两个算法本身不难，代码量也不大，但放到课设里会显得非常专业——因为很多同学的交上去就是个死板的计算器，只有你知道还要先检查文法可用性。这一项在验收时绝对能加分。
4.4 一个具体的计算示例
举个例子，文法：
E → T E' E' → + T E' | ε T → F T' T' → * F T' | ε F → ( E ) | id简化起见只看E和E'：
First(E) = First(T) = First(F) = { (, id }
Follow(E) = { #, ) }，因为E是开始符号所以有#，又因为产生式F → ( E )里E后面跟着)。Follow(E') = Follow(E) = { #, ) }，因为E'在产生式右部末尾，需要传播Follow(E)。
这个示例一定要放在代码里做测试，因为它的ε产生式和Follow传播正好覆盖了所有容易写错的规则。
5. 测试用例编排与隐性评分点
5.1 别拿教材例子跑一遍就交差
我当助教时发现，很多人的代码只跑通了一个教材例子，换个输入就崩。课设验收的核心环节其实就是“换个你不认识的数据你能不能跑”。所以测试这块我建议做一个独立测试文件，覆盖以下维度：
- NFA确定化：普通无ε边NFA、带ε边的NFA、多个终态的NFA、无终态的NFA、单个状态的NFA。
- DFA最小化：本来就是最小化的DFA、有等价状态的DFA、无终态的DFA。
- First/Follow：无ε产生式的文法、有多个ε产生式的文法、开始符号的Follow是否包含#。
每个测试都直接打印出中间结果，比如子集构造时每个DFA状态对应的NFA状态集合、划分过程中每轮的状态分组。这不仅是给自己调试看的，也是课设报告里最有说服力的截图素材。
5.2 输入文法时的边界校验
如果课设允许从文件读入NFA或文法，我还建议加两层校验：合法性校验和可分析性校验。合法性校验检查状态编号是否连续、转移目标是否存在、字母表是否有重复字符；可分析性校验检查文法是否有左递归、是否含有不可达非终结符。这些校验虽然不直接影响算法正确性，但能有效防止用户操作失误导致的崩溃，也是代码健壮性的体现。
举一个常见崩溃案例：NFA的字母表里出现了没在转移函数中使用的字符。如果代码在确定化时直接遍历字母表，倒不会崩，但会生成一堆死状态。如果代码用map按字符索引转移表，遇到未登记的字符会查不到key，直接异常。所以我在遍历字符表时会先检查字符是否存在于转移表中，不存在就跳过。
5.3 交互界面与演示方式
课设是给人验收的，不是纯后台跑批处理。我建议做一个简单的命令行交互，支持三种模式：模式一输入NFA确定化，模式二输入DFA最小化，模式三输入文法求First/Follow。三种模式都要能一步步打印中间过程，而不是只给最终结果。
别小看这个设计。老师验收时最怕的就是看不清学生的过程性思考。你如果只弹出一个最终状态表，老师还得自己心算验证；你如果把“DFA状态B = {NFA状态1,2,4}，读入b后得到{1,2,4}”这样的中间信息打出来，他一眼就知道你真懂了。
6. 课设报告的写法：让老师一眼看到工作量
最后说报告。很多学生报告写成了代码注释汇编，大段贴源码，毫无解释，这是最差的做法。课设报告的重点应该放在“问题建模”和“算法设计”上，代码只需要贴核心函数片段即可。
我推荐的报告结构是：问题描述与需求分析、整体设计方案、关键数据结构与模块划分、核心算法流程（用流程图或伪代码）、测试用例与运行结果截图、遇到的问题与解决方案、总结与收获。其中“遇到的问题与解决方案”这一节是最容易出彩的，因为它是真正个性化的工作记录。
比如你可以写“在DFA最小化阶段，最初合并等价状态时没有重定向初态，导致最小化后的DFA无法匹配任何输入串。通过增加旧状态到新状态的映射数组，并在合并完成后重新定位初态和终态解决”。这种内容比任何空话都有说服力。
流程图我建议用普通的Markdown表格或文本画，因为上交的文档通常是Word或PDF，可以用成熟的画图工具。报告中每个算法最好配上你的输入输出截图，标明日期。一份逻辑清晰、截图完整的报告，比一份排版华丽但内容空洞的报告拿到的分数高得多。
我在实际做课设指导时还有一个执念：报告里一定要写“这个东西在真实编译器中的作用”。哪怕一段话也好，比如解释NFA确定化后得到的DFA会怎么嵌入词法分析器，First/Follow算出来之后怎么填预测分析表。这段话能证明你学完这门课没白学，能把点连成线，老师看过之后对整份报告的评价会完全不同。
本文还有配套的精品资源，点击获取
