简介一份面向编译原理课程设计的Java实现报告聚焦有限自动机NFA的空闭包ε-closureI计算适合需要完成NFA状态子集闭包程序设计与图形化展示的学生参考。资源包内含1个docx文档约177KB整份报告围绕需求分析、概要设计、详细设计、测试与分析、用户使用说明、总结与附录展开旨在输入任意NFA输出全部状态子集及指定子集I的空闭包并以布局合理、具备通用性的状态转换图呈现自动机。程序引入新初始状态X和终止状态Y借助数组、图和哈希表存储数据核心函数包括求X空闭包、对子集读空、读字母表等使用递归和静态变量逐层累积空弧可达状态同时根据状态转移函数逐步生成转换图。测试与分析中给出多个NFA算例验证正确性附录提供完整Java源代码便于读者复现和二次修改已有1284人学习下载对深入理解ε-closure概念及Java实现方法很有帮助。1. ε-closureI一份把编译原理课设从概念落到运行的Java实现拿到“ε-closure(I)的程序实现”这个编译原理课程设计时多数人的第一反应是翻教材找定义状态子集I经过任意条空转移能到达的所有状态集合。定义好懂难的是把它写成能跑的程序——递归怎么做、空转移怎么处理、状态子集怎么去重、转换图怎么画。这份资源把这些一步到位地解决了是一份完整的Java课程设计报告包含需求分析、概要设计、详细设计、三个测试用例和核心源码能完成三件事输入任意NFA并保存到文件、输出所有状态子集、输出每个状态子集的ε-closure。适合正在做编译原理课设的学生也适合用子集构造法把NFA转DFA时需要算闭包的开发者。报告里对“新初态X”的读空处理是一个很实用的边界设计后面会拆开讲。2. 求状态子集的核心思路先读空、再读a、再读空2.1 ε-closure在子集构造法中的位置先搞清楚ε-closure的定义不复杂给定状态子集I从I中任意状态出发经过0条或多条ε弧所能到达的状态集合就是ε-closure(I)。注意“0条”这个词也就是说I里的每个状态都必须出现在结果里这是最容易在实现时漏掉的一点。它在编译原理里的用途很明确——NFA转DFA。DFA的一个状态对应NFA的一个状态集合而这个集合必须是“封闭”的凡是通过ε能到达的状态都要被卷进同一个集合里否则后续读字符时状态会凭空消失。子集构造法里对每个DFA状态T和每个符号a标准做法是先算move(T,a)再对它求ε-closure写成公式就是Ia ε-closure(move(T,a))。报告里的算法主线就是这样展开的先把NFA的初态处理成种子状态集再对每个状态子集逐一读字母表里的每个符号每读一个符号都要把ε可达的状态补进结果。这里有个关键的设计决定求状态子集和求空闭包拆成两个阶段而不是在同一个函数里混着做。因为闭包会被反复调用如果每次读符号都从头递归一遍ε复杂度会肉眼可见地爆炸拆开之后闭包只负责“补ε”读字母只负责“查转移表”主循环只是把两者按顺序拼起来。知道这条主线后面看代码就不会晕。整份资源最值钱的地方不是某个函数有多精巧而是它把“读空—读字母—再读空”这个顺序想清楚了。2.2 引入新初态X和终态Y一个简化但能跑的设计NFA原本可能有多个初态、多个终态。子集构造法要求从“唯一的初态”开始所以一般的做法是加一个新的初态节点X用ε弧连到原NFA的每一个初态加一个新的终态节点Y让原NFA的每一个终态用ε弧连到Y。这样整个自动机的入口和出口就统一了。报告中明确写了自己在这里做的一个取舍“我们能力有限实在想不出如何处理X到任意状态节点以及任意状态节点到Y的情况所以写的时候我们就让X和Y都固定连接到那一个节点。”也就是说X只连到其中一个初态Y只接收其中一个终态的ε弧。从课程设计角度这是一个能跑起来的简化但从通用性角度这条路是堵死的——如果NFA有两个初态固定只连一个后面的状态子集必然丢掉另一个初态可达的所有路径。我一般会在阅读这种代码时把它升级成标准做法X分别ε到每个初态每个终态分别ε到Y并把这几条ε产生式追加到产生式数组里。这样改动成本很低也就是在输出产生式时多拼几个字符串但换成任何输入都能正确处理。报告里三个测试用例都是单初态单终态所以简化版本跑得通但它只能算“作业级”的实现。2.3 三个核心函数怎么分工整个程序的后端逻辑可以拆成三块对应报告里三个函数RestltList对单个状态读空递归地把所有经ε弧可达的状态累加出来。X只有ε出边所以对X调用一次RestltList得到的就是第一个状态子集。RestltListA只读字母不看ε。给定一个状态和一个符号返回它读这个符号后到达的所有状态。DuKong对RestltListA的结果再做一轮读空。因为读a到达的状态可能还有ε出边必须把这一层也卷进来。三者组合起来就是Ia DuKong(RestltListA(T 的每个状态, a))。这也是报告总结里说的“读a的前后都要读空”——T在生成时已经是闭包读a前不需要额外读空但读a后的结果必须补一次闭包。为什么用String来模拟集合而不是直接上Set 报告里所有状态集合都是字符串拼接原因很实际charAt容易取字符、递归容易写、循环判断用String.valueOf(char)比较直观。代价是没有去重、字符顺序不保证、状态编号超过一位就错位。这三个代价恰好成为第五章要讲的避坑点。如果你只是交课程设计String方案够用如果你要让程序处理任意NFA换Set是迟早的事。3. Java实现三个核心函数的代码、参数与调用关系3.1 产生式的读取与预处理先把NFA存成String数组报告里NFA的产生式统一用(状态,字母)→状态的字符串表示这是整个程序的数据契约。例如(1,a)→3表示状态1读a到达状态3(X,ε)→5表示X通过ε弧到达5。从charAt的角度看这个字符串的每个下标都有固定含义下标0123456内容(状态,转移字符)→目标状态这意味着产生式里的状态、字母都必须是单个字符。第一行读状态集、第二行读字母表、之后每行一条产生式读取代码我一般这样写Scanner sc new Scanner(new File(nfa.txt)); String statesLine sc.nextLine(); // 第一行状态列表如 X,1,2,3,4,5,6,Y String alphabetLine sc.nextLine(); // 第二行字母表如 a,b ListString prodList new ArrayList(); while (sc.hasNextLine()) { String line sc.nextLine().trim(); if (!line.isEmpty()) prodList.add(line); } String[] transitions prodList.toArray(new String[0]); sc.close();逻辑说明第一行状态集、第二行字母表之后每行一条产生式存入String数组。文件路径可以替换成命令行参数后续所有函数只依赖这个transitions数组跟UI无关方便单独测试。参数说明transitions数组的每个元素都是类似”(1,a)→3“的字符串读取时不能有任何多余空格否则charAt下标全错。这是我实际复现时踩过的第一个坑。3.2 RestltList对单个状态递归读空的实现先看原报告的代码函数名保持它原来的写法RestltList——少一个字母u读的时候别被绕进去public static String RestltList(String string, String[] strings) { for (int i 0; i strings.length; i) { // 取 string 末尾字符作为当前要扩展的状态 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; }逻辑说明函数从string的末尾取字符这个字符就是“当前正在扩展的状态”。遍历产生式找到当前状态开头的ε产生式后把目标状态拼到string末尾然后递归处理新拼进去的这个状态。字符串末尾不断追加递归不断深入直到没有任何ε产生式能匹配末尾状态为止。参数说明string既是输入状态也是累加结果第一次调用传“X”strings是全部产生式数组格式必须满足3.1的charAt下标规则。注意这个函数没有去重、没有环检测。测试用例里ε弧没有成环所以能跑通一旦出现A→ε→B而且B→ε→A递归就停不下来。这是第五章重点排查的第一个坑。3.3 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; }逻辑说明这个函数故意写得非常“纯”——只匹配一个状态、一个符号返回目标状态拼成的字符串。它不递归、不含ε纯粹是查询转移表。例如状态5读b命中(5,b)→5结果是“5”。参数说明第一个参数是单个状态字符不是状态集合。如果你把整个“15”传进去equals永远不成立这也是后面踩坑高发区。第二个参数s是字母表里的字符第三个strings是产生式数组。返回值可能为空字符串表示这条转移不存在。为什么单独拆出这个函数因为求Ia的正确顺序是先读a、后补ε职责混在一起会让递归和循环嵌套失控。报告也是吃了这个亏才改的“当时一直在考虑如何让一个状态子集不仅要考虑读a的情况还要考虑读空的情况……没想到可以这样写直接写了一个专门读字母的函数。”这是一个很典型的模块化收益比硬凹在同一个函数里清爽得多。3.4 DuKong对读a结果补一轮ε闭包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 但没接返回值 RestltList(result, strings); } } } } return result; }逻辑说明循环遍历result的每个字符只要该字符有ε出边就把目标状态追加到result尾部。因为for循环条件在每轮都会重新计算result.length()新追加的状态也会被继续检查所以这个循环天然具备了“队列扩展”的效果。参数说明result是RestltListA的返回值也就是move(T,a)的结果strings是产生式数组。返回值是补完ε闭包后的状态串。有个细节要说透函数里调用RestltList(result, strings)的返回值被丢弃了。RestltList内部的递归修改只作用在它自己的局部变量上不影响DuKong的result真正让result变长的是上面那句result 。换句话说这行调用没有实际作用。报告里把这段原样贴了出来属于无伤大雅的冗余代码第四章给出的版本会把它删掉并补一个更稳的队列版。这个细节也是第五章避坑里值得留意的典型“看起来读了、实际上没读”。调用关系用伪代码一句话讲清楚主循环下一章展开seed RestltList(X, strings) // 种子状态子集 对每个新状态子集 T 对字母表中的每个符号 a moveRes 对 T 的每个状态分别调用 RestltListA(状态, a) Ia DuKong(moveRes, strings) // 补 ε 闭包4. 主程序BFS生成所有状态子集并输出空闭包4.1 完整主循环从种子集出发BFS扩展直到不再出现新子集有了三个函数主程序就是把它们按BFS组织起来。报告里的思路是先得到X的空闭包作为第一个状态子集然后循环取现有子集对每个字母求Ia一旦出现没见过的新子集就继续扩展直到不再出现新子集。下面是我整理出来的可运行版本public static void main(String[] args) throws Exception { String[] transitions readNFA(nfa.txt); // 读取逻辑见 3.1 String alphabet ab; // 第一步种子状态子集 X 的 ε 闭包 String seed normalize(RestltList(X, transitions)); ListString all new ArrayList(); ListString queue new ArrayList(); all.add(seed); queue.add(seed); // 第二步BFS 生成所有状态子集 while (!queue.isEmpty()) { ListString current new ArrayList(queue); queue.clear(); for (String t : current) { for (char ch : alphabet.toCharArray()) { // 1) 每个状态分别读字符拼成 move 结果 String move ; for (int i 0; i t.length(); i) { move RestltListA(String.valueOf(t.charAt(i)), String.valueOf(ch), transitions); } // 2) 对 move 结果补 ε 闭包并归一化 String ia normalize(DuKong(move, transitions)); if (!ia.isEmpty() !all.contains(ia)) { all.add(ia); queue.add(ia); } } } } // 第三步输出全部状态子集 for (String s : all) { System.out.println(状态子集: { s.replace(, ).trim() }); } } static String normalize(String s) { TreeSetCharacter set new TreeSet(); for (char c : s.toCharArray()) set.add(c); StringBuilder sb new StringBuilder(); for (char c : set) sb.append(c); return sb.toString(); }逻辑说明normalize的作用是把“21”和“12”统一成“12”否则同一集合因为插入顺序不同会被当成两个不同子集BFS永远结束不了。这是状态子集构造法实现里最容易被忽略的一环。参数说明all保存所有状态子集且不重复queue是工作队列move是RestltListA对每个状态单独调用的结果拼接。alphabet这里直接写“ab”更通用的做法是把3.1读取的alphabetLine赋值给它。我为什么没有直接用Set 存all因为课程设计报告里全程用String模拟集合为了保持思维一致、也方便打印输出我保留了String并在入口处做归一化。实际工程中直接上HashSet更省心这在后面避坑里会说。4.2 输出每个状态子集的空闭包Map映射与格式化打印题目要求“输出给定的状态子集的空闭包”而且要求“输出所有状态子集的空闭包”。第二件事的本质是建立一张映射状态子集 → ε闭包。报告用MapSet , Set 核心代码MapSetString, SetString mapmax new HashMap(); for (SetString set : allSets) { SetString closure new HashSet(); for (String s : set) { // 把自身加入闭包对应 ε 路径长度为 0 的情况 closure.add(s); // 从 s 出发的 ε 可达状态 String[] reach Utils.stringtoStringArray( RestltList(s, functionStrings)); for (String r : reach) closure.add(r); } mapmax.put(set, closure); }逻辑说明外层循环遍历所有状态子集内层循环对每个状态单独调用RestltList并按“本身 ε可达状态”的方式累积闭包。使用Set类型后自动去重避免同一个状态出现两次。注意原文里特殊处理了“空字符串”状态集合为空的情况直接break整理后的版本用isEmpty判断效果一样。参数说明allSets是4.1节得到的全部状态子集functionStrings是产生式数组RestltList(s, functionStrings)返回从s出发的ε可达状态的字符串。mapmax的key是状态子集value是对应的空闭包。输出阶段把mapmax遍历打印成“状态子集空闭包”的格式即可。这份资源能直接满足题目第(2)(3)条要求所有状态子集的空闭包打印出来任意给定子集也能从mapmax按key取。4.3 用报告里的例子验证一下算法报告例二的数据最简单适合用来核对整个流程状态集0,1,X,Y字母表a,b产生式(X,ε)→0 (0,ε)→Y (0,a)→1 (0,b)→1 (1,a)→0按算法手推种子S0 ε-closure({X}) {X,0,Y}S0读a的结果是{1}S1 {1}S0读b的结果也是{1}S1读a先得到{0}再补ε得到{0,Y}S2 {0,Y}S1读b没有任何产生式命中结果为∅对应报告里的“空代表状态子集为空的情况”S2读a、读b都回到S1最终状态子集是{X,0,Y}、{1}、{0,Y}对应的空闭包分别是它们自身因为这三个集合已经包含各自的ε可达状态。这是报告三个例子里唯一不需要手工拆X/Y就能看清全流程的用例。例一和例三的情况类似只是产生式更多、状态子集更多跑一遍程序看输出就能验证代码是否一致。建议拿到资源后先跑例二再跑例一数据从小到大逐步递进。5. 避坑与常见问题排查静态变量、环状ε与字符串解析5.1 递归读空死循环环状ε转移直接StackOverflow现象RestltList(X)在两类输入上会一直递归一类是A→ε→B、B→ε→A另一类是A→ε→A这种自环。程序表现为StackOverflowError或CPU拉满不退出。原因函数每次只取字符串末尾状态做匹配命中就追加、就递归完全没有“这个状态已经访问过了”的标记。环状ε转移会让同一状态被无限次追加。解决加一个已访问集合命中ε转移前先判断目标状态是否已经处理过。改成BFS或带visited的DFS都可以。我通常这样处理static String closureBfs(String start, String[] trans) { SetCharacter visited new HashSet(); StringBuilder sb new StringBuilder(start); for (int i 0; i sb.length(); i) { char cur sb.charAt(i); if (visited.contains(cur)) continue; visited.add(cur); for (String t : trans) { if (t.charAt(1) cur t.charAt(3) ε) { char next t.charAt(6); if (visited.contains(next)) continue; if (sb.indexOf(Character.toString(next)) -1) { sb.append(next); } } } } return sb.toString(); }这里sb即队列visited防环append前再查一次重复双保险。测试时加一条(A,ε)→B、(B,ε)→A进去如果程序秒出结果说明防住了。提示验证闭包函数是否抗环最快的方法就是给输入加两个互相ε指向的状态跑一次看是否还退出。不能处理环的闭包实现换到任何真实词法分析器的NFA上都活不过五分钟。5.2 静态变量残留第二次调用把第一次的结果也带出来现象同一个闭包函数连续调用两次第二次的返回串比预期多一截多出来的恰好是第一次调用产生的状态。原因报告描述部分写的是“用静态变量字符串接收递归结果”。静态变量属于类级别状态函数第二次进入时它仍是上次的值如果入口没有清空结果必然串扰。解决入口处立即重置静态变量或者干脆不用静态变量。附录里RestltList实际是“局部变量返回值”写法这比静态变量更安全——递归发生在局部变量的修改上返回值逐层传回。5.1里的closureBfs也是纯局部变量不依赖任何类状态。5.3 charAt固定下标解析产生式状态一超过9位就翻车现象输入(10,a)→3程序匹配不到任何状态输入多字符符号时也会错位。原因整套代码建立在一个隐含假设上状态和字母都必须是单字符。(10,a)→3里charAt(1)取到的是1而实际状态是“10”永远对不上ε本身是单个字符没有大问题但像“aa”这种多字符符号也一样会错位。解决解析产生式不要用charAt定下标用split或正则拆出字段。常见做法是String[] parts t.split([(),→]); // parts[0] 当前状态, parts[1] 转移字符, parts[2] 目标状态然后把所有用到strings[i].charAt(1)、charAt(3)、charAt(6)的地方全部替换成parts[0]、parts[1]、parts[2]。改动点集中十几处引用一次换完。注意split里的正则分隔符涵盖了(、)、→、逗号加号表示连续分隔符也能拆干净。5.4 DuKong里的无效读空调用结果看起来读了实际没接住现象读a之后明明调用了RestltList最终输出的状态子集却少了ε可达状态。翻代码发现调用语句的确存在但闭包结果就是不对。原因RestltList(result, strings)的返回值没有被接收。RestltList内部的递归修改全部发生在其局部变量string上调用结束后对DuKong的result没有任何影响。真正把状态加进result的是前面那句result String.valueOf(strings[j].charAt(6))。解决删除这一行无效调用保留result 或者改成result RestltList(result, strings)让返回值覆盖result。推荐前者因为外层for循环本身已经会检查新增字符叠罗汉式的重复递归反而增加死循环风险。5.5 不去重归一化同一个状态子集被当成无数个不同集合现象BFS扩展时队列越来越长all里出现一堆内容相同、字符顺序不同的集合比如“12”和“21”程序永远跑不完。原因String拼接的天然缺陷——集合的字符顺序由产生式匹配顺序决定顺序不同字符串就不同ArrayList.contains对比字符串自然认为“12”和“21”不相等于是无限入队。解决每个状态子集在入队前先归一化。第四章开头的normalize方法用TreeSet排序后重新拼接保证集合只有一个规范表示。另一个更彻底的方式是把所有集合类变量从String改成Set 或Set 让HashSet自己去重。课程设计里为了输出方便保留String方案但真实项目中一定用Set。6. 状态转换图布局与验证技巧让输出真正可复用6.1 一个能通用到任何NFA的分层布局法报告要求“状态结点大小位置布局合理具有通用性”。用固定的网格坐标必然翻车我项目里用的是分层布局X放在最左侧Y放在最右侧中间的所有状态按“从X出发的最短ε路径长度”分层。第0层放种子状态第1层放种子经一条ε到达的状态依次类推没有ε路径的状态按读a/b时的出现顺序补到最后一层。同层节点从上到下均匀排布自环的节点单独让出一段弧线的空间避免箭头穿过其他节点。这样无论NFA多复杂图的结构都稳定不会出现节点堆叠。更快的办法是导出成GraphViz的DOT文件让布局引擎处理。我常把程序里算好的状态转移表直接转成digraph NFA { rankdirLR; node [shapecircle]; X - 5 [labelε]; 5 - 1 [labelε]; 5 - 5 [labela,b]; 1 - 3 [labela]; 1 - 4 [labelb]; 2 - 6 [labelε]; 6 - Y [labelε]; Y [shapedoublecircle]; }rankdirLR让图从左往右排与X在最左、Y在最右的直觉一致doublecircle标出终态Y。DOT文件能用GraphViz套件直接渲染成PNG不需要在Java里手算坐标。6.2 验证程序正确性的三个力度第一个力度是人工手推。拿例二那种不超过4个状态的NFA在纸上列出S0、S1、S2和它们的Ia再跑程序对比这是最廉价的方式。第二个力度是造环状ε测试用例。手动加一条(A,ε)→B、B→ε→A如果程序报StackOverflow或死循环说明5.1的修复还没生效。环状ε是ε闭包实现的分水岭能处理环才说明代码不是只对“线性输入”有效。第三个力度是交叉验证。同一个NFA用《编译原理》教材里的子集构造法表格手算一遍把表格里的每个集合与程序输出的状态子集逐一比对。这一步顺便把NFA转DFA的move和closure两个阶段都验了。6.3 从ε闭包到完整子集构造法这份资源其实已经把一个正经词法分析器最难的前半段做了只要你把4.1节循环稍加修改——在求出每个Ia时同时记录“这是从哪个集合、读了哪个字母到达的”——就能输出DFA的状态转移表。再把转移表用6.1的DOT导出你就有了一份能看清的NFA→DFA全过程。后续还可以做DFA最小化那是另一个课题了。从我当时的教训来说这类闭包算法的调试最大的敌人不是不会写而是“看起来写对了”。我后来养成了一个习惯任何NFA相关的程序先把状态表和转移表分别存成两个文件再单独写一个打印函数把所有ε出边、字母出边按状态列出来眼睛对着表过一遍才动主逻辑。这个习惯帮我省掉了大量的复盘时间。希望这次的拆解对你有帮助。本文还有配套的精品资源点击获取