企业官网建设流程全解析

简介：这是一份面向编译原理课程设计的Java程序实现报告，聚焦如何对任意输入的非确定有限自动机（NFA）求解状态子集I的空闭包ε-closure（I），并利用状态转换图展示自动机结构，帮助读者从工程角度理解NFA与子集构造法的基础概念。报告完整覆盖需求分析、概要设计、详细设计、测试与分析、用户使用说明、总结与附录源代码，核心模块包括NFA输入解析、基于递归和数组/哈希表的闭包计算、状态子集扩展以及状态转换图绘制；同时以具体测试数据说明算法输出效果，便于读者复现和二次开发。资源为单个Word文档（docx），仅1个文件，压缩包大小约177KB，文本与代码均集中在同一文档中，查阅排版都很方便。目前已有1284人学习浏览，适合编译原理课程设计、实验报告撰写或自学NFA空闭包算法时参考。

1. ε-closure 是什么：NFA 转 DFA 绕不开的十几行代码

ε-closure（ε 闭包）是编译原理课程设计里 NFA 转 DFA 的第一步，也是整个子集构造法的地基。标题里的「（I）」通常表示这是第一阶段任务：先单独把闭包运算用 Java 实现出来，后面才接得上 move 运算和状态合并。这个算法的核心循环压缩到极致只有十几行，但我在答疑里见过最多的翻车现场都发生在这个函数上——程序跑起来不退出、闭包结果少了状态、和手算对不上。问题大多数不是不会写代码，而是对「经过 0 条 ε 边也算闭包的一部分」这半句话理解得不到位。这篇文章把建模选型、BFS/DFS 两种实现、五个高频坑一次讲完，适合正在做编译原理课程设计的学生，也适合手写词法分析器或自动机工具的从业者参考。

2. 动手前先建模：NFA 状态和 ε 边在 Java 里怎么存

2.1 为什么必须先求 ε-closure：子集构造法把它当原子操作

NFA 和 DFA 的本质差别在于 ε 边：NFA 允许不消耗任何输入字符就从一个状态「凭空」走到另一个状态。DFA 不允许这种情况，所以把 NFA 转成 DFA 时，必须把所有「不消耗字符也能到达」的状态事先合并成一个大状态，这个合并动作就是闭包。

子集构造法的标准流程是：对当前 DFA 状态（一个 NFA 状态集合 T），先做 move(T, c) 得到「从 T 中任一状态出发、读入字符 c 能直接到达的 NFA 状态集合」，然后对这个集合求 ε-closure，结果才是真正的 DFA 目标状态。可见闭包是 move 之后必须紧跟的一步，这个调用顺序决定了它会被频繁执行——如果 NFA 状态有成百上千个，closure 的性能会直接影响整个转换过程的耗时。

所以课程设计把 ε-closure 单独拎出来做第一阶段，原因很实在：它是一个独立可测的纯函数，输入输出都是状态集合，不依赖任何全局状态。换句话说，哪怕后面 DFA 构造代码还没写，闭包函数已经可以单独测试和验收。这也是这篇文章先讲它、不急着讲完整 NFA 的原因。闭包这一层做扎实了，后面所有阶段都在这个地基上盖楼。

2.2 状态用 Integer 还是自定义类：id 规则决定后面所有代码

动手前要定的第一个问题不是算法，是状态用什么类型表示。我见过有人把状态封装成 State 类，带 name 和 isAccept 字段，然后放进 HashSet 里求闭包，结果怎么跑结果都不对——因为没重写 hashCode 和 equals。这不是玄学，是 HashSet 的去重完全依赖这两个方法，不重写的话两个「看起来一样」的 State 对象会被当成不同元素，闭包结果就时对时错。

我自己做这个题目时，状态一律用 Integer。理由有三条：第一，Integer 的 hashCode 和 equals 原生正确，集合去重在闭包这种高频操作里不会出幺蛾子；第二，状态 id 从 0 开始连续编号，后面可以用 List 按索引直接取某个状态的 ε 边集合，连查 Map 的开销都省掉了；第三，课程设计报告里画 NFA 图时，节点编号和代码里的 id 一一对应，答辩讲起来省很多口舌。

还有同学用 String 表示状态，比如 q0、q1。字符串可读性好，但每次集合操作都要做字符串内容比较，而且从正则表达式读入后还要额外解析。除非题目明确要求输出带前缀的状态名，否则不建议这么做。真要输出 q0 这种名字，打印时把 id 转一下字符串就行，存储和运算仍然用 Integer。

那什么时候需要自定义类？只有当 NFA 状态本身携带额外属性（比如 Thompson 构造法里节点的 out 指针）时才有必要。那种场景下我的做法是：状态类只存 id 和属性，equals 和 hashCode 仍然只基于 id，并且把 ε 边单独抽出来存，不塞进状态对象里。这样既保留对象的表达能力，又不干扰集合运算。

2.3 三张表存 ε 边：邻接表、邻接矩阵与 Map 的取舍

ε 边本质上是一个有向图的边集合，存储方式常见有三种。课程设计报告里如果能把选型讲清楚，比贴大段代码更能拿分。

第一是邻接表，用List<Set<Integer>>。下标是源状态 id，值是从该状态出发、经过一条 ε 边能直接到达的目标状态集合。这是最常用的方案，因为闭包运算的核心操作是「遍历某个状态的所有 ε 边目标」，邻接表恰好把这个操作的时间复杂度压到 O(出度)。

第二是邻接矩阵，用boolean[][]。查「状态 i 到状态 j 有没有 ε 边」是 O(1)，但 NFA 的 ε 边通常很稀疏，几百个状态的矩阵大部分格子是 false，空间浪费严重，遍历一个状态的全部出边还得扫一整行。

第三是Map<Integer, Set<Integer>>。好处是状态 id 不要求连续，适合从文本文件读入、状态编号不规则的情况；坏处是每次 get 都有装箱和哈希开销，而且遍历顺序不确定，报告里做「手算 vs 程序输出」的对照表时比较麻烦。

选定存法后，初始化代码通常长这样：

// 先按状态数建好列表，再逐条填入 ε 边 List<Set<Integer>> epsilonTransitions = new ArrayList<>(); for (int i = 0; i < numStates; i++) { epsilonTransitions.add(new HashSet<>()); } // 从状态 0 到状态 1 有一条 ε 边 epsilonTransitions.get(0).add(1);

注意不要用 Arrays.asList 之类的方式一次性初始化整个列表——每个状态需要独立的 HashSet 实例，共用一个集合会导致一个状态的出边出现在另一个状态下面。这个错很隐蔽，但后果是闭包结果莫名多出一堆状态。我选List<Set<Integer>>而不是List<List<Integer>>还有一个原因：闭包里要去重，如果改用 List 存出边，同一状态有两条 ε 边时（语法上允许），BFS 会把同一目标入队两次，结果虽然不受影响，但队列里会有冗余，状态多时性能肉眼可见地下降。

另外还有一种常见的坏味道：把 ε 边挂在状态对象内部，比如 State 类里放一个List<State> epsilonOut。这样类图好看，但闭包函数每次取边都要先拿到状态对象，测试时构造人工 NFA 很麻烦，而且一旦状态对象被复用，边表会被意外共享。所以我习惯把边表独立成上面的结构，让闭包函数只依赖这张表。单元测试可以直接手工搭表，不用走正则到 NFA 的生成流程，定位问题快得多。

3. 核心算法：用 BFS 和 DFS 分别实现 ε-closure

3.1 BFS 版本：队列加一个集合，十五行核心代码

闭包的直观定义是：从初始集合出发，沿着 ε 边能走到的所有状态都算进来。这天然就是一张图的遍历问题，BFS 是最不容易写错的解法。核心代码如下：

import java.util.*; public class EpsilonClosure { // epsilonTransitions.get(s) 返回从状态 s 出发、经过一条 ε 边可直达的状态集合 private final List<Set<Integer>> epsilonTransitions; public EpsilonClosure(List<Set<Integer>> epsilonTransitions) { this.epsilonTransitions = epsilonTransitions; } // 对状态集合求 ε 闭包：结果包含初始集合自身（0 条 ε 边） public Set<Integer> closure(Set<Integer> states) { Set<Integer> result = new HashSet<>(states); // 闭包包含自己 Deque<Integer> queue = new ArrayDeque<>(states); while (!queue.isEmpty()) { int s = queue.poll(); for (int next : epsilonTransitions.get(s)) { if (result.add(next)) { // 新状态：加入结果并入队 queue.offer(next); } } } return result; } // 对单个状态求闭包，是集合版本的特例 public Set<Integer> closure(int state) { return closure(Collections.singleton(state)); } }

这段代码最值得讲的是 result 集合身兼两职：它既是返回值，又充当 visited 集合。result.add(next)返回 true 说明 next 是第一次出现，才需要入队；返回 false 说明已经访问过，直接跳过。这样省掉了一个独立的 visited 结构，也让「每个状态最多入队一次」这个性质一目了然。

参数选择上有两个细节。队列用 ArrayDeque 而不是 LinkedList，因为这里只需要队尾入队、队头出队，ArrayDeque 的均摊开销更小，而且是答辩时能说出口的细节。传入的 states 不要直接拿来当 result 用——函数语义是返回一个新集合，不是原地修改入参；如果调用方后续还要用这个集合（比如 move 的结果要复用），原地修改会让整个转换流程出错。

还有一种常见的错误实现：先把初始状态的 ε 边目标全部收集起来，再对这些目标递归扩展，结果初始集合本身没有先放进结果集，最后只能用特殊逻辑补救。BFS 版本用new HashSet<>(states)初始化就绕开了这个问题，也顺便保证了空集输入返回空集。状态数量大时可以在构造 HashSet 时给个预估容量，减少扩容次数，但这个题目规模一般几百个以内，不写也没关系。

3.2 DFS 版本：递归写法与告别栈溢出的改法

DFS 版本更短，也更贴近课本上对闭包的递归定义：closure(S) = S ∪ closure(S 的 ε 后继)。代码如下：

public Set<Integer> closure(Set<Integer> states) { Set<Integer> result = new HashSet<>(); for (int s : states) { dfs(s, result); } return result; } private void dfs(int state, Set<Integer> result) { if (!result.add(state)) { return; // 已访问过，包括环的情况 } for (int next : epsilonTransitions.get(state)) { dfs(next, result); } }

visited 检查放在递归函数的第一行，是必须的。如果漏掉，遇到 A→ε→B→ε→A 这种 ε 环，递归会无限下去，最终抛 StackOverflowError。检查放在递归之前而不是之后，保证环上的每个状态只被处理一次。

DFS 的问题在深链：如果 NFA 里有一条很长的 ε 链（比如上千个状态串联），递归深度跟链长成正比，Java 默认栈深大约几千层，碰巧能跑，再大一点就溢出。我的习惯是：课程设计这种规模用 DFS 没问题，但如果你处理的 NFA 是程序生成的、状态数不可控，直接用 BFS 版本更稳。非要用 DFS，就改成显式栈：

public Set<Integer> closureWithStack(Set<Integer> states) { Set<Integer> result = new HashSet<>(); Deque<Integer> stack = new ArrayDeque<>(states); while (!stack.isEmpty()) { int s = stack.pop(); if (result.add(s)) { for (int next : epsilonTransitions.get(s)) { stack.push(next); } } } return result; }

注意这段和 BFS 的差别：visited 检查在出栈时做，入栈时不做。这意味着同一个状态可能被压栈多次，但因为出栈时会去重，结果依然正确，只是极端情况下栈里会有重复元素。想彻底避免重复入栈，可以把 if 判断提前到压栈前，但那样需要额外的数组标记，代码就不如 BFS 简洁——这也是我推荐 BFS 的另一个原因。

3.3 对外接口与复杂度：单状态重载、缓存与校验

为了让调用方用得顺手，我一般会提供三个入口：集合版本、单状态版本，以及一个带缓存版本。单状态版本上面已经写了，就是包一层Collections.singleton。缓存版本长这样：

private final Map<Set<Integer>, Set<Integer>> cache = new HashMap<>(); public Set<Integer> closureCached(Set<Integer> states) { return cache.computeIfAbsent(new HashSet<>(states), this::closure); }

注意 key 一定要拷贝一份再放进 Map，否则调用方后续修改传入的集合，缓存里的 key 也跟着变，会出现「闭包结果突然变了」的灵异现象。但缓存要不要做，取决于 NFA 转 DFA 流程里同一个集合被重复求闭包的频率。课程设计规模下大概率不需要，加了缓存反而要操心内存；如果后面做完整子集构造法，同一批集合确实会被反复闭包，缓存能省不少时间。我一般先不加缓存，跑通流程后确认瓶颈在闭包时再补。

如果你的 NFA 来自正则表达式构造，边表下标和状态 id 的一致性特别容易出问题。有人先画图再写代码，图上的编号和 List 下标对不上，闭包结果自然对不上。建议构造 NFA 时加一个简单校验：

private void validate() { for (int i = 0; i < epsilonTransitions.size(); i++) { if (epsilonTransitions.get(i) == null) { throw new IllegalStateException("状态 " + i + " 的 ε 边集合未初始化"); } } }

接口确定后，一个完整的最小测试骨架：

public static void main(String[] args) { // 构造 NFA：0 --ε--> 1，1 --ε--> 2 List<Set<Integer>> eps = new ArrayList<>(); eps.add(new HashSet<>(Arrays.asList(1))); // 状态 0 的 ε 边 eps.add(new HashSet<>(Arrays.asList(2))); // 状态 1 的 ε 边 eps.add(new HashSet<>()); // 状态 2 没有 ε 边 EpsilonClosure ec = new EpsilonClosure(eps); System.out.println(ec.closure(0)); // 期望输出 [0, 1, 2] }

这个骨架跑通，说明数据结构和闭包函数的最小链路是通的。后面接 move 运算，只需把 move 结果传进 closure。复杂度方面，BFS 和 DFS 都是 O(V + E)，V 是状态数，E 是 ε 边数；每个状态至多入队或入栈一次，每条 ε 边至多被扫描一次。报告里写复杂度时配一句解释：visited 机制保证每个状态只处理一遍，所以不是 O(V*E)。答辩时老师大概率追问这一点，能答出来，这个阶段的区分度就出来了。

4. 五个最容易翻车的细节：从死循环到 move 与闭包的概念混用

以下五条按出现频率排序，全部来自实际答疑和报告批改现场。每条先说现象，再分析原因，最后给解决办法。

4.1 程序卡死不退出：ε 环导致的死循环

现象：程序跑起来之后不结束，CPU 占用拉满；递归版本则直接抛 StackOverflowError。这种问题在带 ε 环的 NFA 上必现，因为闭包遍历会在环上无限循环。

原因：NFA 里存在形如 A→ε→B→ε→A 的环。如果实现里漏了「已访问」标记，BFS 版本会把环上的状态反复入队，DFS 版本则无限递归直到栈溢出。

解决：任何版本的闭包都必须有 visited 机制。BFS 里让 result 集合兼任 visited（add 的返回值判断），DFS 里在递归函数第一行做result.add(state)检查。这两个写法都能保证环上每个状态只处理一次。如果担心环之外还有坑，也可以另加独立的 boolean[] visited 按状态 id 索引，语义更直白，代价是多一次数组访问。

4.2 闭包结果少了状态：自定义状态类的 hashCode 没写好

现象：手算 closure({A}) 应该得到 {A, B, C}，程序输出只有 {A}，或者偶尔缺 B 偶尔缺 C，看起来像随机出错。

原因：用了自定义 State 类放进 HashSet，但没有正确重写 hashCode 和 equals。两个内容相同的 State 对象被当成不同元素，集合去重失效。这种问题最难排查，因为它不影响编译，只影响运行结果。

解决：状态用 Integer，是最省心的路径。如果确实需要自定义状态类，遵守三条规则：equals 只基于 id；hashCode 只基于 id；id 一旦创建不可变。写完后用一个包含环的用例反复跑几次，结果稳定才算过。很多人把这条归为玄学，其实回到 HashSet 的实现原理看，每一步都是确定的。

4.3 返回结果丢了初始集合：漏了「0 条 ε 边也算」

现象：closure({A}) 返回 {B, C}，把 A 自己弄丢了。手算怎么算都对，程序怎么跑都不对。

原因：闭包的定义是「从初始集合出发，经过 0 条或多条 ε 边能到达的所有状态」。0 条 ε 边意味着初始集合里的每个状态都在闭包里。有些实现把闭包理解成「经过至少一条 ε 边能到达的状态」，于是求 closure({A}) 时只返回 ε 边目标集合，A 自己反被排除。

解决：result 初始化为new HashSet<>(states)，先把初始集合全部放进去。有个容易被忽略的细节：如果为了省内存而复用某个集合对象、每次先 clear 再往里面塞，空集输入就会出问题——clear 之后什么都没加，但返回的却是上一次的残留。最稳妥的就是new HashSet<>(states)一步到位，测试用例里显式包含「closure(空集) = 空集」这一条。

4.4 队列里出现大量重复状态：visited 标记时机不对

现象：结果是对的，但跑一个几百状态的 NFA 明显变慢，调试时打印队列，发现同一个状态出现了很多次。

原因：visited 标记在出队时才设置，而不是入队时。比如状态 X 有两条 ε 边都指向 Y，Y 第一次被遇到时已经入队，但还没出队，第二次遇到时标记尚未生效，Y 又被入队一次。队列越长，重复越多。

解决：用「入队前检查」代替「出队时检查」。BFS 版本里result.add(next)在 offer 之前执行，天然满足要求。如果用了独立的 boolean[] visited，就把visited[next] = true放在入队那一刻，不要放在 poll 之后。这两行代码的先后顺序看似无关紧要，实际上一个是 O(V+E)，一个在最坏情况下会退化成 O(V*E)。这属于典型的「结果对但效率错」，报告里写出来反而是加分项。

4.5 闭包结果和手算对不上：move 与 closure 被混成一步

现象：写完整 NFA 转 DFA 时，构造出的 DFA 状态表明显多出一些不存在的状态，或者少了一些状态。单独测闭包时全对，合起来就错。

原因：把「读入一个字符能到达的状态」和「再沿 ε 边扩展」混在一张表里算了。NFA 转 DFA 的两步必须分开：先 move(T, c) 得到直接目标集合，再对这个集合求闭包得到实际 DFA 目标状态。有人图省事，在 move 里面顺手做了闭包，导致后续每用一次 move 就多闭包一次，语义就乱了。

解决：接口上把两个函数拆开。move 返回未闭合的集合，closure 负责闭合，调用链永远是closure(move(T, c))。报告里画出这条调用链，直接体现对子集构造法的理解。另外注意 move 的结果不要用成员变量复用——如果 move 每次返回同一个集合对象，两次调用之间结果会被覆盖。我一般让 move 每次返回一个新 HashSet，多一次分配，但避免了共享可变状态带来的难查问题。

另外一条经验：闭包的单元测试不要等整个 NFA 生成器写完再做。边表还停留在手工构造阶段时，就先用上面的用例把闭包测一遍。等后面生成器出了问题，至少能确定闭包这一层是干净的。测试框架用 JUnit 或直接 main 方法打印都行，断言要落在「集合相等」上，而不是逐个元素比对。

5. 从闭包到 DFA：验证用例与课程设计报告的落笔重点

闭包函数写完，下一步不是急着写 move，而是先出一份能说服自己和答辩老师的测试对照。我习惯用下面这套最小用例：

这五条覆盖了闭包的所有语义边界：空集、0 条边、1 条边、环、传递闭包。能全部通过，闭包逻辑基本就是对的。做完之后，把「手算过程 + 程序输出」并排贴在报告里，答辩时比口头讲定义有用得多。

写课程设计报告时，我有一条血泪经验：不要整篇贴代码，评阅人没时间读大段源码。重点写三块。第一，选型理由：为什么用 Integer、为什么选邻接表；第二，BFS 和 DFS 的对比，用一个 ε 环用例说明为什么 visited 必不可少；第三，move 与 closure 的调用链，这直接体现你对子集构造法的理解。这三块写清楚，闭包这个「（I）」阶段的区分度就有了。至于后续阶段，报告结尾带一句规划就行，比如「下一阶段将基于本闭包实现完成 move 运算与 DFA 状态合并」，表明你清楚整个链路。DFA 转移表不必大，三四个状态加一个输入字符就够了，重点是标出闭包在中间过程中的作用。

当年我做这个题目时，第一版代码把 move 的结果直接当 DFA 状态用了，闭包函数写好却没接进主流程，构造出来的 DFA 表怎么看怎么不对。后来老老实实把闭包单独测完再往上拼，才发现问题出在调用顺序而不是算法本身。从此我养成了一个习惯：凡是这种纯函数式的运算，先让它独立通过边界用例，再谈集成。这个习惯让后面整个 NFA 转 DFA 的过程顺利了很多。希望帮到你。

本文还有配套的精品资源，点击获取