简介这份课程设计报告面向计算机科学与技术等专业学习编译原理的学生围绕有限自动机NFA的空闭包ε-closure(I)计算给出可运行的Java实现思路与完整课程设计文档。内容从需求分析、概要设计延伸到详细设计与测试涵盖NFA输入与文件保存、全部状态子集空闭包输出、指定状态子集空闭包求解以及状态转换图的布局与绘制并拆解读空函数、读状态子集、读字母表、状态子集扩展等模块说明新增初态X与终态Y的连接处理配有测试用例、用户使用说明、总结和程序源代码附录便于对照任务复现实验、理解递归求空闭包与读字母表后再读空的组合逻辑。压缩包共1个docx文件约177KB以报告文档形式呈现章节完整、便于检索。已有1287人学习适合需要完成编译原理课程设计、参考Java实现与报告写法的读者。1. ε-closure 到底难在哪一份课程设计里真正卡人的三处课本上讲 ε-closure(I) 就两行字I 里每个状态自身加上从它们出发经过任意条 ε 弧能到达的所有状态。我当时看完觉得这有什么难的结果动手写 Java 实现第一个函数就卡了两个晚上。后来把这份《编译原理 ε-closureI的程序实现Java 实现课程设计报告》翻来覆去啃了几遍又把里面的源码拆开重跑才明白难点根本不在定义上。真正的坑集中在三处递归读空时返回值怎么累加、为什么读字母和读空必须拆成两个函数而不能混在一起、以及状态子集去重键怎么设计才不至于让程序转不完。这篇把踩过的坑、拆出来能直接复用的三段代码还有三个测试用例的完整执行轨迹都摊开讲给正在做同类课程设计、或者刚学 NFA 确定化的同学一份能照着跑的版本。2. 需求拆解把输入任意 NFA翻译成四个可编码的目标这份课程设计报告的需求描述只有四条看起来很清楚但真落到代码上每一条都会牵出一堆没说出口的隐含约束。比如输入任意给定的有限自动机这七个字就至少要求程序支持状态数量不固定、字母表不固定、ε 弧的条数不固定、空弧可以和普通弧交叉出现。再比如输出所有的状态子集的空闭包前提是你得先把所有状态子集求出来而求子集本身又依赖空闭包这是个互相咬合的循环第一次写的人很容易在这里绕晕。我一般的做法是先把需求拆成数据怎么进、数据长什么样、数据怎么算、结果怎么呈现四个格子每个格子里只放一件事然后再去看它们之间的依赖顺序。这个习惯后来做别的项目也一样用得上因为凡是需求里出现任意两个字的地方后面基本都藏着一个泛化设计。2.1 产生式字符串一个能用但很脆弱的存储方案这份报告里选的是用 String 数组存状态转移函数每个元素写成(1,a)→3这种形式整体长这样// 每一条产生式就是一个字符串下标位置被当作字段用 String[] rules { (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 };配套的取字段方式是用charAt卡位置读代码的人第一眼会觉得莫名其妙所以我把下标含义列一下下标位置含义例子(5,ε)→1里的取值charAt(0)左括号纯占位(charAt(1)弧的起点状态5charAt(2)逗号纯占位,charAt(3)弧上的标记或 εεcharAt(4)右括号纯占位)charAt(5)箭头符号→charAt(6)弧的终点状态1这个方案的好处是零依赖、写起来快、调试时打印出来人眼能看懂对课程设计这种规模完全够用。代价也很明显它默认状态名只能是单个字符一旦出现q10这样的两字符状态名charAt(6)就取不到终点了。报告里所有例子用的都是0 1 2 3 X Y这种单字符状态所以这个问题一直没暴露出来。新手照着抄很容易在这里翻车后面避坑章我会专门讲怎么改成健壮版本。数据结构部分报告里写的是数组、图、哈希表三种混用对应的实际用途是String 数组存产生式HashSet 存状态子集HashMap 存子集 → 子集的映射和子集 → 空闭包的映射。这三样东西的组合其实已经够用了不需要再引入邻接矩阵或者链表因为 NFA 的规模在课程设计里基本不会超过二三十个状态性能完全不是瓶颈可读性才是。2.2 四条基本要求分别落到哪个函数头上把需求摊平之后四条要求对应的函数清单是这样的需求原文承担的函数输入输出输入 NFA 并保存到文件解析模块文本文件初态集、终态集、字母表、产生式数组输出所有状态子集的空闭包主循环 求闭包函数产生式数组子集 → 空闭包的映射表输出给定状态子集的空闭包求闭包函数单点版一个状态集合串该集合的 ε 闭包以状态转换图方式输出布局 绘图模块状态集 产生式带坐标的节点和连线报告里概要设计部分列了六个模块前端数据传入、后台数据处理与分析、对新引入初态节点 X 的读空函数、对状态子集读空的函数、对状态子集读字母表的函数、根据已有子集求剩余子集直到不出现新子集的函数。这个分法是对的但名字起得有点绕我按功能重新归一下类会更好记录入层文件解析把文本变成产生式数组基础动作层epsilonFrom沿 ε 弧展开、moveOn只沿某个字母的弧走组合层moveThenClosure先走字母再求闭包、closureOfSet对整集求闭包驱动层主循环负责不断产生新子集直到收敛呈现层把结果打印成表格或者算坐标画图。调用关系是一条直线驱动层调组合层组合层调基础动作层呈现层只读结果不参与计算。这条链子一旦理清楚后面写代码基本就是填空。2.3 状态转换图分层加圆周够用且不会挤成一坨第四条要求是以状态转换图方式输出用户输入的有限自动机要求状态结点大小位置布局合理具有通用性。这条最容易被糊弄过去很多课程设计最后就是拿 Java Swing 随手在固定坐标上画几个圆圈交差换个 NFA 立刻重叠。我一般的做法是两级布局先按从新初态 X 出发的最短 ε 路径长度给所有状态分层同一层里的节点按顺序均匀铺在一个圆上。X 固定放在最左边或者最上边Y 固定在对面。具体步骤从 X 开始做一次 BFS只走 ε 弧得到每个状态到 X 的最短空路径长度 d没被 BFS 覆盖到的状态ε 不可达的单独放到最后一层避免漏画第 k 层的节点数量记作 n_k就放在一条水平线上横向间距取max(80, 600 / n_k)像素同层节点如果超过 6 个改成沿半径120 20 * n_k的圆弧分布避免横向撑爆画布连线用直线自环画在节点正上方的小圆弧上双向弧错开 4 像素防止完全重合。这套规则不需要任何图布局库纯手算坐标就行而且对任意 NFA 都能保证节点不重叠、层次方向一致。报告里说结点大小位置布局合理具有通用性其实就是这个意思——通用性不是靠调参调出来的是靠一条确定的规则算出来的。3. 三个读函数怎么配合读空、只读字母、再读空这是整份课程设计报告里最有价值的部分也是报告作者在总结里明确说当时在这个问题上纠结了好一阵的地方。把这三个函数的关系想通了NFA 确定化的代码基本就写完了。核心矛盾在于一个状态子集读字母 a 的时候实际发生的事情不是简单的一条弧。它可能是「先走若干条 ε 到某个状态 → 再走 a → 再走若干条 ε 到别的状态」也可能中间根本没有 a 弧只是被 ε 带到了一个有 a 弧的状态上。如果你试图用一个函数把这两件事一起处理掉代码里立刻会出现三层嵌套的条件判断写到一半必然失控。正确的拆法是让每个函数只做一件最笨的事。3.1 给新初态 X 读空递归能干但游标更稳引入新初态 X 是为了让子集构造有一个统一的起点X 通过一条 ε 弧指向原 NFA 的初态。求第一个状态子集其实就是求 X 的空闭包。报告里给的实现是这样的// 从一个状态出发沿 ε 弧递归展开返回累积后的状态串 // string已累积的状态串末位字符是本次要展开的状态 // strings全部产生式 public static String RestltList(String string, String[] strings) { for (int i 0; i strings.length; i) { // 产生式第 1 位是弧起点和当前串末位状态比较 if (String.valueOf(string.charAt(string.length() - 1)) .equals(String.valueOf(strings[i].charAt(1)))) { // 第 3 位是弧标记只处理 ε 弧 if (ε.equals(String.valueOf(strings[i].charAt(3)))) { string String.valueOf(strings[i].charAt(6)); // 第 6 位是终点 RestltList(string, strings); // 继续往下展开 } } } return string; }这段能跑因为报告里用了一个静态变量字符串来接收、每次递归结果都往上累加的办法。但严格讲它是有隐患的递归调用RestltList(string, strings)的返回值没有被接住靠的是每层递归自己把新字符拼进自己的局部变量再把更深层的结果吞掉。在链式结构A→B→C上这会丢失信息只是因为报告里的测试用例 ε 链都不长所以没暴露。我一般会把它改成游标推进的写法逻辑等价但不需要递归也不怕 ε 环// 沿 ε 弧展开返回状态下标集合 // state起点状态名rules产生式数组 public static String epsilonFrom(String state, String[] rules) { StringBuilder sb new StringBuilder(state); int cursor 0; // 游标指向下一个待展开的位置 while (cursor sb.length()) { char from sb.charAt(cursor); // 取一个还没展开过的状态 cursor; for (String rule : rules) { char src rule.charAt(1); // 弧起点 char lab rule.charAt(3); // 弧标记 char dst rule.charAt(6); // 弧终点 if (src ! from) continue; // 起点不匹配跳过 if (lab ! ε) continue; // 不是 ε 弧跳过 // 已经收进结果的状态不再重复追加防止 ε 环把程序拖死 if (sb.indexOf(String.valueOf(dst)) 0) { sb.append(dst); } } } return sb.toString(); }两个改动值得说清楚。一是把递归换成游标sb一边增长一边被游标扫描天然就是广度优先的展开顺序不需要额外维护队列。二是加了indexOf去重因为一旦 NFA 里存在1 -ε→ 2、2 -ε→ 1这样的 ε 环递归版会一直往下钻而游标版最多扫到串里没有新状态为止撑死跑状态数 × 产生式数次。参数说明state传单个状态名比如Xrules就是完整的产生式数组。返回值是一串拼接起来的状态字符比如X51表示{X, 5, 1}。用字符串而不是 Set 存是为了让后面所有函数的签名保持一致方便互相传参——课程设计这个量级字符串足够快而且打印出来就是人眼可读的结果调试成本极低。3.2 只读字母的函数它必须彻底不管 ε第二个函数是报告里说的对状态子集读字母表。它的职责边界必须守死只走标记为某个具体字母的弧一条 ε 都不许碰。// 从状态集出发只走标记为 letter 的弧不处理任何 ε // states状态集合串如 X51letter单个字母如 a public static String moveOn(String states, String letter, String[] rules) { StringBuilder sb new StringBuilder(); for (String rule : rules) { // 标记不匹配这条弧不参与本次移动 if (rule.charAt(3) ! letter.charAt(0)) continue; // 起点不在当前集合里这条弧也走不到 if (states.indexOf(rule.charAt(1)) 0) continue; char dst rule.charAt(6); if (sb.indexOf(String.valueOf(dst)) 0) { sb.append(dst); // 目标状态去重后追加 } } return sb.toString(); }为什么非要拆出来因为move(T, a)和ε-closure(T)在语义上是两个不同层级的操作前者是经过一条标记为 a 的边后者是经过零条或多条 ε 边。如果你把两者写进同一个循环遇到1 -ε→ 2 -a→ 3这种情况代码就没法回答一个问题——这个 3 到底是被 a 带出来的还是被 ε 带出来的答案会影响下一步如果已经处理完了 a那 3 还要继续做闭包如果只是 ε 展开的一半那后面还得补一次完整的 move。混在一起写边界就丢了。拆开之后每个函数只有两三个判断条件出 bug 的时候一眼就能看出是弧标记读错了还是起点匹配错了不用在十几行的嵌套里找。3.3 求 Ia 的三段式ε 到 a 再到 ε有了前两个函数Ia ε-closure(move(T, a))就只是一次组合调用// 求 Ia先对集合做一次 ε 展开确保闭包性再走 a再对结果求闭包 public static String moveThenClosure(String subset, String letter, String[] rules) { // 第一段把集合里的每个状态各自 ε 展开合并去重 StringBuilder closed new StringBuilder(); for (char c : subset.toCharArray()) { String one epsilonFrom(String.valueOf(c), rules); for (char d : one.toCharArray()) { if (closed.indexOf(String.valueOf(d)) 0) closed.append(d); } } // 第二段只走 letter 弧 String moved moveOn(closed.toString(), letter, rules); if (moved.isEmpty()) return ; // 一步都走不动Ia 就是空集 // 第三段再对 move 的结果做一次 ε 展开 StringBuilder result new StringBuilder(); for (char c : moved.toCharArray()) { String one epsilonFrom(String.valueOf(c), rules); for (char d : one.toCharArray()) { if (result.indexOf(String.valueOf(d)) 0) result.append(d); } } return result.toString(); }三段的顺序是有讲究的。第一段看似冗余因为subset本来就应该已经是闭包的但在主循环里如果你传进来的是手工指定的{3}这种非闭包集合少了这一段就会漏掉3 -ε→ …带出来的状态。第二段只走 a第三段补闭包这是标准定义的直接翻译。报告总结里说在读 a 的同时还需要分别在读 a 的前后分别调用读空的函数说的就是这件事只是当时没写成三段而是靠一个函数来回调逻辑上绕了一圈。参数说明subset是状态集合串letter是单个字母字符rules是产生式数组。返回空串表示这个子集在该字母下无路可走这个空串后面要当成一个合法的死状态处理不能当异常丢掉——这是报告里用例二专门要展示的情况。3.4 子集构造主循环去重键不稳定程序就转不完最后是把上面这些组装起来。主循环要做的事很简单从一个子集出发对字母表里每个字母算出 Ia如果 Ia 是新子集就入队直到队列空。// 主循环从 ε-closure({X}) 出发不断产生新子集直到收敛 MapString, String subsets new LinkedHashMap(); // 去重键 → 原始状态串 DequeString queue new ArrayDeque(); String start epsilonFrom(X, rules); subsets.put(sortKey(start), start); queue.add(start); while (!queue.isEmpty()) { String cur queue.poll(); for (char letter : alphabet) { // 遍历字母表 Σ String next moveThenClosure(cur, String.valueOf(letter), rules); String key sortKey(next); // 排序后做去重键 if (!subsets.containsKey(key)) { // 只处理没见过的子集 subsets.put(key, next); queue.add(next); } } } // 把状态串排序保证同一个集合永远生成同一个键 static String sortKey(String s) { char[] arr s.toCharArray(); Arrays.sort(arr); return new String(arr); }这里的sortKey是关键。如果你直接用HashSet.toString()当去重键同一个集合{1,3,5}在不同轮次可能被打印成[1, 3, 5]、[3, 1, 5]或者别的顺序containsKey就会认为它们是不同的子集于是无限入队、程序永远停不下来。我第一次跑的时候就是这样控制台刷屏十几秒还在跑最后靠手动 kill 才停下来。排序之后键就稳定了时间复杂度也可以接受——课程设计量级下排序开销完全可以忽略。4. 代码复现三个测试用例从头跑到尾光看代码还是虚的得跑数据。报告里给了三个用例覆盖了 ε 链、自环、空集子集、有终态但分支少这几种情况我按上面的写法重新推了一遍把每一步的结果都记下来方便你对照自己的程序输出。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第一步先求ε-closure(X)X 走 ε 到 55 走 ε 到 11 没有 ε 出边所以S0 {X,1,5}。接下来对 S0 分别读 a 和 b按ε → 字母 → ε三段走起始子集读 a 后读 b 后S0 {X,1,5}{1,3,5} → S1{1,4,5} → S2S1 {1,3,5}{1,2,3,5,6,Y} → S3{1,4,5} → S2S2 {1,4,5}{1,3,5} → S1{1,2,4,5,6,Y} → S4S3 {1,2,3,5,6,Y}{1,2,3,5,6,Y} → S3{1,4,5,6,Y} → S5S4 {1,2,4,5,6,Y}{1,3,5,6,Y} → S6{1,2,4,5,6,Y} → S4S5 {1,4,5,6,Y}{1,3,5,6,Y} → S6{1,2,4,5,6,Y} → S4S6 {1,3,5,6,Y}{1,2,3,5,6,Y} → S3{1,4,5,6,Y} → S5七个子集全部闭环没有一个引向新子集收敛。注意 S3 读 a 之后还是 S3这不是写错了——{1,2,3,5,6,Y}里 1 走 a 到 3、3 走 a 到 2、5 走 a 回到自己、6 走 a 回到自己而 2 和 Y 本身又各自被 ε 链带着回到了这个集合里所以结果就是它自己。这种自己指向自己的情况在实际 NFA 里很常见程序里必须能正确识别成同一个子集否则就会无限产生新子集。4.2 用例二空集子集是怎么冒出来的第二个用例的状态集是{0,1,X,Y}产生式只有五条(X,ε)→0 (0,ε)→Y (0,a)→1 (0,b)→1 (1,a)→0ε-closure(X) {X,0,Y}这是 S0。S0 读 a 得到{1}读 b 也得到{1}所以 S1 是{1}。S1 读 a 走1 -a→ 0再做闭包得到{0,Y}也就是 S2。关键在于 S1 读 b状态 1 只有一条 a 弧没有任何 b 弧所以 move 的结果是空的ε-closure(∅)按定义还是空集。子集读 a读 b{X,0,Y}{1}{1}{1}{0,Y}∅{0,Y}{1}{1}∅∅∅报告里那句空代表状态子集为空的情况指的正是这里。空集子集在理论上对应 DFA 里的死状态是合法且有意义的不能因为它是空串就跳过不处理。很多实现就是在这里直接if (next.isEmpty()) continue;结果 DFA 少一个状态后面做最小化或者模拟匹配的时候行为就不对了。4.3 用例三有终态但只有四个子集第三个用例状态集{X,1,2,3,Y}(X,ε)→1 (1,a)→1 (1,b)→1 (1,ε)→2 (2,b)→3 (3,a)→Yε-closure(X) {X,1,2}是 S0。往下推子集读 a读 b{X,1,2}{1,2} → S1{1,3} → S2{1,2}{1,2} → S1{1,3} → S2{1,3}{1,Y} → S3{1,2} → S1{1,Y}{1,2} → S1{1,2} → S1四个子集就收敛了比用例一少一半。这个用例的价值在于它有 Y新终态可以验证终态是否被正确带进子集——S3 {1,Y}里包含 Y说明含终态的子集能被识别出来后面判断接受性就靠这个。4.4 三个能固化成断言的校验点跑完之后我一般会留三个检查下次改代码直接对子集总数对得上用例一 7 个、用例二 4 个、用例三 4 个。数量不对八成是去重键不稳定或者空集被跳过了。每个子集读完字母表都有落点哪怕落点是空集也要有记录。如果某个子集读某字母后直接抛出异常或者返回 null说明moveThenClosure里对空串没做处理。ε-closure 的幂等性对任意子集求两次闭包结果必须和求一次完全一样。这条能抓出忘了把自己加进去和ε 环没去重两类问题。5. 避坑与常见问题五条让我返工的记录这一节写的是真出过问题的五件事每条都按看到什么现象、根子上是什么原因、怎么改来写。你在自己实现的时候大概率会撞上其中两三条。5.1 递归读空链式结构上少状态现象测试用例一里ε-closure(X)出来是{X,5}少了 1但单独对 5 求闭包又能正确得到{5,1}。原因递归版RestltList里string ...改的是当前栈帧的局部变量然后调用RestltList(string, strings)却没接返回值。下一层递归里继续拼的字符只存在于下一层的局部变量中往上一层返回时被丢弃了。链只有一层的时候碰巧能对链长到两层就断。解决要么把递归改成return RestltList(state, rules);让结果一层层回传要么干脆换成 3.1 节的游标版。游标版更好因为它顺手解决了 ε 环的问题。5.2 状态名一超过一个字符charAt 全部错位现象把测试数据里的1改成q1程序不报错但求出来的子集莫名其妙读 a 之后目标状态变成了一堆括号和逗号。原因产生式用(1,a)→3这种固定格式字段全靠charAt(1)、charAt(3)、charAt(6)定位。状态名变成两个字符整条串的每个位置都往后挪了一格charAt(6)取到的就不再是终点。解决解析和取值分开。读取的时候用split或者正则一次性拆成源状态 / 标记 / 目标状态三个字段存成对象后面全部按字段访问不再碰下标。课程设计报告里用 charAt 是因为例子都是单字符能跑通就行但如果你想把这份代码留下来复用这一步值得花半小时改掉。5.3 空闭包把自己漏了现象ε-closure(3)返回空串但 3 明明有一条(3,a)→2出边按定义 3 自己应该在闭包里。原因写循环的时候只遍历产生式找 ε 弧忘了闭包定义的第一条是状态自身。当某个状态没有任何 ε 出边时循环一次都不进结果就是空。解决函数入口先把起点本身塞进结果容器再开始扫产生式。用字符串实现的时候就是StringBuilder sb new StringBuilder(state);用 Set 实现就是set.add(state);。这一行看着不起眼但漏掉之后所有只经过一条 a 弧的状态都会丢。5.4 子集去重键不稳定主循环停不下来现象程序跑到第三个用例还在刷屏控制台一直在输出看起来差不多的子集等半分钟也没结束。原因用HashSet.toString()或者直接拿未排序的状态串当 Map 的 key。{1,3,5}和{3,1,5}在逻辑上是同一个集合但字符串不相等containsKey判成新子集于是又入队又展开又产生更多顺序不同的等价串。解决入 Map 之前先把字符数组排序再拼回字符串保证同一个集合只有一个键。这一步开销很小但直接决定了程序能不能收敛。另一个办法是用TreeSet存状态它的toString天然有序效果一样。5.5 新初态 X 只连一个原初态多初态 NFA 直接算错现象用例一、二、三都能跑对但换成一个有两个初态的 NFA结果里有一半子集消失了。原因报告里作者自己也说了X 和 Y 都固定连接到那一个节点并将其作为状态转移函数写在自动机里。这是为了省事做的简化——只给 X 连一条 ε 弧到某一个原初态。原 NFA 只有单个初态时没问题一旦有多个初态X 就只覆盖了其中一个另一个初态及其后续状态永远进不了子集。解决X 到原初态集的每一条 ε 弧都要显式写进产生式数组。比如原初态是{1,4}那就要同时有(X,ε)→1和(X,ε)→4。这一条改起来只要两行但如果不改程序的支持任意 NFA就是假的。6. 把大函数拆碎的收益一个可以复用到别处的套路回过头看这份课程设计报告里最有价值的不是那些具体代码而是作者在总结里写下的那句当一个功能比较难以实现的时候可以把它再分成几个模块来写。他当时卡在一个状态子集既要想 a 弧又要考虑前后 ε上纠结了很久最后是在资料里看到可以先写两个函数分别读字母表和读空求子集的时候按读空、读 a、再读空来写才一下通了。这个套路的通用性比 NFA 本身大得多。任何看起来要在一个循环里同时处理两件事的场景先问一句这两件事能不能拆成两个各自只做一件笨事的函数拆开之后每个函数的输入输出都能单独测出问题的时候定位范围就从整个算法缩小到一个 if 判断。我后来做词法分析、做表达式求值、甚至做配置文件合并用的都是同一个思路先把原子动作写死再用组合函数把它们串成流程最后才写驱动循环。如果这份报告你只打算带走一样东西我建议带走三行骨架// 原子动作一沿 ε 展开不做别的 String epsilonFrom(String state, String[] rules); // 原子动作二只沿某个字母走一步绝不碰 ε String moveOn(String states, String letter, String[] rules); // 组合ε → 字母 → εIa 就这么来 String moveThenClosure(String subset, String letter, String[] rules);我自己有个习惯凡是写这种看起来要递归、要嵌套、要维护一堆状态的算法先在纸上把原子动作列成两三行函数签名签名写不出来就说明还没想清楚绝不开编辑器。这个习惯是被坑出来的早年间写一个类似的闭包算法直接上手堆了一个两百行的嵌套循环跑出来的结果时对时错改了两天最后推翻重写重写只用了四十分钟。从那以后我每次动这种算法都强制先写签名、先拿一个小用例手推一遍、确认每一步的中间结果能对上才动手敲代码。这份课程设计报告里那三个测试用例其实就是干这个用的——用例一验 ε 链和自环用例二验空集用例三验终态传递三个都过算法基本就站住了。报告本身还带了完整的源码附录和需求、概要、详细设计的分层描述对着里面的产生式格式和函数划分看一遍再配合前面几张子集推导表自己重写一遍大概一个晚上能通。希望帮到你。本文还有配套的精品资源点击获取 
长河君 · 2026/11/4 23:17:12 · 阅读 1.2k 课程设计实战：ε-closure的Java实现与NFA确定化避坑
简介这份课程设计报告面向计算机科学与技术等专业学习编译原理的学生围绕有限自动机NFA的空闭包ε-closure(I)计算给出可运行的Java实现思路与完整课程设计文档。内容从需求分析、概要设计延伸到详细设计与测试涵盖NFA输入与文件保存、全部状态子集空闭包输出、指定状态子集空闭包求解以及状态转换图的布局与绘制并拆解读空函数、读状态子集、读字母表、状态子集扩展等模块说明新增初态X与终态Y的连接处理配有测试用例、用户使用说明、总结和程序源代码附录便于对照任务复现实验、理解递归求空闭包与读字母表后再读空的组合逻辑。压缩包共1个docx文件约177KB以报告文档形式呈现章节完整、便于检索。已有1287人学习适合需要完成编译原理课程设计、参考Java实现与报告写法的读者。1. ε-closure 到底难在哪一份课程设计里真正卡人的三处课本上讲 ε-closure(I) 就两行字I 里每个状态自身加上从它们出发经过任意条 ε 弧能到达的所有状态。我当时看完觉得这有什么难的结果动手写 Java 实现第一个函数就卡了两个晚上。后来把这份《编译原理 ε-closureI的程序实现Java 实现课程设计报告》翻来覆去啃了几遍又把里面的源码拆开重跑才明白难点根本不在定义上。真正的坑集中在三处递归读空时返回值怎么累加、为什么读字母和读空必须拆成两个函数而不能混在一起、以及状态子集去重键怎么设计才不至于让程序转不完。这篇把踩过的坑、拆出来能直接复用的三段代码还有三个测试用例的完整执行轨迹都摊开讲给正在做同类课程设计、或者刚学 NFA 确定化的同学一份能照着跑的版本。2. 需求拆解把输入任意 NFA翻译成四个可编码的目标这份课程设计报告的需求描述只有四条看起来很清楚但真落到代码上每一条都会牵出一堆没说出口的隐含约束。比如输入任意给定的有限自动机这七个字就至少要求程序支持状态数量不固定、字母表不固定、ε 弧的条数不固定、空弧可以和普通弧交叉出现。再比如输出所有的状态子集的空闭包前提是你得先把所有状态子集求出来而求子集本身又依赖空闭包这是个互相咬合的循环第一次写的人很容易在这里绕晕。我一般的做法是先把需求拆成数据怎么进、数据长什么样、数据怎么算、结果怎么呈现四个格子每个格子里只放一件事然后再去看它们之间的依赖顺序。这个习惯后来做别的项目也一样用得上因为凡是需求里出现任意两个字的地方后面基本都藏着一个泛化设计。2.1 产生式字符串一个能用但很脆弱的存储方案这份报告里选的是用 String 数组存状态转移函数每个元素写成(1,a)→3这种形式整体长这样// 每一条产生式就是一个字符串下标位置被当作字段用 String[] rules { (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 };配套的取字段方式是用charAt卡位置读代码的人第一眼会觉得莫名其妙所以我把下标含义列一下下标位置含义例子(5,ε)→1里的取值charAt(0)左括号纯占位(charAt(1)弧的起点状态5charAt(2)逗号纯占位,charAt(3)弧上的标记或 εεcharAt(4)右括号纯占位)charAt(5)箭头符号→charAt(6)弧的终点状态1这个方案的好处是零依赖、写起来快、调试时打印出来人眼能看懂对课程设计这种规模完全够用。代价也很明显它默认状态名只能是单个字符一旦出现q10这样的两字符状态名charAt(6)就取不到终点了。报告里所有例子用的都是0 1 2 3 X Y这种单字符状态所以这个问题一直没暴露出来。新手照着抄很容易在这里翻车后面避坑章我会专门讲怎么改成健壮版本。数据结构部分报告里写的是数组、图、哈希表三种混用对应的实际用途是String 数组存产生式HashSet 存状态子集HashMap 存子集 → 子集的映射和子集 → 空闭包的映射。这三样东西的组合其实已经够用了不需要再引入邻接矩阵或者链表因为 NFA 的规模在课程设计里基本不会超过二三十个状态性能完全不是瓶颈可读性才是。2.2 四条基本要求分别落到哪个函数头上把需求摊平之后四条要求对应的函数清单是这样的需求原文承担的函数输入输出输入 NFA 并保存到文件解析模块文本文件初态集、终态集、字母表、产生式数组输出所有状态子集的空闭包主循环 求闭包函数产生式数组子集 → 空闭包的映射表输出给定状态子集的空闭包求闭包函数单点版一个状态集合串该集合的 ε 闭包以状态转换图方式输出布局 绘图模块状态集 产生式带坐标的节点和连线报告里概要设计部分列了六个模块前端数据传入、后台数据处理与分析、对新引入初态节点 X 的读空函数、对状态子集读空的函数、对状态子集读字母表的函数、根据已有子集求剩余子集直到不出现新子集的函数。这个分法是对的但名字起得有点绕我按功能重新归一下类会更好记录入层文件解析把文本变成产生式数组基础动作层epsilonFrom沿 ε 弧展开、moveOn只沿某个字母的弧走组合层moveThenClosure先走字母再求闭包、closureOfSet对整集求闭包驱动层主循环负责不断产生新子集直到收敛呈现层把结果打印成表格或者算坐标画图。调用关系是一条直线驱动层调组合层组合层调基础动作层呈现层只读结果不参与计算。这条链子一旦理清楚后面写代码基本就是填空。2.3 状态转换图分层加圆周够用且不会挤成一坨第四条要求是以状态转换图方式输出用户输入的有限自动机要求状态结点大小位置布局合理具有通用性。这条最容易被糊弄过去很多课程设计最后就是拿 Java Swing 随手在固定坐标上画几个圆圈交差换个 NFA 立刻重叠。我一般的做法是两级布局先按从新初态 X 出发的最短 ε 路径长度给所有状态分层同一层里的节点按顺序均匀铺在一个圆上。X 固定放在最左边或者最上边Y 固定在对面。具体步骤从 X 开始做一次 BFS只走 ε 弧得到每个状态到 X 的最短空路径长度 d没被 BFS 覆盖到的状态ε 不可达的单独放到最后一层避免漏画第 k 层的节点数量记作 n_k就放在一条水平线上横向间距取max(80, 600 / n_k)像素同层节点如果超过 6 个改成沿半径120 20 * n_k的圆弧分布避免横向撑爆画布连线用直线自环画在节点正上方的小圆弧上双向弧错开 4 像素防止完全重合。这套规则不需要任何图布局库纯手算坐标就行而且对任意 NFA 都能保证节点不重叠、层次方向一致。报告里说结点大小位置布局合理具有通用性其实就是这个意思——通用性不是靠调参调出来的是靠一条确定的规则算出来的。3. 三个读函数怎么配合读空、只读字母、再读空这是整份课程设计报告里最有价值的部分也是报告作者在总结里明确说当时在这个问题上纠结了好一阵的地方。把这三个函数的关系想通了NFA 确定化的代码基本就写完了。核心矛盾在于一个状态子集读字母 a 的时候实际发生的事情不是简单的一条弧。它可能是「先走若干条 ε 到某个状态 → 再走 a → 再走若干条 ε 到别的状态」也可能中间根本没有 a 弧只是被 ε 带到了一个有 a 弧的状态上。如果你试图用一个函数把这两件事一起处理掉代码里立刻会出现三层嵌套的条件判断写到一半必然失控。正确的拆法是让每个函数只做一件最笨的事。3.1 给新初态 X 读空递归能干但游标更稳引入新初态 X 是为了让子集构造有一个统一的起点X 通过一条 ε 弧指向原 NFA 的初态。求第一个状态子集其实就是求 X 的空闭包。报告里给的实现是这样的// 从一个状态出发沿 ε 弧递归展开返回累积后的状态串 // string已累积的状态串末位字符是本次要展开的状态 // strings全部产生式 public static String RestltList(String string, String[] strings) { for (int i 0; i strings.length; i) { // 产生式第 1 位是弧起点和当前串末位状态比较 if (String.valueOf(string.charAt(string.length() - 1)) .equals(String.valueOf(strings[i].charAt(1)))) { // 第 3 位是弧标记只处理 ε 弧 if (ε.equals(String.valueOf(strings[i].charAt(3)))) { string String.valueOf(strings[i].charAt(6)); // 第 6 位是终点 RestltList(string, strings); // 继续往下展开 } } } return string; }这段能跑因为报告里用了一个静态变量字符串来接收、每次递归结果都往上累加的办法。但严格讲它是有隐患的递归调用RestltList(string, strings)的返回值没有被接住靠的是每层递归自己把新字符拼进自己的局部变量再把更深层的结果吞掉。在链式结构A→B→C上这会丢失信息只是因为报告里的测试用例 ε 链都不长所以没暴露。我一般会把它改成游标推进的写法逻辑等价但不需要递归也不怕 ε 环// 沿 ε 弧展开返回状态下标集合 // state起点状态名rules产生式数组 public static String epsilonFrom(String state, String[] rules) { StringBuilder sb new StringBuilder(state); int cursor 0; // 游标指向下一个待展开的位置 while (cursor sb.length()) { char from sb.charAt(cursor); // 取一个还没展开过的状态 cursor; for (String rule : rules) { char src rule.charAt(1); // 弧起点 char lab rule.charAt(3); // 弧标记 char dst rule.charAt(6); // 弧终点 if (src ! from) continue; // 起点不匹配跳过 if (lab ! ε) continue; // 不是 ε 弧跳过 // 已经收进结果的状态不再重复追加防止 ε 环把程序拖死 if (sb.indexOf(String.valueOf(dst)) 0) { sb.append(dst); } } } return sb.toString(); }两个改动值得说清楚。一是把递归换成游标sb一边增长一边被游标扫描天然就是广度优先的展开顺序不需要额外维护队列。二是加了indexOf去重因为一旦 NFA 里存在1 -ε→ 2、2 -ε→ 1这样的 ε 环递归版会一直往下钻而游标版最多扫到串里没有新状态为止撑死跑状态数 × 产生式数次。参数说明state传单个状态名比如Xrules就是完整的产生式数组。返回值是一串拼接起来的状态字符比如X51表示{X, 5, 1}。用字符串而不是 Set 存是为了让后面所有函数的签名保持一致方便互相传参——课程设计这个量级字符串足够快而且打印出来就是人眼可读的结果调试成本极低。3.2 只读字母的函数它必须彻底不管 ε第二个函数是报告里说的对状态子集读字母表。它的职责边界必须守死只走标记为某个具体字母的弧一条 ε 都不许碰。// 从状态集出发只走标记为 letter 的弧不处理任何 ε // states状态集合串如 X51letter单个字母如 a public static String moveOn(String states, String letter, String[] rules) { StringBuilder sb new StringBuilder(); for (String rule : rules) { // 标记不匹配这条弧不参与本次移动 if (rule.charAt(3) ! letter.charAt(0)) continue; // 起点不在当前集合里这条弧也走不到 if (states.indexOf(rule.charAt(1)) 0) continue; char dst rule.charAt(6); if (sb.indexOf(String.valueOf(dst)) 0) { sb.append(dst); // 目标状态去重后追加 } } return sb.toString(); }为什么非要拆出来因为move(T, a)和ε-closure(T)在语义上是两个不同层级的操作前者是经过一条标记为 a 的边后者是经过零条或多条 ε 边。如果你把两者写进同一个循环遇到1 -ε→ 2 -a→ 3这种情况代码就没法回答一个问题——这个 3 到底是被 a 带出来的还是被 ε 带出来的答案会影响下一步如果已经处理完了 a那 3 还要继续做闭包如果只是 ε 展开的一半那后面还得补一次完整的 move。混在一起写边界就丢了。拆开之后每个函数只有两三个判断条件出 bug 的时候一眼就能看出是弧标记读错了还是起点匹配错了不用在十几行的嵌套里找。3.3 求 Ia 的三段式ε 到 a 再到 ε有了前两个函数Ia ε-closure(move(T, a))就只是一次组合调用// 求 Ia先对集合做一次 ε 展开确保闭包性再走 a再对结果求闭包 public static String moveThenClosure(String subset, String letter, String[] rules) { // 第一段把集合里的每个状态各自 ε 展开合并去重 StringBuilder closed new StringBuilder(); for (char c : subset.toCharArray()) { String one epsilonFrom(String.valueOf(c), rules); for (char d : one.toCharArray()) { if (closed.indexOf(String.valueOf(d)) 0) closed.append(d); } } // 第二段只走 letter 弧 String moved moveOn(closed.toString(), letter, rules); if (moved.isEmpty()) return ; // 一步都走不动Ia 就是空集 // 第三段再对 move 的结果做一次 ε 展开 StringBuilder result new StringBuilder(); for (char c : moved.toCharArray()) { String one epsilonFrom(String.valueOf(c), rules); for (char d : one.toCharArray()) { if (result.indexOf(String.valueOf(d)) 0) result.append(d); } } return result.toString(); }三段的顺序是有讲究的。第一段看似冗余因为subset本来就应该已经是闭包的但在主循环里如果你传进来的是手工指定的{3}这种非闭包集合少了这一段就会漏掉3 -ε→ …带出来的状态。第二段只走 a第三段补闭包这是标准定义的直接翻译。报告总结里说在读 a 的同时还需要分别在读 a 的前后分别调用读空的函数说的就是这件事只是当时没写成三段而是靠一个函数来回调逻辑上绕了一圈。参数说明subset是状态集合串letter是单个字母字符rules是产生式数组。返回空串表示这个子集在该字母下无路可走这个空串后面要当成一个合法的死状态处理不能当异常丢掉——这是报告里用例二专门要展示的情况。3.4 子集构造主循环去重键不稳定程序就转不完最后是把上面这些组装起来。主循环要做的事很简单从一个子集出发对字母表里每个字母算出 Ia如果 Ia 是新子集就入队直到队列空。// 主循环从 ε-closure({X}) 出发不断产生新子集直到收敛 MapString, String subsets new LinkedHashMap(); // 去重键 → 原始状态串 DequeString queue new ArrayDeque(); String start epsilonFrom(X, rules); subsets.put(sortKey(start), start); queue.add(start); while (!queue.isEmpty()) { String cur queue.poll(); for (char letter : alphabet) { // 遍历字母表 Σ String next moveThenClosure(cur, String.valueOf(letter), rules); String key sortKey(next); // 排序后做去重键 if (!subsets.containsKey(key)) { // 只处理没见过的子集 subsets.put(key, next); queue.add(next); } } } // 把状态串排序保证同一个集合永远生成同一个键 static String sortKey(String s) { char[] arr s.toCharArray(); Arrays.sort(arr); return new String(arr); }这里的sortKey是关键。如果你直接用HashSet.toString()当去重键同一个集合{1,3,5}在不同轮次可能被打印成[1, 3, 5]、[3, 1, 5]或者别的顺序containsKey就会认为它们是不同的子集于是无限入队、程序永远停不下来。我第一次跑的时候就是这样控制台刷屏十几秒还在跑最后靠手动 kill 才停下来。排序之后键就稳定了时间复杂度也可以接受——课程设计量级下排序开销完全可以忽略。4. 代码复现三个测试用例从头跑到尾光看代码还是虚的得跑数据。报告里给了三个用例覆盖了 ε 链、自环、空集子集、有终态但分支少这几种情况我按上面的写法重新推了一遍把每一步的结果都记下来方便你对照自己的程序输出。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第一步先求ε-closure(X)X 走 ε 到 55 走 ε 到 11 没有 ε 出边所以S0 {X,1,5}。接下来对 S0 分别读 a 和 b按ε → 字母 → ε三段走起始子集读 a 后读 b 后S0 {X,1,5}{1,3,5} → S1{1,4,5} → S2S1 {1,3,5}{1,2,3,5,6,Y} → S3{1,4,5} → S2S2 {1,4,5}{1,3,5} → S1{1,2,4,5,6,Y} → S4S3 {1,2,3,5,6,Y}{1,2,3,5,6,Y} → S3{1,4,5,6,Y} → S5S4 {1,2,4,5,6,Y}{1,3,5,6,Y} → S6{1,2,4,5,6,Y} → S4S5 {1,4,5,6,Y}{1,3,5,6,Y} → S6{1,2,4,5,6,Y} → S4S6 {1,3,5,6,Y}{1,2,3,5,6,Y} → S3{1,4,5,6,Y} → S5七个子集全部闭环没有一个引向新子集收敛。注意 S3 读 a 之后还是 S3这不是写错了——{1,2,3,5,6,Y}里 1 走 a 到 3、3 走 a 到 2、5 走 a 回到自己、6 走 a 回到自己而 2 和 Y 本身又各自被 ε 链带着回到了这个集合里所以结果就是它自己。这种自己指向自己的情况在实际 NFA 里很常见程序里必须能正确识别成同一个子集否则就会无限产生新子集。4.2 用例二空集子集是怎么冒出来的第二个用例的状态集是{0,1,X,Y}产生式只有五条(X,ε)→0 (0,ε)→Y (0,a)→1 (0,b)→1 (1,a)→0ε-closure(X) {X,0,Y}这是 S0。S0 读 a 得到{1}读 b 也得到{1}所以 S1 是{1}。S1 读 a 走1 -a→ 0再做闭包得到{0,Y}也就是 S2。关键在于 S1 读 b状态 1 只有一条 a 弧没有任何 b 弧所以 move 的结果是空的ε-closure(∅)按定义还是空集。子集读 a读 b{X,0,Y}{1}{1}{1}{0,Y}∅{0,Y}{1}{1}∅∅∅报告里那句空代表状态子集为空的情况指的正是这里。空集子集在理论上对应 DFA 里的死状态是合法且有意义的不能因为它是空串就跳过不处理。很多实现就是在这里直接if (next.isEmpty()) continue;结果 DFA 少一个状态后面做最小化或者模拟匹配的时候行为就不对了。4.3 用例三有终态但只有四个子集第三个用例状态集{X,1,2,3,Y}(X,ε)→1 (1,a)→1 (1,b)→1 (1,ε)→2 (2,b)→3 (3,a)→Yε-closure(X) {X,1,2}是 S0。往下推子集读 a读 b{X,1,2}{1,2} → S1{1,3} → S2{1,2}{1,2} → S1{1,3} → S2{1,3}{1,Y} → S3{1,2} → S1{1,Y}{1,2} → S1{1,2} → S1四个子集就收敛了比用例一少一半。这个用例的价值在于它有 Y新终态可以验证终态是否被正确带进子集——S3 {1,Y}里包含 Y说明含终态的子集能被识别出来后面判断接受性就靠这个。4.4 三个能固化成断言的校验点跑完之后我一般会留三个检查下次改代码直接对子集总数对得上用例一 7 个、用例二 4 个、用例三 4 个。数量不对八成是去重键不稳定或者空集被跳过了。每个子集读完字母表都有落点哪怕落点是空集也要有记录。如果某个子集读某字母后直接抛出异常或者返回 null说明moveThenClosure里对空串没做处理。ε-closure 的幂等性对任意子集求两次闭包结果必须和求一次完全一样。这条能抓出忘了把自己加进去和ε 环没去重两类问题。5. 避坑与常见问题五条让我返工的记录这一节写的是真出过问题的五件事每条都按看到什么现象、根子上是什么原因、怎么改来写。你在自己实现的时候大概率会撞上其中两三条。5.1 递归读空链式结构上少状态现象测试用例一里ε-closure(X)出来是{X,5}少了 1但单独对 5 求闭包又能正确得到{5,1}。原因递归版RestltList里string ...改的是当前栈帧的局部变量然后调用RestltList(string, strings)却没接返回值。下一层递归里继续拼的字符只存在于下一层的局部变量中往上一层返回时被丢弃了。链只有一层的时候碰巧能对链长到两层就断。解决要么把递归改成return RestltList(state, rules);让结果一层层回传要么干脆换成 3.1 节的游标版。游标版更好因为它顺手解决了 ε 环的问题。5.2 状态名一超过一个字符charAt 全部错位现象把测试数据里的1改成q1程序不报错但求出来的子集莫名其妙读 a 之后目标状态变成了一堆括号和逗号。原因产生式用(1,a)→3这种固定格式字段全靠charAt(1)、charAt(3)、charAt(6)定位。状态名变成两个字符整条串的每个位置都往后挪了一格charAt(6)取到的就不再是终点。解决解析和取值分开。读取的时候用split或者正则一次性拆成源状态 / 标记 / 目标状态三个字段存成对象后面全部按字段访问不再碰下标。课程设计报告里用 charAt 是因为例子都是单字符能跑通就行但如果你想把这份代码留下来复用这一步值得花半小时改掉。5.3 空闭包把自己漏了现象ε-closure(3)返回空串但 3 明明有一条(3,a)→2出边按定义 3 自己应该在闭包里。原因写循环的时候只遍历产生式找 ε 弧忘了闭包定义的第一条是状态自身。当某个状态没有任何 ε 出边时循环一次都不进结果就是空。解决函数入口先把起点本身塞进结果容器再开始扫产生式。用字符串实现的时候就是StringBuilder sb new StringBuilder(state);用 Set 实现就是set.add(state);。这一行看着不起眼但漏掉之后所有只经过一条 a 弧的状态都会丢。5.4 子集去重键不稳定主循环停不下来现象程序跑到第三个用例还在刷屏控制台一直在输出看起来差不多的子集等半分钟也没结束。原因用HashSet.toString()或者直接拿未排序的状态串当 Map 的 key。{1,3,5}和{3,1,5}在逻辑上是同一个集合但字符串不相等containsKey判成新子集于是又入队又展开又产生更多顺序不同的等价串。解决入 Map 之前先把字符数组排序再拼回字符串保证同一个集合只有一个键。这一步开销很小但直接决定了程序能不能收敛。另一个办法是用TreeSet存状态它的toString天然有序效果一样。5.5 新初态 X 只连一个原初态多初态 NFA 直接算错现象用例一、二、三都能跑对但换成一个有两个初态的 NFA结果里有一半子集消失了。原因报告里作者自己也说了X 和 Y 都固定连接到那一个节点并将其作为状态转移函数写在自动机里。这是为了省事做的简化——只给 X 连一条 ε 弧到某一个原初态。原 NFA 只有单个初态时没问题一旦有多个初态X 就只覆盖了其中一个另一个初态及其后续状态永远进不了子集。解决X 到原初态集的每一条 ε 弧都要显式写进产生式数组。比如原初态是{1,4}那就要同时有(X,ε)→1和(X,ε)→4。这一条改起来只要两行但如果不改程序的支持任意 NFA就是假的。6. 把大函数拆碎的收益一个可以复用到别处的套路回过头看这份课程设计报告里最有价值的不是那些具体代码而是作者在总结里写下的那句当一个功能比较难以实现的时候可以把它再分成几个模块来写。他当时卡在一个状态子集既要想 a 弧又要考虑前后 ε上纠结了很久最后是在资料里看到可以先写两个函数分别读字母表和读空求子集的时候按读空、读 a、再读空来写才一下通了。这个套路的通用性比 NFA 本身大得多。任何看起来要在一个循环里同时处理两件事的场景先问一句这两件事能不能拆成两个各自只做一件笨事的函数拆开之后每个函数的输入输出都能单独测出问题的时候定位范围就从整个算法缩小到一个 if 判断。我后来做词法分析、做表达式求值、甚至做配置文件合并用的都是同一个思路先把原子动作写死再用组合函数把它们串成流程最后才写驱动循环。如果这份报告你只打算带走一样东西我建议带走三行骨架// 原子动作一沿 ε 展开不做别的 String epsilonFrom(String state, String[] rules); // 原子动作二只沿某个字母走一步绝不碰 ε String moveOn(String states, String letter, String[] rules); // 组合ε → 字母 → εIa 就这么来 String moveThenClosure(String subset, String letter, String[] rules);我自己有个习惯凡是写这种看起来要递归、要嵌套、要维护一堆状态的算法先在纸上把原子动作列成两三行函数签名签名写不出来就说明还没想清楚绝不开编辑器。这个习惯是被坑出来的早年间写一个类似的闭包算法直接上手堆了一个两百行的嵌套循环跑出来的结果时对时错改了两天最后推翻重写重写只用了四十分钟。从那以后我每次动这种算法都强制先写签名、先拿一个小用例手推一遍、确认每一步的中间结果能对上才动手敲代码。这份课程设计报告里那三个测试用例其实就是干这个用的——用例一验 ε 链和自环用例二验空集用例三验终态传递三个都过算法基本就站住了。报告本身还带了完整的源码附录和需求、概要、详细设计的分层描述对着里面的产生式格式和函数划分看一遍再配合前面几张子集推导表自己重写一遍大概一个晚上能通。希望帮到你。本文还有配套的精品资源点击获取