简介这份课程设计报告面向计算机专业学生与编译原理初学者聚焦有限自动机中空闭包 ε-closure(I) 的算法落地帮助读者把课堂上的集合推导转化为可运行的 Java 程序并配套完整的状态转换图绘制方案。包内共 1 个 docx 文件约 177KB按需求分析、概要设计、详细设计、测试与分析、用户使用说明、总结、参考文献与附录源代码的顺序展开既可直接作为课程设计模板参考也可用于理解 NFA 求子集与读空的实现细节。报告中给出了数组、图与哈希表的数据结构选型拆分出前端输入、后台处理、读空、读字母表与状态子集扩展等模块并说明对初态 X 递归求空闭包、再用静态字符串逐层累积结果的思路测试部分以两组含 ε 弧的自动机实例演示所有状态子集及其空闭包输出并讨论状态节点布局的通用性。已有 1287 人学习下载适合需要对照代码复现算法、撰写报告或备考编译原理的学习者参考。1. ε-closure 不是“多走几步空弧”而是子集构造法的唯一动力源很多人第一次写 ε-closureI脑子里想的都是个体力活把所有 ε 弧走一遍把能到达的状态塞进集合收工。真拿 Java 去实现一个能处理任意 NFA 的空闭包程序时才会发现难的不是“走一遍”而是走完之后这批集合怎么喂给子集构造法让 NFA 一步步塌缩成 DFA。编译原理课上那句“ε-closure(I) 是从 I 出发经任意条 ε 弧可达的状态集合”省掉了一个关键事实它才是子集构造每一步的动力来源move 只负责吃一个字母剩下的“把新状态补全”全靠闭包兜底。少了这一步NFA 转 DFA 立刻退化成一比一映射所有分支当场消失。这份课程设计报告把实现拆成三个函数读空的、读字母的、把所有状态子集一次性结算闭包的循环。三层正好对应原理到代码的距离下面从机制往回推看每一步为什么必须这么写以及哪些写法会在你自认为跑通的时候悄悄翻车。2. 空闭包到底在算什么可达性、虚拟首尾状态与存储选型2.1 从数学定义到队列闭包本质是一次带环的可达性搜索ε-closure(I) 的完整定义是 I ∪ { t | 存在 s ∈ I使 s 经任意条 ε 弧可达 t }。这里有两个容易被读漏的词“零条”和“任意条”。零条意味着自反性I 里每个状态无条件属于自己的闭包任意条意味着传递性走一步、走十步、绕着环走一圈再回来都算。两条合起来闭包就是一个包含自身的传递闭包换成人话说从 I 出发沿 ε 边走能踩到的所有点。这个定义天然适合图搜索不适合纯递归展开。原因很直接ε 弧可以成环比如 5 --ε-- 1、1 --ε-- 5 这种裸递归会沿着环无限展开直到栈溢出。合格写法是维护一个 visited 集合让“已收录”这件事同时承担两个职责——去重以及判断是否需要继续从该点扩散。// 邻接表状态 - (字母 - 可达状态集合)ε 也当作一个特殊字母存在里面 MapString, MapString, SetString delta; SetString epsilonClosure(SetString start) { // 零条 ε 弧起点自身无条件属于闭包先全部放进去 SetString closure new HashSet(start); DequeString stack new ArrayDeque(start); while (!stack.isEmpty()) { String s stack.pop(); // getOrDefault 两层兜底避免没有出边的状态触发 NPE SetString next delta.getOrDefault(s, Collections.emptyMap()) .getOrDefault(ε, Collections.emptySet()); for (String t : next) { // add 返回 true 表示首次收录才需要继续从 t 往外扩 if (closure.add(t)) { stack.push(t); } } } return closure; }这段代码里最关键的一行是closure.add(t)。它返回布尔值为 false 说明 t 已经在闭包里可能是自反性放进来的也可能是别的路径先到一步。用返回值决定要不要入栈等于把“去重”和“剪枝”合并成一次操作不需要额外的 visited 数组。参数上start 传的是任意状态子集而不是单个状态因为闭包的定义域本来就是子集接口按定义域设计调用方就不用自己拆包。复杂度上看每个状态最多入栈一次每条 ε 弧最多被检查一次总代价是 O(|Q| |δε|)和图的广度优先遍历同一个量级。这一点很重要因为闭包在子集构造里会被调用几十上百次任何一次写成 O(|Q|²) 都会在后面成倍放大。2.2 引入 X 和 Y虚拟首尾状态解决了哪种边界问题NFA 允许多个初态、多个终态这两条自由带来的麻烦是子集构造需要一个唯一的起点还需要一个统一的接受判定。工程上最省事的做法是给自动机补两个虚拟状态X 和 Y然后从 X 拉一条 ε 弧到每一个原初态从每一个原终态拉一条 ε 弧到 Y。补完之后收益立刻显现。第一个状态子集不再是“所有初态的并集再求闭包”而是干净利落的 ε-closure({X})一行代码的事。接受判定也不再需要拿子集去和终态集求交集只看这个子集里有没有 Y有就是接受状态没有就不是。X 和 Y 本身不消耗任何字母所以它们不会污染 move 的结果只参与闭包计算。报告里有一句很诚实的交代因为能力有限X 和 Y 被固定连到一个节点上并直接写进状态转移函数。这个简化会让自动机的通用性打折——它只对“初态唯一”或“终态唯一”的 NFA 成立遇到多初态输入会漏掉分支。但它同时揭示了一个真实的设计动机X、Y 不是算法的一部分是接口适配层适配层写死到什么程度取决于你愿意为通用性付出多少解析复杂度。2.3 状态、字母表、产生式用什么存三种结构各管一段报告里说用了数组、图、哈希表这个组合不是随手凑的各自对应一个层次。产生式用String[]存是因为输入来自文件一行一条最省事的序列化方式是原样保留字符串图用邻接表存是因为算法要反复问“从状态 s 出发走符号 a 能到谁”这个问题在邻接表上是 O(1) 查表在字符串数组上要扫全表哈希表用HashSet存状态子集是因为闭包的语义就是集合去重必须免费。存储方式承担的角色主要代价String[]产生式数组文件读入后的原始形态每次查询要线性扫描字段靠位置解析Map状态, Map符号, Set状态运行期的自动机本体建表有一次转换开销SetString状态子集与闭包结果字符串哈希比 BitSet 慢表格右侧那一列才是真正值得警惕的地方。产生式数组的线性扫描在状态数上到几十以后就开始拖慢整体而字符串哈希在子集数量上千时会明显不如位图。这两处代价在课程设计的规模下完全看不出来所以很容易被当成“没问题”的写法带进更大的项目里。3. 子集构造的主循环Ia 为什么必须“读空—读字母—再读空”3.1 move 与闭包的复合Ia 的推导以及在循环里重复读空的收益Ia 的定义只有一行Ia ε-closure(move(I, a))。拆开看是两段动作先对子集 I 里每个状态走一条 a 弧收集所有落点得到 move(I, a)再对这堆落点求一次 ε 闭包。为什么第二段闭包不能省因为 a 弧落点可能还挂着 ε 弧那些“顺带能到”的状态同样属于下一步的可达集合漏掉它们就会在后续某个字符上丢分支。那为什么不需要在 move 之前也读一次空这涉及子集构造算法必须维持的一个不变量参与运算的每一个状态子集本身已经是闭包。初始子集 ε-closure({X}) 天然满足后续每个 Ia 按定义也满足归纳下来所有子集都闭合。既然 I 已经闭合再对它求一次闭包就是恒等操作——闭包是幂等的ε-closure(ε-closure(I)) 等于 ε-closure(I)。这一点直接解释了报告里那个“读空—读 a—读空”的写法为什么逻辑上成立但没有必要前一次读空是防御性的它保证即便调用方递进来一个裸子集用户手动指定某个状态子集求 Ia 的情况结果依然正确代价是每个子集每个字母都多一次遍历。这类多余操作在课程设计里无所谓在正经构造器里会被去掉。看清这个取舍比死记住三步顺序有用得多。3.2 未标记子集表worklist 怎么保证一定收敛子集构造最经典的写法是维护两张表一张存已经处理过的子集一张存发现了但还没展开的子集。每次从后者取出一个标记然后对字母表里每个字符算 Ia新子集如果没出现过就塞回后者。这个过程一定终止因为子集只能取自 Q 的幂集幂集有限。SetSetString allSubsets new LinkedHashSet(); // 已发现子集Linked 保序 DequeSetString worklist new ArrayDeque(); // 待展开子集 SetString init epsilonClosure(Set.of(X)); // 第一个子集X 的闭包 allSubsets.add(init); worklist.push(init); SetString alphabet Set.of(a, b); // 字母表不含 ε while (!worklist.isEmpty()) { SetString I worklist.pop(); for (String a : alphabet) { SetString moved new HashSet(); for (String s : I) { // move(I, a)只走一条 a 弧 moved.addAll(delta.getOrDefault(s, Collections.emptyMap()) .getOrDefault(a, Collections.emptySet())); } if (moved.isEmpty()) continue; // 空子集不构造也没有闭包 SetString next epsilonClosure(moved); // 落点再求闭包 if (allSubsets.add(next)) { // add 返回 true 说明是新子集 worklist.push(next); } } }这里allSubsets.add(next)的返回值同样被当成判重信号用和闭包里的closure.add(t)是同一个套路集合的 add 天然告诉你“这个元素以前在不在”。moved.isEmpty()那一行是必须的因为空集求闭包仍是空集把空集塞进集合会让后续遍历多出一堆无意义的空壳还会在打印结果时冒出一行[]报告里那个“空代表状态子集为空的情况”根子就在这里。LinkedHashSet而不是HashSet是为了让子集的发现顺序稳定。这个细节在调试阶段价值极大哈希顺序每次运行都可能不同两组结果按行比对时你会以为算法错了其实是打印顺序变了。3.3 状态爆炸的上界与工程上该在哪里踩刹车理论上n 个状态的 NFA 最多能长出 2^n 个 DFA 状态这个上界不是吓唬人的像(a|b)*a(a|b)^k这类结构就能逼近它。课程设计里状态数通常个位数随便怎么写都能跑一旦换到词法分析器真实规模关键字、标识符、注释、字符串十几条规则拼起来的 NFA子集数量很容易上到几百。所以实现层面有三处值得提前留好接口状态子集用BitSet而不是HashSetString哈希开销直接降一个量级子集判重可以先算哈希再比对避免集合之间反复逐元素比较构造过程做成惰性的别一上来就把所有子集全展开再打印只查某个子集的闭包时没必要把整张表建完。报告里那段mapmax循环就是典型的“全量结算”先有全部子集再逐个求闭包规模小时它是最好读的写法规模大时它是第一个该改的地方。4. 源码拆解三个核心函数真实的边界在哪里4.1 RestltList 的递归为什么“只吃到一层”报告里对新初态 X 读空的函数是这样写的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; }两个问题叠在一起。第一函数只盯着结果串的最后一个字符做延展也就是说一次调用只顺着“末尾状态”的一条出边走如果闭包需要从中间某个状态分叉它看不到。第二递归那一行的返回值被直接丢弃而 Java 参数是值传递string 只修改当前栈帧里的局部变量递归里追加的字符根本回不到外层。有意思的是这两个 bug 互相抵消了一部分因为返回值丢了递归第二层不再往 string 里加东西所以即便 ε 弧成环结果串也不会无限增长。它“碰巧”不会栈溢出但代价是闭包只吃到一层多级 ε 链X→1→2→3会算漏。报告正文里说“定义了一个静态变量字符串来接收它”可代码里用的是参数传递说明当时试过静态变量但最终版本没落实。这类“注释和代码对不上”的地方是读别人的课程设计代码时最该盯紧的位置。4.2 RestltListA 的接口错配传进来的是子集还是单个状态public static String RestltListA(String string, String s, String[] strings) { String resultA ; for (int i 0; i strings.length; i) { // 这里拿整个 string 去和一个字符比较 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.equals(charAt(1))这一行是死路。如果调用方按名字传进来一个子集串123它永远不可能等于任何单个字符函数恒返回空串。也就是说这个函数实际只能接受单个状态它是 move 的单步版本不是子集版本。这恰好点出一个接口设计原则move 的最小职责是“一个状态、一个字母、一条出边”子集的循环应该放在调用方。报告的设计说明里写的是“对传入的状态子集进行循环然后再嵌套循环产生式”贴出来的代码里并没有那层外层循环说明贴的是简化版或早期版。函数边界按最小职责切是让逻辑变简单的关键——切对了每个函数只看一件事切错了就得在函数内部判断“你传给我的到底是一个状态还是一串状态”判断逻辑本身又会成为新的 bug 来源。4.3 DuKong 的动态 length 与 mapmax 的哈希顺序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; }i result.length()在循环体内部因为result 而不断变大新追加的字符会被同一个循环继续访问到形成一种“边遍历边扩散”的效果。这确实能把多级 ε 链吃干净但它依赖两个隐式前提String 不可变所以每次都生成新对象长度每次重新求所以循环上界会跟着长。只要有人手贱把它优化成int len result.length()缓存起来功能立刻退化。这种写法本质上是把“队列扩散”伪装成了“循环边界动态变化”可读性和可维护性都很差。正规写法是两个集合轮换frontier 放当前待处理状态next 放本轮新发现的状态处理完交换引用。这个结构一眼就能看出扩展了几层也方便加日志。同一段配套代码里还有HashMapSetString, SetString mapmax遍历时输出顺序不稳定。调试期拿它和标准答案对行会得到“结果一样但顺序全乱”的假象。换成LinkedHashMap或者输出前按子集字符串排序问题立刻消失。4.4 重写一版闭包、move、子集构造三段式把上面这些东西拼起来一个职责清晰的版本长这样// 产生式解析成结构不再靠 charAt 定位 record Edge(String from, String symbol, String to) {} // ① 闭包带 visited 的迭代扩散天然防环 SetString closure(SetString start, ListEdge edges) { SetString result new HashSet(start); DequeString stack new ArrayDeque(start); while (!stack.isEmpty()) { String s stack.pop(); for (Edge e : edges) { if (e.from().equals(s) ε.equals(e.symbol()) result.add(e.to())) { stack.push(e.to()); } } } return result; } // ② move只走一条指定字母的弧不含闭包 SetString move(SetString I, String a, ListEdge edges) { SetString result new HashSet(); for (Edge e : edges) { if (I.contains(e.from()) a.equals(e.symbol())) { result.add(e.to()); } } return result; } // ③ Ia两段复合顺序不能反 SetString ia(SetString I, String a, ListEdge edges) { return closure(move(I, a, edges), edges); }三段的职责边界很清楚closure 只认 εmove 只认指定字母ia 负责复合。这样写还有个额外好处——求“给定状态子集的空闭包”这个需求变成一次closure(I, edges)调用不需要先跑完整个子集构造。报告里要求“输出给定状态子集的空闭包”用这套结构是常数级集成成本用原来那套“先算全部子集再查表”的做法用户只想知道一个子集程序却把整张表算完属于典型的过度计算。5. 避坑与排查字符串建模踩出来的五个坑5.1 递归读空只多了一层现象输入(X,ε)→1 (1,ε)→2 (2,ε)→3期望闭包{X,1,2,3}实际输出{X,1}或者只多一个状态。 原因递归调用RestltList(string, strings)的返回值没有被接住Java 值传递下string 只改当前栈帧的局部变量深层追加结果全部丢失。 解决要么改成传一个SetString或StringBuilder这类可变容器进去让每一层都往里写要么让每层返回自己这一层的并集由调用方合并。静态变量也能凑合但并发和多次调用之间必须手动清空是个更隐蔽的雷。5.2 状态名一旦超过一位整个解析全错位现象状态名从1,2,3换成q1,q2,q10之后程序要么报StringIndexOutOfBoundsException要么算出一堆不存在的状态。 原因解析靠固定下标charAt(1)取左部状态、charAt(3)取符号、charAt(6)取右部状态这套下标只对(1,a)→3这种单字符格式成立。右部一旦是两位数第七个字符只取到了第一位。 解决先把产生式按→和,拆开解析成(from, symbol, to)三元组再进算法。解析和算法分离是硬要求别让下标假设渗进计算逻辑。5.3 换个循环写法结果就变现象把for (int i 0; i result.length(); i)改成先缓存长度原本能算出的多级闭包突然只算出一级。 原因原写法依赖“循环过程中字符串动态变长、上界每次重算”这个副作用来实现分层扩散本质是把队列逻辑藏在了循环边界里。 解决显式用 frontier 和 next 两个集合或者用队列。把“这一步处理谁、下一步处理谁”写明白别让结果依赖于循环条件的求值时机。5.4 同一份输入两次运行打印顺序不同现象结果集合内容完全一致但每次运行的输出行顺序都不一样人工对答案时误判成算错。 原因HashMap、HashSet的迭代顺序由哈希值决定不做任何保证子集作为 key 存进去以后遍历顺序自然漂移。 解决用LinkedHashMap、LinkedHashSet保留插入顺序或者在输出前把子集转成排好序的字符串再打印。调试期稳定顺序能省下大量误判时间。5.5 ε 环把程序拖死现象自动机里存在1 --ε-- 2、2 --ε-- 1这样的环程序要么卡住不动要么内存一路涨到崩。 原因闭包扩展时没有 visited 集合沿环无限展开。用字符串拼接实现的版本更糟串会无限变长直到 OOM。 解决闭包一律用集合承接结果靠add的返回值判断是否首次访问。凡是“沿边走”的逻辑先问一句“环上会不会重复进来”答案是不会才可以省掉 visited。6. 设计取舍字符串建模、固定 X/Y 与全量计算的代价回头看我经手过的这类实现最值得记住的不是算法本身而是三处当时觉得无所谓、后来必须还债的取舍。第一处是拿字符串当数据结构。产生式用String[]存、状态子集用String拼、闭包结果还是String好处是写起来快、打印出来直接能看坏处是所有语义都退化成了字符位置。charAt(6)这类代码在状态名单字符时完全正确一旦规模上去就全线崩。这不是水平问题是建模层级选低了算法层需要的是“状态、符号、转移”三个概念而字符串只提供“字符”一个概念中间那层映射得靠人脑维护人脑一松懈就出错。第二处是 X、Y 固定连到一个节点。这个简化让“补虚拟首尾状态”从一次遍历退化成两行硬编码代价是自动机丧失了多初态、多终态的通用性。报告里那句“因为能力有限”很坦诚但它也提示了一个更普遍的现象接口适配层的偷懒往往被误认为算法层的简化。真正的做法是读入时就把 X 连到全部初态、全部终态连到 Y这一步多写十行后面所有算法都不用再关心“初态到底有几个”。第三处是“先算全量再查表”。把全部状态子集求出来、再逐个求闭包、存进 map 打印逻辑上是闭合的读起来也顺。但它把两个需求的成本绑在了一起用户只查一个子集的闭包程序却付了全量构造的代价。这种绑定在课程设计里看不出来在真实工具里就是响应时间的分水岭。惰性构造、按需展开是同一个算法在不同规模下的两种正确形态。从那以后我每次写闭包类算法都强制先问三个问题结果用什么容器装、环上怎么保证不重复进、这个函数的最小输入到底是一个元素还是一个集合。三个问题回答清楚代码基本一次就能跑对回答不清楚就会出现“算出来了但只对了一半”这种最难查的状态。希望这些踩坑记录能帮你少走一遍我走过的弯路把精力留给真正值得琢磨的子集构造和状态爆炸上。本文还有配套的精品资源点击获取
