企业官网建设流程全解析

简介：面向计算机专业学生的编译原理课程设计报告，聚焦有限自动机（NFA）空闭包 ε-closure（I）的Java程序实现，适合正在完成编译原理课程设计或希望掌握NFA子集构造法的读者。报告完整覆盖需求分析、概要设计、详细设计、测试分析、用户使用说明、总结与附录：需求部分明确了输入任意NFA、输出全部或指定状态子集空闭包并以状态转换图展示的基本要求；设计与实现部分详细说明了数组、图、哈希表等数据结构的选用，以及读空函数、读字母表函数、状态子集扩展函数的递归逻辑，特别解释了引入新初态X与终态Y时的处理约束；附录提供完整Java源码，测试部分包含两组NFA实例及运行结果，可直接对照验证。压缩包内共有1个docx文件，整体大小约177KB，报告结构清晰、代码与文档一体，便于按章节查阅，既可作为课程设计模板，也可作为复习NFA与ε-closure知识点的参考资料。这份报告已有1284人学习/浏览，是同类资源中认可度较高的参考材料。

1. ε-closure（I）不是求单个状态，是给NFA状态集合做“ε闭包”

期末课程设计题目发下来，看到“ε-closure（I）程序实现”这个标题，不少同学的第一反应是：闭包不是离散数学里的内容吗，怎么跑到编译原理里来了？等翻到NFA转DFA那一节才明白，子集构造法的第一步就是反复求状态集合的ε闭包——一个集合沿着ε边不断扩展，直到没有新状态加入为止。这个程序虽然只有几十行，但它牵扯到图的遍历、集合表示、文件解析，正好是一道能区分“背答案”和“真理解”的题。本文从数据结构选型讲到Java实现，再给出验证方法和课程设计中容易翻车的细节，适合正在做编译原理课程设计的学生，也适合想补NFA转DFA底层的开发者。

2. 从NFA的ε边到闭包运算：三条规则和一套数据结构

2.1 闭包的三条规则：自反、传递、且只看ε边

ε闭包的定义可以拆成三条规则，写程序之前必须把这三条在纸上过一遍，否则代码写出来也经不起老师追问。

规则一：若状态q在集合I中，则q一定在ε-closure(I)中。这条叫自反性，是整个递归的起点。很多人写程序时忘了把I里的元素直接加入结果集，导致闭包结果缺了“自己”，这就是典型的逻辑漏项。

规则二：若状态q在ε-closure(I)中，且存在一条从q出发的ε边到达状态p，则p也在ε-closure(I)中。这是传递性的体现，也是程序里循环扩张的那一步。

规则三：重复规则二，直到结果集不再发生变化。注意“不再发生变化”这个终止条件，没有它，带环的NFA会让程序无限循环。

一句话总结：ε闭包就是“从集合I出发，沿着ε边能走到的一切状态，包括自己”。这里强调“包括自己”，因为课程设计里最常见的一个错误就是把初态集合I本身漏掉，导致后面子集构造出来的DFA状态表缺了起点。

要区分的是：ε闭包只看ε转移，不关心那些带字母a、b的边。也就是说，读入NFA文件时要先把边分类，把ε边单独存一张表，普通字母边另存一张表。后面算完闭包，还要跟move操作配合，先走字母边，再求一次闭包，两条路径不能混。

2.2 数据结构选型：用Map存ε转移表，用Set存闭包结果

在Java里落地，最自然的数据结构不是二维数组，而是Map<Integer, Set<Integer>>。为什么不用二维数组？课程设计的NFA输入通常只有几十个状态，用二维布尔数组boolean epsEdge[i][j]也能表示，但数组有两个问题：一是如果输入文件里的状态编号不连续，比如状态是0、1、5、7，数组得开到最大编号加一，浪费内存；二是“某个状态的ε出边有哪些”这个查询，数组需要扫描一整行，时间复杂度O(n)，而Map可以直接按编号取。

我一般这样声明：

// 状态编号 -> 该状态所有ε出边的目标状态集合 Map<Integer, Set<Integer>> epsTrans = new HashMap<>();

Map的key是源状态编号，value是目标状态集合。为什么不直接存一个列表List<Integer>？因为后面查询时要用getOrDefault，如果某个状态没有ε出边，返回空集合，调用方不用再做空指针判断。至于value用ArrayList还是Set，我选择HashSet，因为后续闭包计算中会反复判断“某个目标状态是否已经加入结果”，Set的contains和add去重都是O(1)，比List的contains O(n)快一个量级。

闭包结果本身也是一个Set<Integer>。这里有个细节值得注意：用HashSet还是TreeSet。HashSet的遍历顺序不稳定，同样的状态集合，换一次运行可能输出顺序就变了。课程设计的报告里要截图贴运行结果，前后两次输出顺序不一致会很尴尬。我建议闭包结果用TreeSet，它按状态编号升序排列，toString也自然有序。代价是插入和查询从O(1)变成O(log n)，但对于几十个状态的NFA，这点开销可以忽略。

还有一个小结构是工作列表（worklist）。闭包计算本质是图的遍历，需要记录“还有哪些状态的ε出边没被扩展”。这个队列用ArrayDeque<Integer>来装，比LinkedList更快，也比自己在ArrayList上维护头尾指针省心。完整的Data结构组合是：

public class EpsilonClosure { private final Map<Integer, Set<Integer>> epsTrans; private final Deque<Integer> worklist = new ArrayDeque<>(); private final Set<Integer> result = new TreeSet<>(); public EpsilonClosure(Map<Integer, Set<Integer>> epsTrans) { this.epsTrans = epsTrans; } }

这段代码的三个成员变量就是整个程序的地基。epsTrans是外部传入的ε转移表，worklist和result是每次调用closure方法时临时使用的容器。这里把worklist和result设计为成员变量，是为了避免在方法内部频繁new，但对课程设计来说，把result作为方法内局部变量更安全，防止上一次调用残留数据污染下一次结果。下面实现时我会把result放在方法内new。

2.3 复杂度与边界条件：为什么这个算法能在线性时间跑完

闭包算法的复杂度是O(V+E)，V是状态数，E是ε边数。每个状态最多入队一次、出队一次，每条ε边最多被扫描一次，所以总操作次数是线性的。这个结论老师在答辩时大概率会问，得能答上来。

边界条件有三个。第一，输入集合I是空集时，闭包也应该是空集，不能让算法进入死循环也不能NPE。第二，某个状态没有任何ε出边，这时getOrDefault返回空集合，循环体直接跳过。第三，状态编号虽然是int，但输入文件里可能有负数表示“无转移”，解析时要做合法性校验。

3. Java实现最小可跑版本：从文本输入到闭包输出

3.1 输入格式：自定一份NFA描述文件

课程设计没有给定输入格式，这是好事也是坏事。好事是设计自由度大，坏事是解析代码容易写出bug。我建议采用最简单的按行拆分格式，每行一个规则，学校老师看了也容易懂。文件的长这样：

# 状态总数 5 # ε转移表：源状态:目标状态1,目标状态2 0:1 1:2 2:0 3:4 # 待求闭包的状态集合I I:0,3

为什么这么设计？第一，用#开头作为注释行，方便在报告里贴出完整的输入样例。第二，每条ε边单独一行，源状态和目标状态用冒号分隔，目标状态多个时用逗号分隔，解析逻辑清晰。第三，最后一行用I:前缀标记闭包输入集合，读取时一旦遇到这个前缀就停止ε表解析，转入集合解析。

注意，NFA的终态集合在这个程序里不需要，因为我们只算闭包，不判断接受串。文件里不写初态、终态、字母表，程序职责单一，后续子集构造法再把这些补齐。

3.2 核心算法：用工作列表避免递归爆栈

闭包算法有两种写法：递归DFS和非递归BFS。我强烈建议课程设计用非递归的工作列表法，理由有三：一是NFA的ε环可能很深，递归深了会StackOverflow，Java默认栈深度只有几千层，课程设计里状态数虽然少，但“能解释清楚为什么不用递归”是答辩加分项；二是工作列表法的循环结构直观，每一步都能在调试器里查看result和worklist的状态；三是代码量几乎一样，没必要给自己挖坑。

核心实现如下：

public Set<Integer> closure(Set<Integer> I) { Set<Integer> result = new TreeSet<>(I); Deque<Integer> worklist = new ArrayDeque<>(I); while (!worklist.isEmpty()) { int q = worklist.poll(); Set<Integer> nexts = epsTrans.getOrDefault(q, Collections.emptySet()); for (int p : nexts) { if (result.add(p)) { worklist.add(p); } } } return result; }

这段代码的精髓在于result.add(p)的返回值。Set的add方法在元素已存在时返回false，否则返回true并加入元素。所以这一句同时完成了“判重”和“入队决策”两件事：新状态加进result，同时加入worklist等待扩展；老状态什么也不做，自然不会再入队。这样一来，既不需要单独的visited数组，也不会出现同一个状态重复扩展的情况。

逻辑说明：初始化时用new TreeSet<>(I)把输入集合I的所有状态直接拷贝进结果集，这就实现了闭包规则一“自己包含自己”。工作列表初始化为new ArrayDeque<>(I)意味着所有初始状态都需要被扩展一次。主循环每次从工作列表头部取出一个状态，找到它所有ε出边，凡是没有出现过的目标状态，立即加入结果集和工作列表。当工作列表清空时，算法自然终止。

参数说明：getOrDefault(q, Collections.emptySet())的第二个参数用了不可变的空集合，好处是当q不在epsTrans中时，不会因为返回null导致下文的for (int p : nexts)抛出NullPointerException。Collections.emptySet()是类型安全的，协变到Set<Integer>没问题。如果这里写成get(q)，忘了判空，就是程序中最隐蔽的翻车点。

3.3 主程序与文件解析：把字符串变成结构

主程序做的事情有四步：打开文件、逐行解析、构造epsTrans、调用closure并打印结果。下面是一个完整的可运行版：

import java.io.*; import java.util.*; public class EpsilonClosureMain { public static void main(String[] args) throws IOException { if (args.length < 1) { System.err.println("用法: java EpsilonClosureMain <nfa描述文件>"); return; } Map<Integer, Set<Integer>> epsTrans = new HashMap<>(); Set<Integer> I = new TreeSet<>(); try (BufferedReader br = new BufferedReader(new FileReader(args[0]))) { String line; while ((line = br.readLine()) != null) { line = line.trim(); if (line.isEmpty() || line.startsWith("#")) { continue; } if (line.startsWith("I:")) { parseStateSet(line.substring(2), I); break; } int colon = line.indexOf(':'); if (colon < 0) { throw new IllegalArgumentException("无法解析的行: " + line); } int from = Integer.parseInt(line.substring(0, colon).trim()); String[] targets = line.substring(colon + 1).split(","); Set<Integer> toSet = new TreeSet<>(); for (String t : targets) { if (!t.trim().isEmpty()) { toSet.add(Integer.parseInt(t.trim())); } } epsTrans.put(from, toSet); } } EpsilonClosure calc = new EpsilonClosure(epsTrans); Set<Integer> result = calc.closure(I); System.out.println("ε-closure(" + I + ") = " + result); } private static void parseStateSet(String data, Set<Integer> out) { for (String token : data.split(",")) { String t = token.trim(); if (!t.isEmpty()) { out.add(Integer.parseInt(t)); } } } }

逻辑说明：读取器用BufferedReader逐行扫描，trim()去掉行首尾的空白，注释行和空行直接跳过，这样文件里无论有没有换行符残留都能稳定解析。遇到I:前缀时，把剩余部分切给parseStateSet，逐一转成int并加入初始集合。

这段代码有几个细节值得说。line.indexOf(':')找的是第一个冒号，如果目标状态集合里不小心写了类似“1:2”这种带冒号的行，会因为substring截断得到错误结果。所以输入文件格式要约定好：一行只能有一个冒号，后面的部分用逗号分隔。整数解析用了Integer.parseInt，它会自动trim吗？不会，所以我在外面手动trim()。Windows环境下从文件读出的行尾可能带\r，如果不trim，Integer.parseInt("1\r")会抛NumberFormatException，这是课程设计交作业前最容易踩的坑。

运行方式很简单：

javac EpsilonClosureMain.java java EpsilonClosureMain nfa.txt

注意Java 8以后编译运行两条命令分开执行，不写classpath时默认当前目录。如果老师的机器上Java版本较高而你的代码用了var关键字，会有兼容性问题；为保险起见，老实的Map<Integer, Set<Integer>>写法永远不过时。

4. 验证闭包算得对不对：手工推演加自动化断言

4.1 手算一个带环的NFA例子

写代码只完成了一半工作，另一半是证明代码正确。课程设计报告里只贴运行截图不够，得能手工推演一遍，让老师看到算法确实按数学定义在工作。

用下面这个NFA作为验证用例：

5 0:1 1:2 2:0 3:4 I:0,3

这组输入里有两个分开的子图：状态0、1、2构成一个三状态环，0到1、1到2、2到0都是ε边；状态3到4是一条单向ε边。求ε-closure({0,3})。

手工推演过程如下：

第一轮：结果集初始为{0,3}。工作列表里有0和3。

弹出状态0，发现0的ε出边指向1，1不在结果集里，加入。结果集变成{0,1,3}，工作列表加入1。

弹出状态3，3的ε出边指向4，4不在结果集里，加入。结果集变成{0,1,3,4}，工作列表加入4。

弹出状态1，1的ε出边指向2，2不在结果集里，加入。结果集变成{0,1,2,3,4}，工作列表加入2。

弹出状态4，4没有ε出边，什么都不做。

弹出状态2，2的ε出边指向0，但0已经在结果集里，什么都不做。

工作列表清空，算法停止。最终闭包是{0,1,2,3,4}。

这个例子验证了三件事：第一，环被正确处理，状态2回到0时因为0已存在所以不会再重复入队；第二，两个独立连通分量都被覆盖到；第三，没有ε出边的状态4不会导致异常。

4.2 把教材例子固化成断言测试

手算完成了，我还要把推演过程自动化，这样每次改代码后跑一下就知道有没有改坏。课程设计里不用引入JUnit，直接在main方法里写断言即可：

public static void selfTest() { Map<Integer, Set<Integer>> epsTrans = new HashMap<>(); epsTrans.put(0, new TreeSet<>(Arrays.asList(1))); epsTrans.put(1, new TreeSet<>(Arrays.asList(2))); epsTrans.put(2, new TreeSet<>(Arrays.asList(0))); epsTrans.put(3, new TreeSet<>(Arrays.asList(4))); EpsilonClosure calc = new EpsilonClosure(epsTrans); Set<Integer> result1 = calc.closure(new TreeSet<>(Arrays.asList(0))); Set<Integer> expected1 = new TreeSet<>(Arrays.asList(0, 1, 2)); if (!result1.equals(expected1)) { throw new AssertionError("用例1失败: 期望 " + expected1 + " 实际 " + result1); } Set<Integer> result2 = calc.closure(new TreeSet<>(Arrays.asList(0, 3))); Set<Integer> expected2 = new TreeSet<>(Arrays.asList(0, 1, 2, 3, 4)); if (!result2.equals(expected2)) { throw new AssertionError("用例2失败: 期望 " + expected2 + " 实际 " + result2); } Set<Integer> result3 = calc.closure(new TreeSet<>()); if (!result3.isEmpty()) { throw new AssertionError("空集闭包应该为空"); } System.out.println("全部测试通过"); }

为什么要用throw new AssertionError而不是assert关键字？因为Java默认关闭断言功能，运行时加-ea参数才能生效，很多课程设计环境里同学直接java EpsilonClosureMain执行，断言压根不会触发，测试等于白写。手动抛异常不需要任何JVM参数，只要测试不通过，程序就会以非零状态退出，这个设计在任何环境下都可靠。

这个测试方法的特别之处在于第三个用例：空集的闭包必须为空。很多人在写算法时先初始化结果集再循环，如果初始化用的不是new TreeSet<>(I)而是一个空集合然后手动把I加进去，空集情况就会得到错误结果。测试先行，这些边界条件想在后面就多了。

4.3 再补一个多分支的测试用例

环测完了，还要测多分支的情况。状态0同时有ε边指向1和2，状态2又指向3，这就是一个二叉发散结构。预期闭包应该覆盖0、1、2、3四个状态。这种用例看起来简单，但能抓出“只扩展了一条出边就以为处理完了”的低级错误——比如有人用if判断第一条出边而不是用for循环遍历所有出边。多分支测试是最容易暴露这一类bug的。

5. 避坑指南：课程设计交作业前必查的5个问题

5.1 死循环：图里有环时visited数组没生效

现象：程序输入的NFA自带ε环，比如状态0到1、1到0，运行后控制台没有任何输出，CPU占用飙升，程序卡死。

原因：闭包算法里缺少判重机制。常见写法是用一个单独的visited集合，但只在该状态首次加入结果集时标记，却忘了在处理完某个状态之后把它从“待处理”队列里剔除时再检查一次。更隐蔽的是用if (!visited.contains(p))判断时，查询在add之前，两个线程并发会出问题，单线程下如果代码逻辑是“先查再放”，环上的状态还是会被重复处理。

解决：用result.add(p)的返回值直接作为判重依据。这个技巧把“查重”和“加入”合并成一步，天然免疫重复入队。如果是自己维护visited数组，务必保证状态入队前就标记，而不是出队后才标记。换句话说，标记要发生在“加入队列的那一刻”，不是“取出元素的那一刻”。

5.2 把普通字母边当成了ε边

现象：闭包结果出奇地大，比如NFA里有一条0--a-->1的边，算closure({0})居然把1也算进去了。

原因：解析文件时没有把边的类型区分开，把所有转移都塞进了epsTrans里。这通常是因为输入文件里字母边和ε边混在同一张表里，比如一行写成0:a,1，程序没过滤掉“a”这样的非ε目标。

解决：输入格式约定ε边单独成行，目标状态只允许整数，遇到字母直接抛异常。解析代码里加一个过滤：

for (String t : targets) { String token = t.trim(); if (token.equals("ε") || token.equals("eps") || token.equalsIgnoreCase("lambda")) { toSet.add(Integer.parseInt(token)); // 不行，parseInt("ε")会报错 } }

上面的写法是错的，正确做法是让输入文件里只写整数编号。更稳的方法是约定ε边就用特殊状态编号-1表示？也不行。最简单可靠的约定就是让输入文件的ε表里全是整数，把ε的定义写进文档而不写进数据。如果非要允许“ε”这两个字符出现在文件里，解析时遇到非数字token，应该跳过而不是报错。我在课程设计里吃过这个亏，后来干脆规定NFA文件里只允许三种内容：注释、数字、冒号和逗号和I:前缀，任何别的字符都算文件格式错误。

5.3 文件解析的格式坑：\r、空格与空行

现象：程序在本地跑得好好的，一到答辩演示用的Windows电脑上就抛NumberFormatException，报错的明明是同一个文件。

原因：Windows下用记事本编辑的文本文件换行符是\r\n，readLine()按\n切分后每行末尾还残留一个\r，Integer.parseInt("1\r")直接炸。另一个坑是文件末尾有多余空行，空行被trim()后变成空字符串，如果代码里没有过滤空行的逻辑，split(",")返回的数组里有一个空串，parseInt照样炸。

解决：每一行读进来先line = line.trim()，再判空；trim()会干掉\r和普通空格。解析目标状态列表时，split(",")后对每个token也做trim()，并跳过空串。这三个动作一个都不能少。建议在报告里写清楚“输入文件需为UTF-8无BOM编码”，BOM头会导致第一行开头多一个不可见字符，那个字符parseInt也不认识。

5.4 迭代中修改集合导致的结果漂移

现象：闭包算出来的结果偶尔错误，而且每次运行结果还不一样，像是玄学问题。

原因：有人把算法写成了for-each风格：

for (int q : result) { result.addAll(epsTrans.getOrDefault(q, emptySet())); }

Java的HashSet在迭代过程中被修改会立刻抛ConcurrentModificationException，TreeSet的迭代器是fail-fast的，同样会抛。但如果你遍历的同时没有触发iterator的下一次调用，问题会以“结果不对”的假象出现——某次add操作恰好重新哈希了底层数组，后续遍历访问的链表节点就错乱了。

解决：用工作列表模式，遍历的对象是独立的Deque<Integer>，闭包结果只做读操作和add操作，不参与迭代。这是教科书的标准做法，也是聊天里推荐的非递归版本。想用流式写法的话，可以用while循环加索引变量手动遍历一个ArrayList快照，但没必要。工作列表方案是经过实践检验的，别自作聪明改成“更优雅”的方式。

5.5 输出顺序不稳定：报告截图前后对不上

现象：同一个输入文件，第一次运行输出[0, 1, 2, 3]，第二次运行输出[1, 0, 2, 3]，虽然集合内容一样，但报告里的截图和文字描述对不上，答辩时老师一对比就觉得程序有毛病。

原因：HashSet和HashMap的遍历顺序依赖对象的hashCode，而Integer的hashCode就是值本身，顺序看起来和值有关但实际是由哈希桶的分布决定的，不同集合的初始容量不同会导致顺序错乱。更糟糕的是，Java 8之后HashMap在链表长度超过8时会转成红黑树，顺序会再次改变。

解决：使用TreeSet作为闭包结果集合，按状态编号升序输出。或者在打印时手动排序：

List<Integer> sortedList = new ArrayList<>(result); Collections.sort(sortedList); System.out.println(sortedList);

如果这两招都用上了，还能跟文件输入顺序不一致，那只有一种可能——文件本身的目标集合就是乱序写的。TreeSet重写了toString，打印出来永远是升序，课程设计用这个最省心。

6. 从ε-closure（I）走向子集构造法：补上DFA状态表

闭包算完，课程设计如果只停在这里，老师多半会追问一句“下一步呢”。为了让报告有纵深，我建议加一节代码，展示如何用ε-closure配合move操作构建DFA状态转移表。原理很简单：子集构造法里，NFA的每个状态子集对应DFA的一个状态，从初始状态集合出发，对每个字母a，计算move(S, a)的ε闭包，得到新的子集，重复直到不再产生新子集。

public Map<Set<Integer>, Map<Character, Set<Integer>>> buildDfa( Map<Integer, Map<Character, Set<Integer>>> nfaTrans, Set<Integer> startSet) { Map<Set<Integer>, Map<Character, Set<Integer>>> dfa = new LinkedHashMap<>(); Deque<Set<Integer>> queue = new ArrayDeque<>(); Set<Set<Integer>> visited = new HashSet<>(); Set<Integer> start = closure(startSet); queue.offer(start); visited.add(start); while (!queue.isEmpty()) { Set<Integer> current = queue.poll(); Map<Character, Set<Integer>> row = new LinkedHashMap<>(); for (char c : new char[]{'a', 'b'}) { Set<Integer> moved = new TreeSet<>(); for (int q : current) { Set<Integer> targets = nfaTrans.getOrDefault(q, new HashMap<>()).getOrDefault(c, new TreeSet<>()); moved.addAll(targets); } Set<Integer> next = closure(moved); if (!next.isEmpty()) { row.put(c, next); if (!visited.contains(next)) { visited.add(next); queue.offer(next); } } } dfa.put(current, row); } return dfa; }

这段代码把前面做的闭包当成黑匣子来用：先对初始集合求一次闭包得到DFA的起始状态，再对每个输入符号移动一步并再次闭包。LinkedHashMap保证了DFA状态按发现顺序输出，图表和论文截图能对得上。

我自己的习惯是把这一节当作“附加分”写进报告摘要里，但代码体量控制在30行以内，这样答辩时讲得清楚，老师也不会觉得是抄的。回想我做课程设计那段时间，踩得最深的一个坑是自己写完闭包算法后没有立刻自测，直接拿去跑子集构造法，结果DFA状态表出来全是空的，找了半天才发现是闭包里忘了把初始集合加进去。这个教训让我养成了“先写selfTest再写业务代码”的习惯，确实管用，希望帮到你。

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