简介这份课程设计报告面向计算机科学与技术等专业学生聚焦编译原理中有限自动机空闭包ε-closureI的程序实现帮助读者理解并动手完成从NFA输入到状态子集构造的完整流程。报告以Java为实现语言内容覆盖需求分析、概要设计、详细设计与测试分析具体讲解数组、图与哈希表的数据组织前端数据传入、读空函数、读字母表函数及状态子集扩展等模块的调用关系并给出递归求空闭包、状态转换图布局等关键实现思路与测试用例。资源包共1个docx文件约177KB即课程设计报告正文含目录、各章节说明、参考文献与附录程序源代码结构完整便于对照学习。目前已有1287人学习下载适合正在做编译原理课程设计、需要参考NFA空闭包算法实现与报告写法的读者使用。1. 从一份课程设计报告说起为什么值得把 ε-closure 单独拎出来跑一遍很多人学编译原理词法分析、语法分析都能跟着教材走唯独到了 NFA 转 DFA 这一步ε-closure 这个概念看着简单真让自己写代码算一遍状态子集一多就开始犯迷糊。这份课程设计报告做的事很具体输入一个任意给定的 NFA程序自动求出它的所有状态子集对每个状态子集输出对应的空闭包 ε-closure(I)同时把 NFA 以状态转换图的形式画出来。它面向的是正在啃编译原理、需要把子集构造法真正落到代码里的开发者尤其是要交课程设计、又不想只抄伪代码的那批人。报告里把需求、概要设计、详细设计、测试用例、源码附录都摊开了读下来能看清一个学生项目是怎么把递归读空、读字母表、状态子集扩展这几块拼起来的也能看到作者踩过的坑——比如 X 和 Y 两个新增节点最后被固定连到一个状态上这种妥协在真实作业里太常见了。2. 项目定位与技术选型一个纯 Java 控制台程序怎么组织2.1 它到底解决什么问题先把问题边界说清楚。给定一个 NFA状态集合里包含普通状态、一个新增初态 X、一个新增终态 Y字母表是 a、b 这类有限符号转移函数以产生式字符串的形式给出比如(X,ε)→5、(5,a)→5。程序要做三件事第一从 X 出发读空得到第一个状态子集第二对这个子集反复读字母表、读空扩展出所有可达状态子集直到不再出现新子集第三对每个状态子集再求一次空闭包并打印。报告里还要求把 NFA 画成状态转换图节点大小位置要合理这一块属于可视化输出和核心算法是两条线。这个定位决定了它不是一个通用自动机库而是一个教学验证工具。输入靠文件或控制台输出靠System.out.println没有 GUI 框架也没有引入图论库。对新手来说这是好事依赖少、能跑对熟手来说它的价值在于把子集构造法的中间步骤全部打印出来方便对照教材检查每一步的集合变化。2.2 技术栈与数据结构选择报告里明确写了主要用数组、图结构和哈希表。落到 Java 代码上产生式用String[]存每个元素是一条形如(1,a)→3的字符串状态子集用SetString表示所有状态子集和它们的空闭包用MapSetString, SetString收口。这个选型很朴素但够用Set天然去重Map的 key 是集合本身正好对应“状态子集 → 空闭包”的映射关系。有一点要提前说明报告里的产生式解析是按下标硬取字符的strings[i].charAt(1)取当前状态charAt(3)取输入符号charAt(6)取目标状态。这意味着产生式字符串的格式必须严格固定多一个空格就会错位。这是这个项目最脆的地方后面避坑章节会专门讲。2.3 模块划分与调用关系按报告的概要设计模块分成前端数据传入、后台数据处理、对新增初态 X 读空、对状态子集读空、对状态子集读字母表、状态子集扩展这几块。调用关系是主流程先调 X 读空拿到初始子集然后循环里对每个子集先读字母表、再对读字母表的结果读空拼成新子集全部子集收集完之后再对每个子集逐个状态调读空函数汇总成该子集的空闭包。这里有个设计上的取舍值得注意读空函数被复用了两次一次是求初始子集一次是求每个子集的闭包。但两次传入的参数形态不一样前者传的是单个状态字符串后者是在循环里对子集内每个状态分别调用再合并。报告作者用静态字符串变量来累积递归结果这个做法能跑但埋了线程安全和重复调用的隐患二次开发时建议改成传可变集合。3. 核心算法拆解读空、读字母表、子集扩展三段式3.1 对新增初态 X 读空递归累积的写法与代价先看报告附录里第一个函数它的任务是从一个状态出发沿空弧一路走下去把所有能到达的状态拼成一个字符串返回。public static String RestltList(String string, String[] strings) { // string 是当前已累积的状态串strings 是全部产生式 for (int i 0; i strings.length; i) { // 取当前串最后一个字符看它是否能作为某条产生式的起点 if (String.valueOf(string.charAt(string.length() - 1)) .equals(String.valueOf(strings[i].charAt(1)))) { // 该产生式的输入符号是 ε说明是空弧 if (ε.equals(String.valueOf(strings[i].charAt(3)))) { string String.valueOf(strings[i].charAt(6)); // 把扩展后的串再递归进去继续找空弧 RestltList(string, strings); } } } return string; }逻辑说明函数每次只看当前累积串的最后一个字符找到以它为起点的空弧产生式把目标状态追加到串尾然后递归。因为空闭包的定义是“经过任意条空弧可达”递归正好对应“任意条”。参数string既是输入也是累积器strings是全局产生式表。这里有两个必须点破的细节。第一递归调用RestltList(string, strings)的返回值没有被接收靠的是string 在递归前已经改了局部变量而 Java 字符串不可变递归里改的是新串外层拿到的还是旧串的引用——严格说这个写法能“看起来对”是因为每次追加后递归内部又基于新串继续追加最终返回的是最内层那个最长的串但中间层的返回值被丢弃了。这种依赖调用顺序的写法很脆换个遍历顺序就可能漏状态。第二静态累积的替代方案是传一个SetString visited每次加入前判重既避免无限递归也避免重复状态撑大字符串。我一般会这么改public static void epsilonClosure(String state, String[] rules, SetString visited) { if (!visited.add(state)) return; // 已访问过直接返回防止空弧成环 for (String rule : rules) { // 用固定分隔符解析避免 charAt 下标错位 String[] parts rule.split([,)→]); if (parts[0].equals(state) parts[1].equals(ε)) { epsilonClosure(parts[2], rules, visited); } } }参数说明state是当前状态rules是产生式数组visited是外部传入的集合既做去重又做结果容器。这样改完空弧成环也不会栈溢出返回值也不再依赖字符串拼接顺序。3.2 读字母表只负责 a 弧不碰空弧第二个函数负责“读一个字母”报告里叫RestltListA它只处理输入符号等于指定字母的产生式。public static String RestltListA(String string, String s, String[] strings) { String resultA ; for (int i 0; i strings.length; i) { // 当前状态匹配产生式起点 if (string.equals(String.valueOf(strings[i].charAt(1)))) { // 输入符号匹配待读字母 if (s.equals(String.valueOf(strings[i].charAt(3)))) { resultA String.valueOf(strings[i].charAt(6)); } } } return resultA; }逻辑说明string是单个状态s是待读字母strings是产生式表。函数遍历所有产生式命中“起点等于当前状态且符号等于 s”的就把目标状态拼进结果。注意它一次只处理一个状态所以主流程里要对状态子集里的每个状态分别调用再把结果合并。参数怎么改如果要把这个函数用在子集上最直接的做法是外层套一个循环把每个状态的返回值并进一个Set。报告里主流程就是这么干的但用的是字符串拼接重复状态会重复出现后续读空时虽然不影响正确性但会让输出难看。建议把返回类型改成SetString天然去重。3.3 子集扩展读空、读 a、再读空真正把子集构造法串起来的是主循环。报告的描述是对每个已有状态子集对字母表里每个字母 a先对子集读 a再对读 a 的结果读空得到的新集合如果没出现过就加入待处理队列。这里的关键是“读 a 前后都要考虑空弧”因为 NFA 里可能存在(1,ε)→2、(2,a)→3这种路径只读 a 会漏掉 2 这个中间状态。// 伪代码式主循环体现三段式顺序 SetSetString allSubsets new HashSet(); QueueSetString queue new LinkedList(); SetString start new HashSet(); epsilonClosure(X, rules, start); // 第一步X 读空得初始子集 allSubsets.add(start); queue.add(start); while (!queue.isEmpty()) { SetString current queue.poll(); for (String letter : alphabet) { SetString moved new HashSet(); for (String st : current) { move(st, letter, rules, moved); // 读字母表 } SetString closure new HashSet(); for (String st : moved) { epsilonClosure(st, rules, closure); // 对读 a 结果再读空 } if (!closure.isEmpty() allSubsets.add(closure)) { queue.add(closure); // 新子集入队继续扩展 } } }逻辑说明move对应报告里的读字母表函数epsilonClosure对应读空函数。三段式的顺序不能反先读 a 再读空才能覆盖“经过 a 后走空弧”的情况而初始子集必须先读空才能覆盖“从 X 出发先走空弧再读 a”的情况。报告作者在总结里也提到一开始纠结怎么在一个函数里同时处理读 a 和读空后来拆成两个函数再组合逻辑就清楚了——这个拆分思路是整份报告里最有价值的工程经验。参数说明alphabet是字母表集合从产生式里扫一遍非 ε 符号就能得到allSubsets同时充当结果集和判重集add返回 false 说明子集已存在不再入队这就是终止条件。3.4 输出所有子集的空闭包最后一段是把allSubsets里每个子集再求一次闭包存进MapSetString, SetString并打印。MapSetString, SetString mapmax new HashMap(); for (SetString subset : allSubsets) { SetString closure new HashSet(); for (String st : subset) { epsilonClosure(st, rules, closure); // 对子集内每个状态读空并合并 } mapmax.put(subset, closure); } for (Map.EntrySetString, SetString e : mapmax.entrySet()) { System.out.println(e.getKey() e.getValue()); }逻辑说明这里对子集内每个状态分别求闭包再合并等价于对整个子集求闭包因为空闭包对集合并运算满足分配律。报告原代码里用setmax.add(string)先把状态本身加进去再调RestltList把读空结果拆成数组加进去思路一致只是字符串拆分那一步容易把多字符状态名拆错。4. 跑起来与验证输入格式、测试用例和状态图输出4.1 输入文件长什么样报告要求 NFA 保存在文件里产生式以字符串数组形式读入。按测试用例反推输入至少包含三部分状态列表、字母表、产生式列表。以报告里的例子一为例状态是X,1,2,3,4,5,6,Y字母表是a,b产生式是(X,ε)→5 (5,a)→5 (5,b)→5 (5,ε)→1 (1,a)→3 (1,b)→4 (3,a)→2 (4,b)→2 (2,ε)→6 (6,a)→6 (6,b)→6 (6,ε)→Y读文件时按行读每行一条产生式直接塞进String[]。注意产生式里不能有多余空格因为解析靠charAt(1)、charAt(3)、charAt(6)固定下标(X,ε)→5这个格式下下标刚好对上0 是(1 是X3 是ε6 是5。一旦写成(X, ε)→5下标全乱。4.2 三个测试用例分别验证什么报告给了三个例子覆盖的场景不一样。例子一状态多、空弧多用来验证子集扩展能不能收敛以及每个子集的闭包是否包含自身例子二只有0,1,X,Y四个状态产生式里(0,ε)→Y让 0 的空闭包含 Y用来验证终态通过空弧可达的情况例子三状态少但有空弧链(1,ε)→2、(2,b)→3、(3,a)→Y用来验证“读 a 前先读空”的必要性——如果只读 a 不读空从 1 出发读 a 会漏掉经 2 到 3 再到 Y 的路径。跑的时候建议先把输出重定向到文件再和手算结果逐行对。重点看三处初始子集是不是 X 的闭包、每个子集读 a 后的新子集有没有漏、最终闭包表里每个 key 是否都包含自己。4.3 状态转换图输出的现实做法报告要求以状态转换图方式输出 NFA节点大小位置合理、具有通用性。原文没有给图形代码只说了根据状态转移函数逐步构造。按这个场景下常见做法纯 Java 控制台项目一般走两条路一是用 Swing 的JPanel重写paintComponent按状态数算圆周坐标画圆和箭头二是输出 Graphviz 的 DOT 文本交给外部工具渲染。前者不用额外依赖适合课程设计演示后者代码量小但需要环境里有渲染工具。如果走 Swing核心是把状态列表均匀分布在一个圆上int n states.size(); int cx 300, cy 300, r 200; for (int i 0; i n; i) { double angle 2 * Math.PI * i / n; int x (int) (cx r * Math.cos(angle)); int y (int) (cy r * Math.sin(angle)); g.drawOval(x - 20, y - 20, 40, 40); // 节点半径 20 g.drawString(states.get(i), x - 5, y 5); }参数说明n是状态数r是布局半径节点多时把r调大或改成椭圆布局。箭头部分按产生式逐条画线自环用drawArc普通边用drawLine加箭头三角。这块和核心算法解耦改布局不影响闭包计算。5. 避坑与排查这份实现里最容易翻车的五个点5.1 产生式下标解析错位现象程序跑出来状态子集为空或者读空结果里混进了)、→这类字符。原因产生式字符串格式和charAt下标不匹配比如状态名超过一位、符号前后多了空格。解决把解析从固定下标改成按分隔符切分rule.split([,)→])之后取第 0、1、2 段状态名多长都不怕。5.2 空弧成环导致栈溢出现象输入里出现(1,ε)→2、(2,ε)→1这种环程序抛StackOverflowError。原因递归读空没有访问标记环上无限递归。解决读空函数加SetString visited进入时先add已存在就返回。报告原实现靠字符串累积环上会一直追加同样会炸。5.3 静态变量累积结果串味现象连续调用两次读空第二次结果里带着第一次的状态。原因报告用静态字符串接收递归结果静态变量跨调用共享。解决去掉静态累积改成每次调用新建Set作为参数传入或者把函数改成返回Set的纯函数。5.4 只读 a 不读空漏状态现象某个子集读 a 后得到的目标状态和手算结果对不上少了几个。原因读字母表函数只处理(s,a)→t没处理t还能走空弧到u的情况。解决严格按“读空 → 读 a → 读空”三段式读 a 的结果必须再过一遍闭包函数报告里DuKong就是干这个的。5.5 子集判重失效导致死循环现象程序一直跑不完输出里反复出现相同子集。原因用字符串表示子集12和21被当成不同集合或者Set里混入了空串。解决子集统一用SetString表示入队前用allSubsets.add的布尔返回值判重空集直接跳过不入队。6. 二次开发把课程设计改成能复用的 NFA 工具如果要把这份代码往实用方向推我建议先动三处。第一把产生式解析抽成独立方法返回MapString, MapString, SetString这种“状态 → 符号 → 目标集合”的三层结构后面读空、读 a 都查这张表不再每次遍历字符串数组状态一多性能差距很明显。第二把读空和读 a 改成纯函数输入集合、输出集合不碰静态变量这样单元测试好写也能直接拿 JUnit 对报告里的三个例子做断言。第三状态图输出和算法解耦算法只产出子集和闭包表画图模块单独读这张表想换 DOT 还是 Swing 都不影响核心逻辑。验证方法上我习惯用“手算小例子 对拍”两步走。先拿例子二这种四状态的小 NFA 手算子集和闭包写成断言再随机生成一批小规模 NFA用改后的实现和一份暴力枚举实现对比输出。暴力枚举的思路很简单对每个状态子集枚举所有长度不超过状态数的路径能走到的状态全收进闭包虽然慢但不容易错拿来当基准正合适。还有一个具体技巧把MapSetString, SetString的 key 换成排序后的字符串比如1,2,3打印和比对都直观也避免Set的hashCode顺序问题导致输出顺序飘。改的时候注意保留原始产生式表别在解析阶段就把 ε 弧丢掉否则后面求闭包没数据可用。这份报告最让我有共鸣的地方是作者在总结里写“把一个难实现的功能拆成几个模块来写就会发现好理解很多”。我早期写子集构造也犯过把读 a 和读空揉在一个函数里的毛病调了一下午才发现是顺序问题。从那以后我每次碰自动机相关的代码都强制先把“单步转移”和“闭包”拆成两个函数再在调用处组合宁可多写一个函数也不省这一步。希望这份拆解能帮到你把这份课程设计真正跑通、改顺。本文还有配套的精品资源点击获取 
长河君 · 2026/10/31 14:59:17 · 阅读 1.2k 编译原理实战：NFA转DFA中ε-closure算法详解与Java实现
简介这份课程设计报告面向计算机科学与技术等专业学生聚焦编译原理中有限自动机空闭包ε-closureI的程序实现帮助读者理解并动手完成从NFA输入到状态子集构造的完整流程。报告以Java为实现语言内容覆盖需求分析、概要设计、详细设计与测试分析具体讲解数组、图与哈希表的数据组织前端数据传入、读空函数、读字母表函数及状态子集扩展等模块的调用关系并给出递归求空闭包、状态转换图布局等关键实现思路与测试用例。资源包共1个docx文件约177KB即课程设计报告正文含目录、各章节说明、参考文献与附录程序源代码结构完整便于对照学习。目前已有1287人学习下载适合正在做编译原理课程设计、需要参考NFA空闭包算法实现与报告写法的读者使用。1. 从一份课程设计报告说起为什么值得把 ε-closure 单独拎出来跑一遍很多人学编译原理词法分析、语法分析都能跟着教材走唯独到了 NFA 转 DFA 这一步ε-closure 这个概念看着简单真让自己写代码算一遍状态子集一多就开始犯迷糊。这份课程设计报告做的事很具体输入一个任意给定的 NFA程序自动求出它的所有状态子集对每个状态子集输出对应的空闭包 ε-closure(I)同时把 NFA 以状态转换图的形式画出来。它面向的是正在啃编译原理、需要把子集构造法真正落到代码里的开发者尤其是要交课程设计、又不想只抄伪代码的那批人。报告里把需求、概要设计、详细设计、测试用例、源码附录都摊开了读下来能看清一个学生项目是怎么把递归读空、读字母表、状态子集扩展这几块拼起来的也能看到作者踩过的坑——比如 X 和 Y 两个新增节点最后被固定连到一个状态上这种妥协在真实作业里太常见了。2. 项目定位与技术选型一个纯 Java 控制台程序怎么组织2.1 它到底解决什么问题先把问题边界说清楚。给定一个 NFA状态集合里包含普通状态、一个新增初态 X、一个新增终态 Y字母表是 a、b 这类有限符号转移函数以产生式字符串的形式给出比如(X,ε)→5、(5,a)→5。程序要做三件事第一从 X 出发读空得到第一个状态子集第二对这个子集反复读字母表、读空扩展出所有可达状态子集直到不再出现新子集第三对每个状态子集再求一次空闭包并打印。报告里还要求把 NFA 画成状态转换图节点大小位置要合理这一块属于可视化输出和核心算法是两条线。这个定位决定了它不是一个通用自动机库而是一个教学验证工具。输入靠文件或控制台输出靠System.out.println没有 GUI 框架也没有引入图论库。对新手来说这是好事依赖少、能跑对熟手来说它的价值在于把子集构造法的中间步骤全部打印出来方便对照教材检查每一步的集合变化。2.2 技术栈与数据结构选择报告里明确写了主要用数组、图结构和哈希表。落到 Java 代码上产生式用String[]存每个元素是一条形如(1,a)→3的字符串状态子集用SetString表示所有状态子集和它们的空闭包用MapSetString, SetString收口。这个选型很朴素但够用Set天然去重Map的 key 是集合本身正好对应“状态子集 → 空闭包”的映射关系。有一点要提前说明报告里的产生式解析是按下标硬取字符的strings[i].charAt(1)取当前状态charAt(3)取输入符号charAt(6)取目标状态。这意味着产生式字符串的格式必须严格固定多一个空格就会错位。这是这个项目最脆的地方后面避坑章节会专门讲。2.3 模块划分与调用关系按报告的概要设计模块分成前端数据传入、后台数据处理、对新增初态 X 读空、对状态子集读空、对状态子集读字母表、状态子集扩展这几块。调用关系是主流程先调 X 读空拿到初始子集然后循环里对每个子集先读字母表、再对读字母表的结果读空拼成新子集全部子集收集完之后再对每个子集逐个状态调读空函数汇总成该子集的空闭包。这里有个设计上的取舍值得注意读空函数被复用了两次一次是求初始子集一次是求每个子集的闭包。但两次传入的参数形态不一样前者传的是单个状态字符串后者是在循环里对子集内每个状态分别调用再合并。报告作者用静态字符串变量来累积递归结果这个做法能跑但埋了线程安全和重复调用的隐患二次开发时建议改成传可变集合。3. 核心算法拆解读空、读字母表、子集扩展三段式3.1 对新增初态 X 读空递归累积的写法与代价先看报告附录里第一个函数它的任务是从一个状态出发沿空弧一路走下去把所有能到达的状态拼成一个字符串返回。public static String RestltList(String string, String[] strings) { // string 是当前已累积的状态串strings 是全部产生式 for (int i 0; i strings.length; i) { // 取当前串最后一个字符看它是否能作为某条产生式的起点 if (String.valueOf(string.charAt(string.length() - 1)) .equals(String.valueOf(strings[i].charAt(1)))) { // 该产生式的输入符号是 ε说明是空弧 if (ε.equals(String.valueOf(strings[i].charAt(3)))) { string String.valueOf(strings[i].charAt(6)); // 把扩展后的串再递归进去继续找空弧 RestltList(string, strings); } } } return string; }逻辑说明函数每次只看当前累积串的最后一个字符找到以它为起点的空弧产生式把目标状态追加到串尾然后递归。因为空闭包的定义是“经过任意条空弧可达”递归正好对应“任意条”。参数string既是输入也是累积器strings是全局产生式表。这里有两个必须点破的细节。第一递归调用RestltList(string, strings)的返回值没有被接收靠的是string 在递归前已经改了局部变量而 Java 字符串不可变递归里改的是新串外层拿到的还是旧串的引用——严格说这个写法能“看起来对”是因为每次追加后递归内部又基于新串继续追加最终返回的是最内层那个最长的串但中间层的返回值被丢弃了。这种依赖调用顺序的写法很脆换个遍历顺序就可能漏状态。第二静态累积的替代方案是传一个SetString visited每次加入前判重既避免无限递归也避免重复状态撑大字符串。我一般会这么改public static void epsilonClosure(String state, String[] rules, SetString visited) { if (!visited.add(state)) return; // 已访问过直接返回防止空弧成环 for (String rule : rules) { // 用固定分隔符解析避免 charAt 下标错位 String[] parts rule.split([,)→]); if (parts[0].equals(state) parts[1].equals(ε)) { epsilonClosure(parts[2], rules, visited); } } }参数说明state是当前状态rules是产生式数组visited是外部传入的集合既做去重又做结果容器。这样改完空弧成环也不会栈溢出返回值也不再依赖字符串拼接顺序。3.2 读字母表只负责 a 弧不碰空弧第二个函数负责“读一个字母”报告里叫RestltListA它只处理输入符号等于指定字母的产生式。public static String RestltListA(String string, String s, String[] strings) { String resultA ; for (int i 0; i strings.length; i) { // 当前状态匹配产生式起点 if (string.equals(String.valueOf(strings[i].charAt(1)))) { // 输入符号匹配待读字母 if (s.equals(String.valueOf(strings[i].charAt(3)))) { resultA String.valueOf(strings[i].charAt(6)); } } } return resultA; }逻辑说明string是单个状态s是待读字母strings是产生式表。函数遍历所有产生式命中“起点等于当前状态且符号等于 s”的就把目标状态拼进结果。注意它一次只处理一个状态所以主流程里要对状态子集里的每个状态分别调用再把结果合并。参数怎么改如果要把这个函数用在子集上最直接的做法是外层套一个循环把每个状态的返回值并进一个Set。报告里主流程就是这么干的但用的是字符串拼接重复状态会重复出现后续读空时虽然不影响正确性但会让输出难看。建议把返回类型改成SetString天然去重。3.3 子集扩展读空、读 a、再读空真正把子集构造法串起来的是主循环。报告的描述是对每个已有状态子集对字母表里每个字母 a先对子集读 a再对读 a 的结果读空得到的新集合如果没出现过就加入待处理队列。这里的关键是“读 a 前后都要考虑空弧”因为 NFA 里可能存在(1,ε)→2、(2,a)→3这种路径只读 a 会漏掉 2 这个中间状态。// 伪代码式主循环体现三段式顺序 SetSetString allSubsets new HashSet(); QueueSetString queue new LinkedList(); SetString start new HashSet(); epsilonClosure(X, rules, start); // 第一步X 读空得初始子集 allSubsets.add(start); queue.add(start); while (!queue.isEmpty()) { SetString current queue.poll(); for (String letter : alphabet) { SetString moved new HashSet(); for (String st : current) { move(st, letter, rules, moved); // 读字母表 } SetString closure new HashSet(); for (String st : moved) { epsilonClosure(st, rules, closure); // 对读 a 结果再读空 } if (!closure.isEmpty() allSubsets.add(closure)) { queue.add(closure); // 新子集入队继续扩展 } } }逻辑说明move对应报告里的读字母表函数epsilonClosure对应读空函数。三段式的顺序不能反先读 a 再读空才能覆盖“经过 a 后走空弧”的情况而初始子集必须先读空才能覆盖“从 X 出发先走空弧再读 a”的情况。报告作者在总结里也提到一开始纠结怎么在一个函数里同时处理读 a 和读空后来拆成两个函数再组合逻辑就清楚了——这个拆分思路是整份报告里最有价值的工程经验。参数说明alphabet是字母表集合从产生式里扫一遍非 ε 符号就能得到allSubsets同时充当结果集和判重集add返回 false 说明子集已存在不再入队这就是终止条件。3.4 输出所有子集的空闭包最后一段是把allSubsets里每个子集再求一次闭包存进MapSetString, SetString并打印。MapSetString, SetString mapmax new HashMap(); for (SetString subset : allSubsets) { SetString closure new HashSet(); for (String st : subset) { epsilonClosure(st, rules, closure); // 对子集内每个状态读空并合并 } mapmax.put(subset, closure); } for (Map.EntrySetString, SetString e : mapmax.entrySet()) { System.out.println(e.getKey() e.getValue()); }逻辑说明这里对子集内每个状态分别求闭包再合并等价于对整个子集求闭包因为空闭包对集合并运算满足分配律。报告原代码里用setmax.add(string)先把状态本身加进去再调RestltList把读空结果拆成数组加进去思路一致只是字符串拆分那一步容易把多字符状态名拆错。4. 跑起来与验证输入格式、测试用例和状态图输出4.1 输入文件长什么样报告要求 NFA 保存在文件里产生式以字符串数组形式读入。按测试用例反推输入至少包含三部分状态列表、字母表、产生式列表。以报告里的例子一为例状态是X,1,2,3,4,5,6,Y字母表是a,b产生式是(X,ε)→5 (5,a)→5 (5,b)→5 (5,ε)→1 (1,a)→3 (1,b)→4 (3,a)→2 (4,b)→2 (2,ε)→6 (6,a)→6 (6,b)→6 (6,ε)→Y读文件时按行读每行一条产生式直接塞进String[]。注意产生式里不能有多余空格因为解析靠charAt(1)、charAt(3)、charAt(6)固定下标(X,ε)→5这个格式下下标刚好对上0 是(1 是X3 是ε6 是5。一旦写成(X, ε)→5下标全乱。4.2 三个测试用例分别验证什么报告给了三个例子覆盖的场景不一样。例子一状态多、空弧多用来验证子集扩展能不能收敛以及每个子集的闭包是否包含自身例子二只有0,1,X,Y四个状态产生式里(0,ε)→Y让 0 的空闭包含 Y用来验证终态通过空弧可达的情况例子三状态少但有空弧链(1,ε)→2、(2,b)→3、(3,a)→Y用来验证“读 a 前先读空”的必要性——如果只读 a 不读空从 1 出发读 a 会漏掉经 2 到 3 再到 Y 的路径。跑的时候建议先把输出重定向到文件再和手算结果逐行对。重点看三处初始子集是不是 X 的闭包、每个子集读 a 后的新子集有没有漏、最终闭包表里每个 key 是否都包含自己。4.3 状态转换图输出的现实做法报告要求以状态转换图方式输出 NFA节点大小位置合理、具有通用性。原文没有给图形代码只说了根据状态转移函数逐步构造。按这个场景下常见做法纯 Java 控制台项目一般走两条路一是用 Swing 的JPanel重写paintComponent按状态数算圆周坐标画圆和箭头二是输出 Graphviz 的 DOT 文本交给外部工具渲染。前者不用额外依赖适合课程设计演示后者代码量小但需要环境里有渲染工具。如果走 Swing核心是把状态列表均匀分布在一个圆上int n states.size(); int cx 300, cy 300, r 200; for (int i 0; i n; i) { double angle 2 * Math.PI * i / n; int x (int) (cx r * Math.cos(angle)); int y (int) (cy r * Math.sin(angle)); g.drawOval(x - 20, y - 20, 40, 40); // 节点半径 20 g.drawString(states.get(i), x - 5, y 5); }参数说明n是状态数r是布局半径节点多时把r调大或改成椭圆布局。箭头部分按产生式逐条画线自环用drawArc普通边用drawLine加箭头三角。这块和核心算法解耦改布局不影响闭包计算。5. 避坑与排查这份实现里最容易翻车的五个点5.1 产生式下标解析错位现象程序跑出来状态子集为空或者读空结果里混进了)、→这类字符。原因产生式字符串格式和charAt下标不匹配比如状态名超过一位、符号前后多了空格。解决把解析从固定下标改成按分隔符切分rule.split([,)→])之后取第 0、1、2 段状态名多长都不怕。5.2 空弧成环导致栈溢出现象输入里出现(1,ε)→2、(2,ε)→1这种环程序抛StackOverflowError。原因递归读空没有访问标记环上无限递归。解决读空函数加SetString visited进入时先add已存在就返回。报告原实现靠字符串累积环上会一直追加同样会炸。5.3 静态变量累积结果串味现象连续调用两次读空第二次结果里带着第一次的状态。原因报告用静态字符串接收递归结果静态变量跨调用共享。解决去掉静态累积改成每次调用新建Set作为参数传入或者把函数改成返回Set的纯函数。5.4 只读 a 不读空漏状态现象某个子集读 a 后得到的目标状态和手算结果对不上少了几个。原因读字母表函数只处理(s,a)→t没处理t还能走空弧到u的情况。解决严格按“读空 → 读 a → 读空”三段式读 a 的结果必须再过一遍闭包函数报告里DuKong就是干这个的。5.5 子集判重失效导致死循环现象程序一直跑不完输出里反复出现相同子集。原因用字符串表示子集12和21被当成不同集合或者Set里混入了空串。解决子集统一用SetString表示入队前用allSubsets.add的布尔返回值判重空集直接跳过不入队。6. 二次开发把课程设计改成能复用的 NFA 工具如果要把这份代码往实用方向推我建议先动三处。第一把产生式解析抽成独立方法返回MapString, MapString, SetString这种“状态 → 符号 → 目标集合”的三层结构后面读空、读 a 都查这张表不再每次遍历字符串数组状态一多性能差距很明显。第二把读空和读 a 改成纯函数输入集合、输出集合不碰静态变量这样单元测试好写也能直接拿 JUnit 对报告里的三个例子做断言。第三状态图输出和算法解耦算法只产出子集和闭包表画图模块单独读这张表想换 DOT 还是 Swing 都不影响核心逻辑。验证方法上我习惯用“手算小例子 对拍”两步走。先拿例子二这种四状态的小 NFA 手算子集和闭包写成断言再随机生成一批小规模 NFA用改后的实现和一份暴力枚举实现对比输出。暴力枚举的思路很简单对每个状态子集枚举所有长度不超过状态数的路径能走到的状态全收进闭包虽然慢但不容易错拿来当基准正合适。还有一个具体技巧把MapSetString, SetString的 key 换成排序后的字符串比如1,2,3打印和比对都直观也避免Set的hashCode顺序问题导致输出顺序飘。改的时候注意保留原始产生式表别在解析阶段就把 ε 弧丢掉否则后面求闭包没数据可用。这份报告最让我有共鸣的地方是作者在总结里写“把一个难实现的功能拆成几个模块来写就会发现好理解很多”。我早期写子集构造也犯过把读 a 和读空揉在一个函数里的毛病调了一下午才发现是顺序问题。从那以后我每次碰自动机相关的代码都强制先把“单步转移”和“闭包”拆成两个函数再在调用处组合宁可多写一个函数也不省这一步。希望这份拆解能帮到你把这份课程设计真正跑通、改顺。本文还有配套的精品资源点击获取