简介这是一份面向计算机专业学生的编译原理课程设计报告围绕有限自动机空闭包 ε-closure(I) 的 Java 程序实现展开适合正在完成课程设计、实验或准备复习 NFA 状态子集构造的读者参考。报告从需求分析与概要设计入手介绍数组、图结构和哈希表等数据组织方式并拆解读空函数、状态子集扩展、读字母表等模块详细设计部分说明引入新初态 X、终态 Y 后如何通过递归逐条处理空弧并累加结果最终输出全部状态子集及指定子集的空闭包同时以状态转换图呈现自动机结构。正文还包含测试样例、用户使用说明与总结能帮助读者理解算法流程、对照实现思路并排查递归终止与状态扩展中的问题。资源包共 1 个 docx 文件约 177KB为可查阅和修改的课程设计文档。已有 1287 人学习适合作为课程设计写作与 ε-closure 编程实现的对照材料。1. ε-closure(I) 到底在算什么一份 Java 课程设计报告的复现起点编译原理课设里ε-closure(I) 是那种老师讲十分钟、自己写三天还错的地方。这份 Java 课程设计报告做的事情很明确读入一个任意给定的 NFA把状态子集一路推出来对每个子集求空闭包并把自动机按状态转换图画出来结点位置要求「布局合理、有通用性」。它适合两类人——正在赶课设、需要一个能跑通骨架的以及想把子集构造法从伪代码落到真实数据结构上的。后面按「数据怎么进来、闭包怎么算、图怎么画、哪里会翻车」的顺序拆代码在报告原有函数基础上改写成可直接编译的版本手上有 JDK 就能跟。2. 把 NFA 读进内存产生式编码、数据契约与三个函数的职责边界这份报告最容易被低估的部分不是算法是数据怎么进来。原文把状态转移写成(1,a)→3这样的字符串然后靠charAt(1)、charAt(3)、charAt(6)三个固定下标去抠源状态、字母和目标状态。这个做法在课设里能跑通因为它默认了三件事状态名只有一个字符、字母只有一个字符、箭头和括号的写法一个字都不能变。三件事只要破一件整个程序就在解析层崩掉而且崩得很隐蔽——不会抛异常只会算出一个静悄悄的错误结果。我一般会把输入切成「段标记 逗号分隔」的文本格式把解析和算法彻底分开。原因很实在闭包算法是稳定的输入格式是随时会变的两者耦合在一起改一次输入就得动一遍算法调试成本翻倍。2.1 文件格式与状态转移的存储结构先定数据契约。下面这份nfa.txt是后面所有代码的输入$代表 ε 弧段标记以开头states q0,q1,q2,q3 alphabet a,b start q0 accept q3 trans q0,$,q1 q1,a,q2 q2,$,q3 q3,b,q3对应的两个基础类型Transition只存三个字段不做任何解析Nfa负责集合与索引import java.util.*; /** 一条状态转移from --symbol-- tosymbol 为 $ 时代表 ε 弧 */ final class Transition { final String from; final String symbol; final String to; Transition(String from, String symbol, String to) { this.from from; this.symbol symbol; this.to to; } Override public String toString() { return from - symbol - to; } } final class Nfa { final SetString states new LinkedHashSet(); final SetString alphabet new LinkedHashSet(); final SetString starts new LinkedHashSet(); final SetString accepts new LinkedHashSet(); final ListTransition transitions new ArrayList(); /** 源状态 - 出边列表避免每次求闭包都全表扫一遍 */ private final MapString, ListTransition index new HashMap(); void buildIndex() { index.clear(); for (Transition t : transitions) { index.computeIfAbsent(t.from, k - new ArrayList()).add(t); } } ListTransition outOf(String state) { return index.getOrDefault(state, Collections.emptyList()); } }这里用LinkedHashSet而不是HashSet理由不是性能是可复现同一份输入跑两次输出的状态顺序必须一致否则你没法用 diff 对比「改代码前」和「改代码后」的结果差异。子集构造这种指数级输出的东西顺序一乱人工核对基本等于重做。buildIndex把「按源状态取出边」从 O(m) 降到 O(1)。原文的几个函数都是「外层循环状态、内层循环全部产生式」状态数上到二十、弧数上到五十以后子集构造里每产生一个新子集就要扫一遍全表卡顿会非常明显。课设规模小感觉不到但这是一种会随着输入规模放大的写法早改早省事。解析器本身没有技术含量关键是每一段都必须给出明确的失败信息import java.io.*; import java.nio.charset.StandardCharsets; static Nfa parse(File file) throws IOException { Nfa nfa new Nfa(); int section 0; // 0未进入任何段 try (BufferedReader br new BufferedReader( new InputStreamReader(new FileInputStream(file), StandardCharsets.UTF_8))) { String line; while ((line br.readLine()) ! null) { line line.trim(); if (line.isEmpty() || line.startsWith(#)) continue; // 注释与空行跳过 if (line.startsWith()) { switch (line.substring(1)) { case states: section 1; break; case alphabet: section 2; break; case start: section 3; break; case accept: section 4; break; case trans: section 5; break; default: throw new IllegalArgumentException(未知段标记 line); } continue; } String[] p line.split(\\s*,\\s*); // 逗号两侧允许空格 switch (section) { case 1: nfa.states.addAll(Arrays.asList(p)); break; case 2: nfa.alphabet.addAll(Arrays.asList(p)); break; case 3: nfa.starts.add(p[0]); break; case 4: nfa.accepts.add(p[0]); break; case 5: if (p.length ! 3) { throw new IllegalArgumentException(转移行必须是 源,符号,目标 line); } nfa.transitions.add(new Transition(p[0], p[1], p[2])); nfa.states.add(p[0]); // 转移里出现但没声明的状态自动补登记 nfa.states.add(p[2]); break; default: throw new IllegalArgumentException(数据行出现在任何段标记之前 line); } } } nfa.buildIndex(); return nfa; }section是一个状态机switch里每个分支只做一件事。p.length ! 3这一行是必须的没有它少写一个逗号就会抛ArrayIndexOutOfBoundsException报错行号指向数组访问而不是你的数据文件排查时间全浪费在找错地方。参数上唯一需要留意的是文件编码InputStreamReader显式指定UTF-8后面第 5 章会讲到不指定会出什么事。2.2 读空、读字母、读后再读空三段式函数的输入输出原文把闭包拆成三个函数这个拆法本身是对的只是名字起得随意。放到标准子集构造的语境里它们是三个语义清晰的算子函数输入输出对应数学记号epsilonClosure一个状态集合沿 ε 弧能到达的全部状态含自身ε-closure(I)move集合 I 一个字母 a从 I 出发只走 a 弧到达的状态move(I, a)step集合 I 一个字母 a先 move 再求闭包ε-closure(move(I, a))原文说的「读空、读 a、再读空」其实比标准定义多做了一次前置读空。多出来的那一次不是错误是冗余参与运算的子集如果已经是闭包前置读空的结果就是它自己。但冗余会带来一个副作用——当你想单独测试闭包函数是否正确时喂进去的集合本身已经是闭包输出和输入一模一样你根本判断不出函数有没有生效。这个现象在第 5 章会展开。三个函数的实现极短短到没有出错空间/** ε-closure栈式不动点visited 兼作结果集天然去重 */ static SetString epsilonClosure(Nfa nfa, CollectionString seed) { SetString closure new LinkedHashSet(seed); // 闭包恒包含自身 DequeString stack new ArrayDeque(seed); while (!stack.isEmpty()) { String cur stack.pop(); for (Transition t : nfa.outOf(cur)) { if (!$.equals(t.symbol)) continue; // 只走 ε 弧 if (closure.add(t.to)) stack.push(t.to); // add 返回 false 说明已收过不再展开 } } return closure; } /** move只走字母弧不看 ε */ static SetString move(Nfa nfa, CollectionString set, String symbol) { SetString result new LinkedHashSet(); for (String s : set) { for (Transition t : nfa.outOf(s)) { if (symbol.equals(t.symbol)) result.add(t.to); } } return result; } /** 子集构造里真正用到的一步 */ static SetString step(Nfa nfa, CollectionString set, String symbol) { return epsilonClosure(nfa, move(nfa, set, symbol)); }if (closure.add(t.to)) stack.push(t.to);这一行是整个闭包函数的核心。Set.add返回布尔值返回true表示这是个新状态值得继续展开返回false表示之前已经收过再展开就是重复劳动甚至死循环。用add的返回值当去重判据比先contains再add少一次哈希查找更重要的是它把「去重」和「是否继续」绑成了一个原子判断不会出现「判断了没加、加了没判断」这类经典笔误。ε 环在真实 NFA 里非常常见比如q0 -ε- q1、q1 -ε- q0没有这个判据就是StackOverflowError。2.3 子集构造的主循环与不动点终止有了step主循环就是一个标准的宽度优先搜索队列里放的是集合而不是状态/** 返回子集构造过程中产生的全部状态集合顺序稳定 */ static ListSetString buildSubsets(Nfa nfa) { SetSetString visited new LinkedHashSet(); // Set 的 hashCode 与元素顺序无关可直接去重 DequeSetString queue new ArrayDeque(); SetString start epsilonClosure(nfa, nfa.starts); // 新初态的闭包 所有初态闭包的并 visited.add(start); queue.add(start); while (!queue.isEmpty()) { SetString cur queue.poll(); for (String a : nfa.alphabet) { SetString next step(nfa, cur, a); if (next.isEmpty()) continue; // 空集是否保留成死状态看课程要求 if (visited.add(next)) queue.add(next); // 只有新集合才入队这就是不动点判据 } } return new ArrayList(visited); }visited.add(next)既做去重又做「是否入队」的判定和闭包函数里是同一个套路。子集数量最多 2 的 n 次方但实际 NFA 通常远小于这个上界因为很多子集根本不可达。next.isEmpty()那一行的取舍取决于课设要求如果要求画出完整 DFA需要保留一个死状态如果只要求输出可达子集直接跳过。这一点在写报告的时候要明确写出来否则答辩时被问「你的 DFA 为什么少一个状态」会很被动。buildSubsets返回List而不是Set是因为后面输出、画图、建转移表都要按下标访问List用起来直接。顺序由LinkedHashSet的插入序保证也就是按 BFS 发现的顺序这个顺序对人读输出是友好的。3. 递归求闭包String 累加的翻车现场与 Set 版本重写原文所有闭包逻辑都靠递归加字符串拼接完成还特意提到「用静态变量字符串接收结果」。这段代码我第一眼看到就觉得不对劲实际跑起来会发现它不是「偶尔出错」而是稳定地少收状态。原因不复杂但很值得写下来因为它踩的是 Java 里最基础也最容易被忽略的一条方法参数是值传递String不可变。3.1 为什么第一版用递归以及递归错在哪原文的读空函数长这样逻辑意图是「一直递归到没有新状态为止」public static String RestltList(String string, 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; }问题出在RestltList(string, strings);这一行——调用完就完了返回值没赋给任何变量。string是局部变量在方法入口处复制了一份引用的副本递归调用把它再复制一份传给下一层。下一层里string ...生成一个新对象并赋给下一层的局部变量当前这一层手里的string完全没变。等递归返回那个更长的字符串就随着栈帧一起被丢掉了。最终效果是闭包只收了一层。X -ε- 5能查到5 -ε- 1查不到。如果 NFA 的 ε 链只有一层函数看起来是对的只要有二层以上结果就是错而且错得很安静。同一段代码还有两个次要问题。string.charAt(string.length() - 1)只取最后一个字符隐含「状态名是单字符」这个假设string里如果拼进了多字符状态名取到的是半个名字。另外整个函数没有 visitedq0 -ε- q1加q1 -ε- q0会直接把栈打穿。注意递归本身没问题问题在「靠递归的副作用收集结果」。收集型递归要么把返回值接住再传入下一层要么干脆传一个可变容器进去两条路选一条别混着来。3.2 用 Set 收集器重写 ε-closure改成迭代加Set之后代码反而更短。第 2 章的epsilonClosure已经给出了版本这里补一个带「来源追踪」的变体——调试的时候能直接看到某个状态是怎么被收进闭包的省掉大量打印语句/** 返回 状态 - 把它收进闭包的前驱状态用于排查闭包为什么多/少 */ static MapString, String closureWithTrace(Nfa nfa, CollectionString seed) { MapString, String from new LinkedHashMap(); DequeString stack new ArrayDeque(); for (String s : seed) { from.put(s, null); // 种子状态没有前驱 stack.push(s); } while (!stack.isEmpty()) { String cur stack.pop(); for (Transition t : nfa.outOf(cur)) { if (!$.equals(t.symbol)) continue; if (!from.containsKey(t.to)) { from.put(t.to, cur); // 记录是被谁拉进来的 stack.push(t.to); } } } return from; }from的 key 集合就是闭包本身value 是前驱null表示种子。排查「闭包少了某个状态」的时候不用猜看这个状态在不在 key 里、不在就顺着 ε 弧往回找断在哪一条排查「闭包多了某个状态」也一样顺着 value 链往上走一眼能看出是不是某条ε弧被误读成了别的符号。参数seed接受Collection而不是Set是为了让调用方可以直接传List少一次装箱拷贝的麻烦。3.3 从新增初态 X 求首个子集批量输出闭包标准子集构造会在 NFA 前面加一个新初态 X、后面加一个新终态 Y。原文在这一点上做了妥协只让 X 连到「非空初态集里的某一个状态」理由是「连到任意一个太麻烦」。这个妥协在单初态的 NFA 上完全看不出问题在多初态 NFA 上会直接算错——剩下那几个初态的闭包根本进不了第一个子集。我在实现里把这步改回完整语义X 到每个初态都连一条 ε 弧然后直接求epsilonClosure(nfa, nfa.starts)等价于求 X 的闭包还省掉了真的把 X 插进图里的麻烦。Y 同理把所有终态收进一个集合判断某个子集是否为终态时用「与终态集有交集」代替。批量输出这一段是课设的要求之一也是第 5 章那个「输出和输入一样」的坑的源头static void printAllClosures(Nfa nfa) { ListSetString subsets buildSubsets(nfa); System.out.println(状态子集\t空闭包); for (SetString sub : subsets) { SetString closure epsilonClosure(nfa, sub); // 标准构造下 sub 已是闭包这里等于自身 System.out.println(sub \t closure); } }跑起来会发现两列内容一模一样很多人到这一步以为算法没生效回头去改闭包函数越改越乱。真相是buildSubsets产出的每个sub本身就是闭包再求一次当然是它自己。要验证闭包函数得拿原始状态比如只含{q0}单独喂进epsilonClosure别拿子集构造的结果去测它。4. 状态转换图邻接表建模、分层布局与自环/双向边处理报告里「以状态转换图方式输出、结点大小位置布局合理、具有通用性」这条要求实际动手量比闭包算法还大。闭包是纯计算画图要处理坐标、边重叠、自环、双向边、终态双圈每一项都能卡半天。4.1 图数据结构与边去重画图之前先把「哪些边要画」算清楚。NFA 里同一对状态之间可能有多条不同符号的边直接画会重叠成一团正确做法是按 (源, 目标) 归并把符号拼成一个标签/** 把 (from,to) 相同的多条转移合并成一条边标签用逗号拼接 */ static ListString[] mergeEdges(Nfa nfa) { MapString, ListString byPair new LinkedHashMap(); // key from \u0001 to for (Transition t : nfa.transitions) { String key t.from \u0001 t.to; String label $.equals(t.symbol) ? ε : t.symbol; byPair.computeIfAbsent(key, k - new ArrayList()).add(label); } ListString[] edges new ArrayList(); for (Map.EntryString, ListString e : byPair.entrySet()) { String[] parts e.getKey().split(\u0001); edges.add(new String[]{ parts[0], parts[1], String.join(,, e.getValue()) }); } return edges; }用\u0001做分隔符而不是逗号或冒号是因为状态名里可能出现任何可打印字符只有控制字符能保证不冲突。这是个很小的习惯但在解析类项目里能省掉一堆「状态名叫a:b怎么办」的追问。4.2 分层坐标计算与结点半径「布局合理」翻译成代码就是层次分明、同行不重叠、整体居中。用 BFS 层次是最省事也最通用的做法环形布局在状态数少的时候好看状态一多就挤成一坨/** BFS 分层同一层沿水平方向等距铺开从初态不可达的状态单独沉到底层 */ static MapString, int[] layout(Nfa nfa, int width, int height) { MapString, Integer depth new HashMap(); DequeString queue new ArrayDeque(); for (String s : nfa.starts) { depth.put(s, 0); queue.add(s); } MapString, ListString adj new HashMap(); for (Transition t : nfa.transitions) { adj.computeIfAbsent(t.from, k - new ArrayList()).add(t.to); } while (!queue.isEmpty()) { String cur queue.poll(); int d depth.get(cur); for (String to : adj.getOrDefault(cur, Collections.emptyList())) { if (!depth.containsKey(to)) { // 只按首次到达定层回边不参与 depth.put(to, d 1); queue.add(to); } } } int maxDepth depth.values().stream().mapToInt(Integer::intValue).max().orElse(0); for (String s : nfa.states) depth.putIfAbsent(s, maxDepth 1); // 兜底防止缺坐标 MapInteger, ListString layers new TreeMap(); for (String s : nfa.states) { layers.computeIfAbsent(depth.get(s), k - new ArrayList()).add(s); } MapString, int[] pos new HashMap(); int rowCount layers.size(), row 0; for (Map.EntryInteger, ListString e : layers.entrySet()) { ListString nodes e.getValue(); double y (rowCount 1) ? height / 2.0 : 60 (height - 120.0) * row / (rowCount - 1); for (int i 0; i nodes.size(); i) { double x width * (i 1.0) / (nodes.size() 1); pos.put(nodes.get(i), new int[]{(int) x, (int) y}); } row; } return pos; }if (!depth.containsKey(to))这个判断很关键。状态图里回边极多如果不加判断BFS 每遇到一条回边就把目标状态的层次往上推层数会一路涨到超过状态总数图会被拉成一条斜线。只按首次到达定层等价于对图做一次最短路径分层视觉上最接近教科书画法。结点半径建议按状态名的字符数动态算r max(18, 8 textWidth / 2)固定半径在状态名变长之后会出现文字压边框。同行间距用width / (n 1)也能用但当同层状态超过八个时中点会被挤到一起稳妥一点的做法是取max(固定间距, 可用宽度 / n)超宽就允许横向滚动。4.3 Swing 绘制与 DOT 导出两条输出路线看课设要求哪种。要求截图放进报告里Swing 直接画最省事要求可交互或可打印导成 DOT 交给 Graphviz 渲染质量更高。Swing 这边paintComponent里只做三件事画边、画结点、画标签。自环和双向边是两个必须单独处理的情况Override protected void paintComponent(Graphics g) { super.paintComponent(g); Graphics2D g2 (Graphics2D) g; g2.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON); for (String[] e : edges) { // edges 来自 mergeEdges int[] p1 pos.get(e[0]), p2 pos.get(e[1]); if (e[0].equals(e[1])) { g2.drawArc(p1[0] - 12, p1[1] - R - 24, 24, 24, 0, 360); // 自环画成小圆 g2.drawString(e[2], p1[0] 16, p1[1] - R - 8); continue; } boolean back hasReverse(e[0], e[1]); // 反向边是否存在存在则画弧线错开 int offset back ? 14 : 0; g2.drawLine(p1[0], p1[1] offset, p2[0], p2[1] offset); g2.drawString(e[2], (p1[0] p2[0]) / 2, (p1[1] p2[1]) / 2 - 6); } for (String s : pos.keySet()) { // 先画边后画点保证点压在边上面 int[] p pos.get(s); g2.drawOval(p[0] - R, p[1] - R, R * 2, R * 2); if (nfa.accepts.contains(s)) { // 终态套双圈 g2.drawOval(p[0] - R - 4, p[1] - R - 4, (R 4) * 2, (R 4) * 2); } g2.drawString(s, p[0] - 6, p[1] 5); } }hasReverse的实现就是查一下edges里有没有(e[1], e[0])。有的话两条边都往下偏移视觉上分成两条弧。这个偏移量 14 是试出来的太小两条线还是贴在一起太大箭头会飘到结点外面。导出 DOT 的代码只有十几行适合直接贴进报告附录static String toDot(Nfa nfa) { StringBuilder sb new StringBuilder(digraph NFA {\n rankdirLR;\n node [shapecircle];\n); for (String s : nfa.states) { String shape nfa.accepts.contains(s) ? doublecircle : circle; sb.append( \).append(s).append(\ [shape).append(shape).append(];\n); } for (Transition t : nfa.transitions) { String label $.equals(t.symbol) ? ε : t.symbol; sb.append( \).append(t.from).append(\ - \).append(t.to) .append(\ [label\).append(label).append(\];\n); } return sb.append(}\n).toString(); }rankdirLR让图从左到右排跟教材里的自动机图方向一致doublecircle是 Graphviz 里终态的标准写法不用自己套圈。文件名后缀写.dot渲染交给外部工具代码里不引任何图形库依赖课设环境里少一个装包的环节。5. 避坑与排查五条踩坑记录每条都能让结果错得毫无提示这一章是整篇里我最想写的部分。前面几章的代码都是改好之后的样子真正耗时间的是从「跑出来不对」到「知道哪里不对」这一段。下面五条都是我在本地照着原文复现时真实撞上的共同点是不报错、不崩溃、程序正常退出只是结果悄悄错了。5.1 闭包只收一层String 在递归里被复制了现象ε 链X -ε- 5 -ε- 1闭包输出{X, 5}1死活进不来。换成只有一层 ε 的 NFA 又完全正常。原因递归调用RestltList(string, strings)的返回值没有被接住。String不可变string x在当层栈帧里创建新对象并赋给局部变量父层手里那份引用指向的还是老对象。递归越深被丢掉的部分越多。解决换成第 3 章的epsilonClosure用Set做收集器迭代代替递归。如果一定要保留递归形式就得写成string RestltList(string next, strings); return string;让每层都把结果接住再往下传。我倾向前者一是没有栈深度风险二是收集逻辑和遍历逻辑分开了调试时能单独打断点看集合内容。5.2 ε 符号读成乱码编码没对齐现象数据文件里明明写的是ε程序里ε.equals(...)永远返回false闭包只剩种子状态自己一个都收不进来。原因源文件用 UTF-8 保存javac在有的环境里默认按平台编码GBK读源文件编译出来的字符串常量字节序列和运行时的ε对不上。表现出来就是「代码看着没错结果就是不对」最消耗耐心的一种。解决三处一起对齐。源文件保存为 UTF-8编译加-encoding UTF-8读数据文件时显式new InputStreamReader(in, StandardCharsets.UTF_8)。更彻底的做法是数据文件里干脆不用ε用$或空串表示只在输出、画图的时候再映射回ε把编码风险限制在展示层。第 2 章的解析器用的就是这个思路。javac -encoding UTF-8 -d out src/*.java java -Dfile.encodingUTF-8 -cp out Main nfa.txt5.3 输出的闭包和输入一模一样现象批量输出所有子集的闭包两列内容完全相同逐行对比零差异。以为是闭包函数没被调用。原因buildSubsets产出的每个子集本身就是「先 move 再求闭包」的结果天然是闭包。再对它求一次闭包由幂等性必然得到自身。这个现象恰恰说明算法是对的。解决验证闭包函数要拿非闭包的原始集合去测。准备三个最小用例单状态无 ε 出口、两层 ε 链、两个状态互为 ε 环。三个都过再跑完整 NFA。另外在输出里加一列「子集来源」由哪个子集经过哪个字母得到报告里写清楚每个子集的来历答辩时被追问也答得上。5.4 多初态 NFA 结果少了一半现象NFA 声明了两个初态子集构造跑出来的第一个子集只包含其中一个初态的闭包另一个初态及其后续状态完全没出现在结果里。原因新增初态 X 只连了一条 ε 弧到「非空初态集里的某一个状态」。这是原文明确写下的简化「连到任意一个太麻烦」。单初态时看不出问题多初态时剩下那几个初态的闭包根本进不了第一个子集整棵可达树被砍掉一半。解决X 到每个初态都连 ε 弧或者干脆不插 X直接求epsilonClosure(nfa, nfa.starts)。后者更省事语义完全等价。终态同理用「子集与终态集有交集」判断不要只认 Y 一条弧。5.5 charAt 固定下标解析在换格式后全线崩现象把状态名从1、2改成q1、q2程序要么抛StringIndexOutOfBoundsException要么算出一堆不存在的状态。原因charAt(1)、charAt(3)、charAt(6)这三个下标是照着(1,a)→3这个模板数出来的隐含「括号一位、状态一位、箭头两位」的假设。状态名变两位第三个字符就不是字母了逗号后面多一个空格所有下标整体偏移。解决坚决不用固定下标解析结构化文本。用split按分隔符切或者正则可选分组把「格式」和「取值」分开。第 2 章的逗号分隔格式就是为这个改的。如果必须兼容原有(1,a)→3写法至少用replaceAll([()→\\s], )先清一遍外壳再切别数下标。// 兼容旧格式(1,a)→3 或 ( q1 , a ) → q2 static Transition parseLegacy(String line) { String core line.replaceAll([()\\s→], ); // 去掉括号、箭头、空白 String[] p core.split(,); if (p.length ! 3) throw new IllegalArgumentException(无法解析转移 line); return new Transition(p[0], p[1], p[2]); }replaceAll里→直接写在字符类里不需要转义。这行代码比三个charAt多敲了几个字符换来的是状态名随便改都不会崩。6. 验证闭包对不对手算对照、位集加速与一个可复用的检查习惯闭包这种东西光看代码看不出对错必须有一组能手工核对的小用例。我一般固定跑三个单状态无 ε 出口闭包等于自身验证恒等性、三层 ε 链验证递归深度、两个状态互为 ε 环验证去重和终止。这三个过了再上真实数据。完整对照建议用报告里的那个例子手算一遍贴表里比起点集合读 a 后的 moveε-closure(move){X,5,1}{5,3}{5,3}{X,5,1}{5,4}{5,4}{5,3}{5,2}{5,2,6,Y}{5,4}{5,5}{5,1}{5,1}{5,3}{5,3}手算的关键不是算得多快是每一步都写清楚「这个状态是从哪条弧进来的」。只要有一格对不上顺着那条弧往回查比对着输出瞎猜快十倍。规模上去之后SetString的开销会变成瓶颈。常见做法是把状态编号映射成整数用java.util.BitSet表示集合闭包运算就是按位或/** 预先把 ε 弧的闭包算好存在一张表里运行期只做按位或 */ static BitSet[] precomputeEpsilon(Nfa nfa, MapString, Integer idOf) { BitSet[] table new BitSet[nfa.states.size()]; for (String s : nfa.states) { int id idOf.get(s); BitSet bs new BitSet(); for (String t : epsilonClosure(nfa, List.of(s))) bs.set(idOf.get(t)); table[id] bs; } return table; }预计算的开销是 O(n × 闭包大小)换来的是运行期每次求闭包只需对若干个BitSet做or比反复建HashSet快一个量级也让「两个子集是否相同」退化成BitSet.equals。代价是状态必须提前编号输入里出现新状态就得重建映射表。课设规模下不必上这套但知道有这么一条路遇到状态数上百的自动机时不会手足无措。最后说一个习惯。我在写这类「递归 收集结果」的代码时只要发现返回值没被接住就会立刻停下来改结构不管当前测试是不是碰巧能过——因为这类 bug 的表现完全取决于输入数据的形状测不到不代表不存在。从那以后我每次改完闭包函数都强制走一遍那三个最小用例再跑完整例子宁可多花五分钟也不愿意在报告交上去之后才发现某个 ε 环把结果带偏了。希望帮到你。本文还有配套的精品资源点击获取
