简介面向计算机专业学生的编译原理课程设计报告聚焦有限自动机NFA空闭包 ε-closureI的Java程序实现适合正在完成编译原理课程设计或希望掌握NFA子集构造法的读者。报告完整覆盖需求分析、概要设计、详细设计、测试分析、用户使用说明、总结与附录需求部分明确了输入任意NFA、输出全部或指定状态子集空闭包并以状态转换图展示的基本要求设计与实现部分详细说明了数组、图、哈希表等数据结构的选用以及读空函数、读字母表函数、状态子集扩展函数的递归逻辑特别解释了引入新初态X与终态Y时的处理约束附录提供完整Java源码测试部分包含两组NFA实例及运行结果可直接对照验证。压缩包内共有1个docx文件整体大小约177KB报告结构清晰、代码与文档一体便于按章节查阅既可作为课程设计模板也可作为复习NFA与ε-closure知识点的参考资料。这份报告已有1284人学习/浏览是同类资源中认可度较高的参考材料。1. ε-closureI不是求单个状态是给NFA状态集合做“ε闭包”期末课程设计题目发下来看到“ε-closureI程序实现”这个标题不少同学的第一反应是闭包不是离散数学里的内容吗怎么跑到编译原理里来了等翻到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里落地最自然的数据结构不是二维数组而是MapInteger, SetInteger。为什么不用二维数组课程设计的NFA输入通常只有几十个状态用二维布尔数组boolean epsEdge[i][j]也能表示但数组有两个问题一是如果输入文件里的状态编号不连续比如状态是0、1、5、7数组得开到最大编号加一浪费内存二是“某个状态的ε出边有哪些”这个查询数组需要扫描一整行时间复杂度O(n)而Map可以直接按编号取。我一般这样声明// 状态编号 - 该状态所有ε出边的目标状态集合 MapInteger, SetInteger epsTrans new HashMap();Map的key是源状态编号value是目标状态集合。为什么不直接存一个列表ListInteger因为后面查询时要用getOrDefault如果某个状态没有ε出边返回空集合调用方不用再做空指针判断。至于value用ArrayList还是Set我选择HashSet因为后续闭包计算中会反复判断“某个目标状态是否已经加入结果”Set的contains和add去重都是O(1)比List的contains O(n)快一个量级。闭包结果本身也是一个SetInteger。这里有个细节值得注意用HashSet还是TreeSet。HashSet的遍历顺序不稳定同样的状态集合换一次运行可能输出顺序就变了。课程设计的报告里要截图贴运行结果前后两次输出顺序不一致会很尴尬。我建议闭包结果用TreeSet它按状态编号升序排列toString也自然有序。代价是插入和查询从O(1)变成O(log n)但对于几十个状态的NFA这点开销可以忽略。还有一个小结构是工作列表worklist。闭包计算本质是图的遍历需要记录“还有哪些状态的ε出边没被扩展”。这个队列用ArrayDequeInteger来装比LinkedList更快也比自己在ArrayList上维护头尾指针省心。完整的Data结构组合是public class EpsilonClosure { private final MapInteger, SetInteger epsTrans; private final DequeInteger worklist new ArrayDeque(); private final SetInteger result new TreeSet(); public EpsilonClosure(MapInteger, SetInteger epsTrans) { this.epsTrans epsTrans; } }这段代码的三个成员变量就是整个程序的地基。epsTrans是外部传入的ε转移表worklist和result是每次调用closure方法时临时使用的容器。这里把worklist和result设计为成员变量是为了避免在方法内部频繁new但对课程设计来说把result作为方法内局部变量更安全防止上一次调用残留数据污染下一次结果。下面实现时我会把result放在方法内new。2.3 复杂度与边界条件为什么这个算法能在线性时间跑完闭包算法的复杂度是O(VE)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的ε环可能很深递归深了会StackOverflowJava默认栈深度只有几千层课程设计里状态数虽然少但“能解释清楚为什么不用递归”是答辩加分项二是工作列表法的循环结构直观每一步都能在调试器里查看result和worklist的状态三是代码量几乎一样没必要给自己挖坑。核心实现如下public SetInteger closure(SetInteger I) { SetInteger result new TreeSet(I); DequeInteger worklist new ArrayDeque(I); while (!worklist.isEmpty()) { int q worklist.poll(); SetInteger 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()是类型安全的协变到SetInteger没问题。如果这里写成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; } MapInteger, SetInteger epsTrans new HashMap(); SetInteger 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(,); SetInteger 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); SetInteger result calc.closure(I); System.out.println(ε-closure( I ) result); } private static void parseStateSet(String data, SetInteger 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如果不trimInteger.parseInt(1\r)会抛NumberFormatException这是课程设计交作业前最容易踩的坑。运行方式很简单javac EpsilonClosureMain.java java EpsilonClosureMain nfa.txt注意Java 8以后编译运行两条命令分开执行不写classpath时默认当前目录。如果老师的机器上Java版本较高而你的代码用了var关键字会有兼容性问题为保险起见老实的MapInteger, SetInteger写法永远不过时。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的ε出边指向11不在结果集里加入。结果集变成{0,1,3}工作列表加入1。弹出状态33的ε出边指向44不在结果集里加入。结果集变成{0,1,3,4}工作列表加入4。弹出状态11的ε出边指向22不在结果集里加入。结果集变成{0,1,2,3,4}工作列表加入2。弹出状态44没有ε出边什么都不做。弹出状态22的ε出边指向0但0已经在结果集里什么都不做。工作列表清空算法停止。最终闭包是{0,1,2,3,4}。这个例子验证了三件事第一环被正确处理状态2回到0时因为0已存在所以不会再重复入队第二两个独立连通分量都被覆盖到第三没有ε出边的状态4不会导致异常。4.2 把教材例子固化成断言测试手算完成了我还要把推演过程自动化这样每次改代码后跑一下就知道有没有改坏。课程设计里不用引入JUnit直接在main方法里写断言即可public static void selfTest() { MapInteger, SetInteger 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); SetInteger result1 calc.closure(new TreeSet(Arrays.asList(0))); SetInteger expected1 new TreeSet(Arrays.asList(0, 1, 2)); if (!result1.equals(expected1)) { throw new AssertionError(用例1失败: 期望 expected1 实际 result1); } SetInteger result2 calc.closure(new TreeSet(Arrays.asList(0, 3))); SetInteger expected2 new TreeSet(Arrays.asList(0, 1, 2, 3, 4)); if (!result2.equals(expected2)) { throw new AssertionError(用例2失败: 期望 expected2 实际 result2); } SetInteger 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\nreadLine()按\n切分后每行末尾还残留一个\rInteger.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在迭代过程中被修改会立刻抛ConcurrentModificationExceptionTreeSet的迭代器是fail-fast的同样会抛。但如果你遍历的同时没有触发iterator的下一次调用问题会以“结果不对”的假象出现——某次add操作恰好重新哈希了底层数组后续遍历访问的链表节点就错乱了。解决用工作列表模式遍历的对象是独立的DequeInteger闭包结果只做读操作和add操作不参与迭代。这是教科书的标准做法也是聊天里推荐的非递归版本。想用流式写法的话可以用while循环加索引变量手动遍历一个ArrayList快照但没必要。工作列表方案是经过实践检验的别自作聪明改成“更优雅”的方式。5.5 输出顺序不稳定报告截图前后对不上现象同一个输入文件第一次运行输出[0, 1, 2, 3]第二次运行输出[1, 0, 2, 3]虽然集合内容一样但报告里的截图和文字描述对不上答辩时老师一对比就觉得程序有毛病。原因HashSet和HashMap的遍历顺序依赖对象的hashCode而Integer的hashCode就是值本身顺序看起来和值有关但实际是由哈希桶的分布决定的不同集合的初始容量不同会导致顺序错乱。更糟糕的是Java 8之后HashMap在链表长度超过8时会转成红黑树顺序会再次改变。解决使用TreeSet作为闭包结果集合按状态编号升序输出。或者在打印时手动排序ListInteger sortedList new ArrayList(result); Collections.sort(sortedList); System.out.println(sortedList);如果这两招都用上了还能跟文件输入顺序不一致那只有一种可能——文件本身的目标集合就是乱序写的。TreeSet重写了toString打印出来永远是升序课程设计用这个最省心。6. 从ε-closureI走向子集构造法补上DFA状态表闭包算完课程设计如果只停在这里老师多半会追问一句“下一步呢”。为了让报告有纵深我建议加一节代码展示如何用ε-closure配合move操作构建DFA状态转移表。原理很简单子集构造法里NFA的每个状态子集对应DFA的一个状态从初始状态集合出发对每个字母a计算move(S, a)的ε闭包得到新的子集重复直到不再产生新子集。public MapSetInteger, MapCharacter, SetInteger buildDfa( MapInteger, MapCharacter, SetInteger nfaTrans, SetInteger startSet) { MapSetInteger, MapCharacter, SetInteger dfa new LinkedHashMap(); DequeSetInteger queue new ArrayDeque(); SetSetInteger visited new HashSet(); SetInteger start closure(startSet); queue.offer(start); visited.add(start); while (!queue.isEmpty()) { SetInteger current queue.poll(); MapCharacter, SetInteger row new LinkedHashMap(); for (char c : new char[]{a, b}) { SetInteger moved new TreeSet(); for (int q : current) { SetInteger targets nfaTrans.getOrDefault(q, new HashMap()).getOrDefault(c, new TreeSet()); moved.addAll(targets); } SetInteger 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再写业务代码”的习惯确实管用希望帮到你。本文还有配套的精品资源点击获取