Java实现ε-closure：NFA子集构造与状态转换图课程设计

简介面向编译原理课程设计场景这份报告围绕有限自动机空闭包ε-closureI的Java程序实现展开适合正在完成NFA相关实验、需要参考报告结构与算法思路的高校学生。内容覆盖NFA输入与存储、状态子集生成、空闭包递归计算、读空与读字母表处理以及状态转换图的节点布局和通用性设计并包含需求分析、概要设计、详细设计、测试与分析、用户使用说明、总结和附录源代码可作为课程设计撰写与程序实现的对照材料。资源包共1个docx文件约177KB篇幅紧凑便于直接查阅关键章节与代码片段。已有1287人学习适合希望理解ε-closure概念、梳理递归读空逻辑并借鉴测试用例设计的读者。1. 状态集一大就数不清ε-closure 单独做成程序的理由手推一个十几个状态的 NFA求任意子集 I 的 ε-closure(I)多数人不是不懂定义是眼睛跟不上——第一层空弧数对了第二层就漏状态。这份《编译原理 ε-closureI的程序实现》课程设计报告干的就是把这件事交给机器读入任意 NFA输出所有状态子集的空闭包输出指定子集 I 的闭包再把自动机按状态转换图画出来节点位置还得排得能看。它是 Java 写的代码量不大但把子集构造法subset construction里最容易写乱的三段逻辑拆得很清楚。适合三类人正在做编译原理课设、需要一个能跑能改的参考实现的学生想把 NFA→DFA 那套算法落到业务代码里的开发者以及想找一个体量小到能一晚上读完的自动机工具雏形的人。往下读能拿到结构、核心函数和改造入口。2. 架构与数据结构产生式字符串、状态集 Map 与三函数分工整套程序的行数放在工程里算很小但它对「数据怎么存」这件事做了一个很朴素的选择所有状态转移都用字符串存所有状态集合都用 Java 集合类存算法层只负责在这两者之间来回转换。读懂这个选择后面的代码几乎不用逐行看也能猜出结构。2.1 三层分工输入层、计算层、展示层按报告里的模块划分程序被切成三块。第一块是前端数据传入负责把用户敲进去的状态表、字母表和状态转移函数收进来落成文件保存这样同一台 NFA 不用每次重敲。第二块是后台数据处理与分析也是真正吃算法的地方里面又分了五件事对新引入初态节点 X 的读空、对状态子集读空、对状态子集读字母表、由当前子集推出后续子集、以及把所有子集拼成结果集。第三块是状态转换图的绘制按状态转移函数把节点和边画出来。这三层的边界在报告里没写成接口而是靠函数调用串起来的计算层拿输入层的字符串数组展示层拿计算层整理好的转移关系。中间没有 DTO也没有配置文件属于典型的课程设计写法——好处是链路短、调试时一眼能看到底代价是耦合重后面第 6 章会讲怎么拆。有一处设计值得单独提一句。报告里明确写了为了求状态子集先给 NFA 补一个新的初态 X 和新的终态 YX 连一条 ε 弧到原初态原终态连一条 ε 弧到 Y。但作者也老实交代X 到「任意状态节点」、任意终态节点到 Y 这种通用连法他们没做出来最后是固定连到某一个节点并把这条边直接写进状态转移函数里。这不是偷懒是把一个通用性问题降级成特例问题用一条手写产生式换掉了动态建边。教学项目里这么干完全能接受工程里就得留个心眼了因为换一台 NFA 就得改那两行。2.2 用字符串存产生式一个便宜但有代价的选择状态转移函数在程序里长这样(5,a)→5、(X,ε)→5、(2,ε)→6。整个转移表就是一个String[]每个元素是一条产生式。解析全靠charAt取固定下标因为格式是人为约定死的。下标0123456字符(起点状态,字母或ε)→终点状态// 每条产生式固定成 (起点,字母)→终点 的文本形式 // 解析约定charAt(1)起点charAt(3)字母charAt(6)终点 String[] functionStrings { (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 };这段数组是例子一的完整转移表一行一条边ε统一用希腊字母表示空弧。逻辑上它等价于一个三元组列表(from, symbol, to)只是把三元组压成了字符串。好处很直接文件读写零成本一行一条人眼能核对用户在界面上填表也就是拼字符串。代价在参数说明里已经埋着了——起点和终点被限制成单字符charAt(1)和charAt(6)这两个写死的下标一旦状态编号变成10、11整张表就全错位。这是后面避坑章节第一条要展开的坑。2.3 状态集用什么装Set 做元素、Map 做索引计算过程中有两类东西要存单个状态字符串比如5和状态子集一堆状态。子集用的是SetString这一点很关键因为 ε-closure 的结果天然去重用List就得自己判重用Set直接add就行。所有已经生成的状态子集则塞进一个Map键是子集本身值是它的闭包或者其他附属信息。// 状态子集 - 该子集的 ε-closure最终输出用 MapSetString, SetString mapmax new HashMap(); // 子集构造的工作表已经生成、但还没用字母表扩展过的状态子集 MapSetString, SetString allset2 new HashMap();mapmax是结果容器键是状态子集值是它的空闭包最后遍历打印就是「状态子集 状态子集空闭包」这张对照表。allset2类似工作队列存的是子集构造过程中已经产生、等待用字母表逐个字母去扩展的那些集合。用Set当Map的键有个隐含前提HashSet的equals和hashCode是按元素内容算的所以{1,2}和{2,1}会被认为是同一个键这正是我们想要的去重语义。但反过来HashSet的迭代顺序不稳定导致同一份输入跑两次控制台打印的子集顺序可能不一样。功能上没错观感上像 bug这个在第 5 章会单独说。2.4 三个核心函数的职责边界报告里作者自己总结过一句话大意是一开始想用一个函数把「读 a 又要考虑前后读空」全做完纠结了很久没写出来后来改成拆成「只读字母」和「只读空」两个函数求子集的时候按「读空 → 读 a → 再读空」的顺序拼起来逻辑一下就顺了。这个拆分是整份设计里最值钱的部分。三个函数的边界是这样的RestltList(string, strings)从某个状态出发沿 ε 弧一路走下去把能到达的状态全收进来。传进去的是一个状态串出来的是闭包串。RestltListA(string, s, strings)只处理字母s找出从状态string经一条s弧能到的状态完全不管 ε。DuKong(result, strings)给一个已经由字母扩展出来的状态集合再沿 ε 走一遍补齐闭包。对应到形式语言里的符号就是第一个是 closure第二个是 move 的单状态版本第三个是 move 之后再 closure。主循环拿这三个拼出完整的ε-closure(move(T, a))。调用关系上求状态子集的主函数调RestltList拿初始子集然后对每个子集、每个字母调RestltListA再对结果调DuKong新得到的子集如果没出现过就进工作表直到工作表空了为止。这套结构跟教科书上的子集构造伪代码是一一对应的只是伪代码里的ε-closure(move(T,a))被拆成了三次函数调用。3. 核心算法拆解读空、读字母、子集扩展的完整调用链结构看完接下来是真正要抄作业的部分。这一章按调用顺序走一遍从引入 X 开始到所有子集生成完为止每段代码后面都说清楚它吃什么参数、吐什么结果、哪里容易出错。3.1 补 X 和 Y把「任意初态集」压成单点问题NFA 的原初态可能不止一个直接对集合求闭包会让入口逻辑变复杂。常见做法是补一个新初态 X用 ε 弧连到所有原初态再补一个新终态 Y让所有原终态用 ε 弧连到 Y。这样整个自动机就有了唯一的入口和出口求闭包时只要从 X 出发就行。报告里的实现做了简化X 只连到某一个固定节点Y 也只从某一个固定节点接进来而且这两条边是直接手写进转移表的不是跑图算法算出来的。所以你会看到转移表里有(X,ε)→5和(6,ε)→Y这样两行。对单次演示够用换 NFA 就得手动改这两行。// 补边之后的转移表开头和结尾X、Y 作为唯一入口出口 // (X,ε)→5 表示新初态 X 空跳到原初态 5 // (6,ε)→Y 表示原终态 6 空跳到新终态 Y String[] functionStrings { (X,ε)→5, // ... 原有转移 (6,ε)→Y };参数说明X和Y只是两个普通字符串程序里没有任何特殊判断它们和其他状态一样参与闭包计算。这么做的前提是转移表里已经写好了对应的 ε 边少了这两行初始子集就只剩{X}后面所有扩展都是空的输出会整齐地全是空集第一次跑的人很容易以为算法写错了其实是数据没喂对。3.2 读空函数递归 静态变量累积原版代码是长这样的public static String RestltList(String string, String[] strings) { for (int i 0; i strings.length; i) { // string 的最后一个字符就是当前所在的状态 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是一个状态串比如初始调用传Xstrings是整张转移表。循环扫每条产生式取出它的起点charAt(1)跟string的最后一个字符比较——也就是说函数永远只从「当前串的尾巴」继续往下走。命中之后再看这条边的字母是不是ε是的话就把终点charAt(6)拼到串尾然后递归再走一轮。返回的是累积后的整串。举例传X进去扫到(X,ε)→5拼成X5递归这一轮尾巴是5扫到(5,ε)→1拼成X51递归尾巴是1没有从1出发的 ε 边递归返回。最终得到X51也就是{X,5,1}。递归的终止条件其实是隐式的没有新的 ε 边可走时循环里什么都不做直接返回原串。这依赖一个前提——ε 图里不能有环。一旦存在(1,ε)→2、(2,ε)→1这种互相空跳的结构串会无限增长递归层级也一路加深最后StackOverflowError。第 5 章会把这条列成独立坑位。还有一个必须点出来的问题RestltList(string, strings);这一句的返回值没有被接住。Java 里字符串是不可变的string ...修改的是当前方法栈里的局部变量递归调用内部再拼的东西只在递归那一层有效回到外层就丢了。所以严格按这段代码执行走两层以上 ε 弧时结果会缺状态。报告里提到用了静态变量来接收每次递归的结果思路是对的但落到这份代码上静态变量和局部拼接混在一起反而更容易乱。下面是我一般会改成的样子用显式的栈做传递闭包环和深链都不会炸public static SetString epsilonClosure(SetString states, String[] productions) { SetString closure new LinkedHashSet(states); // 先把自己放进去 DequeString stack new ArrayDeque(states); // 待展开的状态 while (!stack.isEmpty()) { String cur stack.pop(); for (String p : productions) { String from p.substring(1, p.indexOf(,)); // 起点 String symbol p.substring(p.indexOf(,) 1, p.indexOf())); // 字母 String to p.substring(p.indexOf(→) 1); // 终点 if (!ε.equals(symbol)) continue; // 只走空弧 if (from.equals(cur) closure.add(to)) { // add 返回 true 说明是新状态 stack.push(to); } } } return closure; }参数说明states是待求闭包的起始集可以是单个状态包成的集合也可以是 move 之后的结果集productions还是那张字符串转移表。关键在closure.add(to)的返回值——LinkedHashSet在元素已存在时返回false正好用来判断「要不要继续展开」这样即使 ε 图有环每个状态也只会入栈一次。把局部串换成Set之后还有一个附带好处1和11这种多字符状态不会被contains误判因为比较的是元素而不是子串。3.3 读字母函数只负责 move不管 ε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是要读的字母比如astrings是转移表。返回值是从这个状态经一条s弧能直达的所有终点拼成的串。这个函数刻意做得很窄——它只处理一条边、一个字母、一个起点。把「前后还要读空」这件事完全推给调用方逻辑就干净了。作者在报告里说正是这一步拆开之后原来卡住的地方才通。这个经验很值得记遇到一个函数要同时处理多种转移关系时先按转移类型拆别在一个循环里堆if。同样的多字符问题在这里也存在charAt(1)只认一位数。要扩成集合版就是外层再套一层遍历public static SetString move(SetString states, String symbol, String[] productions) { SetString result new LinkedHashSet(); for (String st : states) { // 对集合里每个状态 for (String p : productions) { String from p.substring(1, p.indexOf(,)); String sym p.substring(p.indexOf(,) 1, p.indexOf())); String to p.substring(p.indexOf(→) 1); if (from.equals(st) symbol.equals(sym)) { result.add(to); // 只走这一条字母边不管 ε } } } return result; }参数含义和单状态版一致只是起点换成了集合返回值也换成集合。空结果直接返回空集不用特殊标记调用方用isEmpty()判断就行。3.4 子集读空Ia 之后再走一遍 εpublic static String DuKong(String result, String[] strings) { for (int i 0; i result.length(); i) { for (int j 0; j strings.length; j) { if (String.valueOf(result.charAt(i)).equals(String.valueOf(strings[j].charAt(1)))) { if (ε.equals(String.valueOf(strings[j].charAt(3)))) { result String.valueOf(strings[j].charAt(6)); // 拼到串尾 RestltList(result, strings); // 继续读空 } } } } return result; }这个函数跟 3.2 那个读空长得像但入口不一样它接收的是「已经读过字母」的结果集然后对这个集合里的每个状态都尝试走 ε。外层for遍历result的每个字符内层扫转移表命中 ε 边就把终点拼到result尾部。因为result在循环里不断变长result.length()每次判断都会重新取值新拼进来的状态也会被后续轮次扫到。参数说明result是 move 的输出strings是转移表。返回的是补齐闭包之后的集合串。这里同样有返回值没接住的问题RestltList(result, strings)的结果被丢掉了同时result又在原地增长两种累积方式混用容易出现「有的分支补全了、有的没补全」的玄学现象——表现就是同一个 NFA改一下转移表的行顺序输出就变了。这是最难受的一类 bug因为它不报错。顺一下完整的语义链条move(T, a)得到的是「从 T 里任意状态走一条 a 弧直达的状态」这些状态自己可能还有 ε 出边所以必须再求一次闭包。三步合起来才是教科书上的ε-closure(move(T, a))。少走最后一步构造出来的 DFA 会缺转移多走一步在 move 之前也求闭包倒不影响正确性只是多算一遍。3.5 主循环从 {ε-closure(X)} 滚到不再出现新子集主循环用的是工作表算法worklist本质就是 BFSSetString start epsilonClosure(Collections.singleton(X), productions); DequeSetString queue new ArrayDeque(); SetSetString visited new LinkedHashSet(); // 用 LinkedHashSet 保证输出顺序稳定 queue.add(start); visited.add(start); // dfa: 状态子集 - (字母 - 下一个状态子集) MapSetString, MapString, SetString dfa new LinkedHashMap(); while (!queue.isEmpty()) { SetString cur queue.poll(); MapString, SetString trans new LinkedHashMap(); for (String a : alphabet) { // 字母表比如 {a,b} SetString moved move(cur, a, productions); SetString next epsilonClosure(moved, productions); trans.put(a, next); if (!next.isEmpty() visited.add(next)) { // 新子集才入队 queue.add(next); } } dfa.put(cur, trans); }几个参数要说清楚。start是新初态 X 的闭包也就是子集构造的种子alphabet是字母表从输入里读出来不包含εvisited承担去重职责visited.add(next)返回true表示这是第一次出现才需要继续扩展否则会死循环dfa存最终结果键是状态子集值是这个子集在每个字母上的去向。外层每弹出一个子集就对字母表里每个字母做一次 move closure得到的新子集如果没出现过就入队。队列空了说明所有可达子集都扩展完了。这个循环一定会停因为状态子集的总数是有限的状态数的幂集而每个子集最多入队一次。如果想额外输出「所有状态子集的空闭包」就在循环结束后再遍历一遍dfa.keySet()对每个子集调一次epsilonClosure打印成对照表System.out.println(状态子集状态子集空闭包); for (SetString subset : dfa.keySet()) { System.out.println(subset epsilonClosure(subset, productions)); }这段就是报告里mapmax那段代码在做的事只不过原版是手工遍历Set的迭代器、逐个状态调RestltList再合并我这里直接用集合版函数一次算完。语义一样少一层循环。4. 跑起来输入格式、三组测试用例与结果核对代码看懂了接下来是把它跑起来。这份设计没有构建脚本属于纯 Java SE 项目一个入口类加几个静态方法就能编译。真正花时间的不是编译是输入数据的格式对齐——转移表里少一个逗号charAt(3)就取到别的字符程序不报错只是结果全错。4.1 输入约定与解析先定格式再写算法输入分三块状态集、字母表、转移函数。落在文件里就是三行第一行状态用逗号分隔第二行字母用逗号分隔之后每行一条产生式。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读取用Files.readAllLines就够不用上第三方库ListString lines Files.readAllLines(Paths.get(nfa.txt), StandardCharsets.UTF_8); String[] states lines.get(0).split(,); // 状态集 String[] alphabet lines.get(1).split(,); // 字母表不含 ε String[] productions lines.subList(2, lines.size()) // 剩余全是转移函数 .stream() .filter(s - !s.trim().isEmpty()) .toArray(String[]::new);StandardCharsets.UTF_8这个参数别省因为转移表里有ε和→两个非 ASCII 字符用平台默认编码在部分环境下会读成乱码随后charAt(3)取到的就不是ε所有空弧判断全部失效——现象是程序能跑、输出却像没读过空弧一样排查起来很花时间。字母表必须单独给不能让程序从转移表里自己扫。原因很实际一条a边都没有的字母扫不出来但它仍然是字母表成员子集构造时对应的转移应该是空集而不是「不存在这个字母」。这两种情况在做 DFA 最小化的时候区别很大。4.2 例子一一条带 ε 环的完整链路走一遍拿 4.1 那份数据手推几步用来核对程序输出。初始子集是closure({X})X 空跳到 55 空跳到 11 没有 ε 出边所以{X,5,1}。对字母a从{X,5,1}走 a5 有(5,a)→51 有(1,a)→3得到{5,3}再求闭包5 空跳到 1所以是{5,3,1}。对字母b5 有(5,b)→51 有(1,b)→4得到{5,4}闭包补上 1得{5,4,1}。接着扩展{5,3,1}走 a 得{5,3}闭包{5,3,1}是自己不新增走 b 得{5,4}闭包{5,4,1}已经在表里。再扩展{5,4,1}走 a 得{5,3}走 b 得{5,4}闭包后有 44 走 b 到 22 空跳到 66 空跳到 Y所以closure({5,4}) {5,4,1,2,6,Y}。这是一个新子集入队。这就是子集构造的典型形态状态数在扩张但很快收敛。跑完程序控制台应该输出「状态子集状态子集空闭包」的对照表每一行左边是子集右边是它的闭包。核对时抓两点初始子集必须是{X,5,1}含 Y 的那个子集必须是{5,4,1,2,6,Y}。这两个对上了中间逻辑基本就没跑偏。4.3 例子二和例子三空集输出与终态汇合例子二的状态是0,1,X,Y字母a,b转移是(X,ε)→0、(0,ε)→Y、(0,a)→1、(0,b)→1、(1,a)→0。初始闭包{X,0,Y}因为 0 直接空跳到 YY 是终态。这个例子的特点是闭包里从一开始就含终态用来验证「闭包不区分初态终态一律收进来」这一点。同时对字母b走一步从{X,0,Y}出发只有 0 有 b 边到 1得到{1}闭包还是{1}因为 1 没有 ε 出边。程序在这种情况下会输出一个空集行——报告里专门说明「空代表状态子集为空的情况」。这是对的某个子集在某个字母上没有出边move 结果就是空集闭包也是空集它代表 DFA 里的死状态。有些实现会直接把空集丢掉不显示结果看输出的人以为漏了实际上丢掉的是合法信息。例子三的状态是X,1,2,3,Y转移是(X,ε)→1、(1,a)→1、(1,b)→1、(1,ε)→2、(2,b)→3、(3,a)→Y。初始闭包{X,1,2}。走 b1 有 b 到 12 有 b 到 3得{1,3}闭包补上 2 得{1,2,3}。再走 a1 有 a 到 13 有 a 到 Y得{1,Y}闭包不变。这个例子是用来验证「一个子集里既有普通状态又有终态」的合并情况也是手算最容易漏的一个。三组用例覆盖了带 ε 环、初始闭包含终态、子集内混合终态、空集输出。作为验证集合已经够用。要再加我建议补一个「字母表里有某个字母完全没边」的用例专门测空集那条路径。4.4 状态转换图节点布局别用固定坐标报告要求「以状态转换图方式输出用户输入的有限自动机状态结点大小位置布局合理具有通用性」。这个「通用性」是难点——状态数不固定写死坐标一定会重叠。常见做法是环形布局把 n 个状态均匀摆在一个圆上圆心就是面板中心半径按面板尺寸算。// 环形布局n 个状态均匀分布在圆周上避免固定坐标重叠 int n stateList.size(); int cx panel.getWidth() / 2, cy panel.getHeight() / 2; int radius Math.min(cx, cy) - 60; // 留 60px 边距给节点半径和标签 for (int i 0; i n; i) { double theta 2 * Math.PI * i / n; // 每个节点占 2π/n int x (int) (cx radius * Math.cos(theta)); int y (int) (cy radius * Math.sin(theta)); g.drawOval(x - 25, y - 25, 50, 50); // 节点圆直径 50 g.drawString(stateList.get(i), x - 8, y 5); }参数说明stateList是状态列表顺序决定节点在圆上的位置radius用面板宽高较小值减 60保证节点圆不贴边theta是极角2π/n保证等距。这个布局的通用性在于它只依赖状态数量不依赖状态名状态从 3 个变到 30 个都能排开30 个以上标签会挤得换分层布局。边比节点麻烦。自环像(5,a)→5要画成节点上方的一个小圆弧双向边要画成两条带偏移的曲线否则重合成一条。课程设计里通常简化处理直线加箭头自环用固定偏移的小圆重复边合并成一个标签写a,b。这样做视觉上不完美但能看而且代码量可控。5. 避坑与排查字符串下标、递归返回值与静态变量的四个坑这一章是我拆这类小项目时踩过、也在别人代码里反复见到的几个问题全是「不报错但结果不对」的类型排查成本比编译错误高得多。5.1 坑一递归调用的返回值丢了闭包只算出一层现象输入一个三层 ε 链X→5→1→2输出的闭包只有{X,5}第三层的1、2都没进来。换个顺序或者少一条边结果又对了一部分。原因string String.valueOf(strings[i].charAt(6)); RestltList(string, strings);——递归调用发出去了返回值没接。Java 的String不可变递归那一层拼出来的新串只存在于那一层的局部变量里回到调用层就丢了。所以只有最外层拼的那一次生效。解决要么用返回值层层回传string RestltList(string, strings);要么干脆别用递归换成 3.2 里那个显式栈的写法。后者更稳因为不用关心递归深度也不用担心 ε 环。5.2 坑二charAt(6) 写死下标状态编号两位就翻车现象状态名换成10、11之后程序能跑但转移关系完全对不上输出里出现一堆不存在的状态。原因(1,a)→3这个格式下起点在charAt(1)、字母在charAt(3)、终点在charAt(6)全部假定单字符。一旦变成(10,a)→3charAt(1)取到的是1而不是10charAt(3)取到的是,字母判断直接失效。解决不要用固定下标改用分隔符解析。p.substring(1, p.indexOf(,))取起点p.substring(p.indexOf(,) 1, p.indexOf()))取字母p.substring(p.indexOf(→) 1)取终点。更彻底的做法是输入阶段就解析成Production对象后面全程用字段访问字符串只在读写文件时出现。5.3 坑三static 变量跨调用残留第二次运行结果带着上一次的尾巴现象连续对两个不同的 NFA 求闭包第二个的输出里混进了第一个的状态名比如明明状态只有0,1,X,Y结果里冒出个5。原因报告里提到用「静态变量字符串」来累积递归结果因为「每次调用函数只能返回一个状态节点而我们需要的是一个状态子集的集合」。静态变量属于类不随方法调用结束而清理第一次的结果留在里面第二次调用直接往后拼。解决静态变量在方法入口处清空是治标正确的做法是别用静态变量存中间结果。需要返回多个值时返回一个SetString需要跨函数传递时作为参数显式传进去。把状态写进返回值而不是类字段是这类算法代码最基本的一条纪律。5.4 坑四HashSet 当 Map 键输出顺序每次不一样现象同一份输入连跑三次控制台的子集顺序每次都不同看起来像程序有随机行为。原因MapSetString, SetString里键是HashSetHashSet的迭代顺序由哈希值决定元素内容相同但插入顺序不同时遍历出来的顺序就可能不同。算法本身没错只是打印顺序不稳。解决把容器换成LinkedHashSet和LinkedHashMap保持插入顺序。子集构造天然是 BFS按入队顺序输出就是稳定的而且这个顺序恰好是从初始子集逐层扩展的顺序看着更符合直觉核对结果时也方便。6. 二次开发改造把课程设计抽成能复用的自动机工具类这份代码要往工程里挪第一刀应该切在数据表示上。字符串转移表在演示里很方便但它是所有坑的根源——固定下标、单字符状态、ε靠字面量比较。我一般会先抽一个不可变的值对象public final class Production { public final String from; // 起点状态 public final String symbol; // 字母空弧统一用 EPSILON 常量 public final String to; // 终点状态 public static final String EPSILON ε; public Production(String from, String symbol, String to) { this.from from; this.symbol symbol; this.to to; } public boolean isEpsilon() { return EPSILON.equals(symbol); } }解析只在读文件时做一次之后算法层全程用对象。这么改完5.2 那个坑直接消失因为不再有下标这回事。第二刀是把三个静态函数收进一个Nfa类转移关系在构造时按起点建索引MapString, ListProductionmove 和 closure 都从索引里查不再每次全表扫。状态一多全表扫的代价是 O(状态数 × 边数)建索引之后降到 O(出边数)差别在小例子上看不出来在几百个状态的自动机上很明显。第三刀是让算法不只服务于 NFA。epsilonClosure和move这两个函数和具体业务无关抽成工具方法之后能直接用来做 DFA 最小化求等价状态划分、正则表达式转 NFA 之后的闭包计算、甚至语法分析里 LR 项目集的闭包运算——这些场景的数学结构是一样的都是「在一个有 ε 关系的图上求传递闭包」。改造点原实现改造后收益状态转移表示String[]charAtProduction对象 索引支持多字符状态去掉下标依赖闭包计算递归拼串显式栈 LinkedHashSet有 ε 环也不炸结果顺序稳定结果容器HashMapSet,SetLinkedHashMap输出可复现便于比对图布局未实现或固定坐标环形 / 分层布局状态数变化时不重叠验证方法很简单拿原来那三组用例跑改造前后的版本逐行对比输出。状态子集集合必须完全相等顺序可以不同但要能一一对应。再补一个随机生成器造 50 个状态的随机 NFA随机 ε 边比例控制在 20% 以内两个版本跑出来的子集数量必须一致——这一步能抓出递归版的深链问题我试过超过二十层 ε 链的时候旧版就开始缺状态了。状态图那一块如果只是给自己看别在 Swing 里手画箭头把dfa的转移关系导成 DOT 文本交给外部工具渲染几行字符串拼接的事布局质量比手写坐标高一个档次。真要集成进 Web 页面也是前端拿 JSON 渲染Java 这边只负责吐出{from, symbol, to}三元组。这份课程设计最值钱的地方不是那几百行代码是作者在报告里留下的那句经验一个功能难实现的时候把它拆成几个模块就会变得好理解很多。读空、读字母、读空——三步拆开各自都能单独测合起来就是完整的子集构造。从那以后我每次写状态机相关的代码都强制先把「转移关系怎么存」和「闭包怎么求」这两件事分开写再回头看调用链基本不会再陷进一个函数里绕不出来。希望帮到你。本文还有配套的精品资源点击获取