简介面向计算机专业学生与编译原理课程设计学习者的一份Java实现课程设计报告聚焦有限自动机NFA的空闭包ε-closure(I)计算。报告按需求分析、概要设计、详细设计、测试与分析、用户使用说明与总结展开围绕读入NFA、保存转换关系、输出全部状态子集及指定状态子集的空闭包进行说明并交代引入初态X与终态Y、递归读空、对状态子集读字母表、逐步扩展状态子集直至不再产生新集合等关键模块最终以状态转换图呈现自动机结构并讨论状态结点大小与位置布局的通用性要求、测试数据与结果分析。压缩包仅含1个docx文件大小约177KB附录附有Java程序源代码便于对照报告理解算法落地与测试用例设计。当前已有1287人学习下载适合用作课程设计模板、实验参考或答辩前梳理材料。1. 从一份课程设计说起NFA 空闭包到底要用代码做什么手算一遍 ε-closure(I) 不难难的是算到第十几个状态子集时还能保证不漏一条 ε 弧。编译原理课上讲子集构造黑板上一画就过去了真让你用 Java 把它落成一个能读文件、能输出全部状态子集、还能画出状态转换图的程序多数人会卡在两处递归求闭包时结果收不全以及从字符串里抠状态名时下标对不上。这份《编译原理 ε-closureI的程序实现》课程设计报告就是一个完整的落地样本——输入任意 NFA 的状态转移函数程序输出所有状态子集的空闭包、指定子集的空闭包并渲染出自动机的状态转换图。它适合两类读者正在做编译原理课程设计、需要一份 Java 参考实现的学生以及想复习子集构造细节、看看 move 和 ε-closure 这两步在代码里怎么拆的开发者。代码量不大坑却不少值得逐行拆开看。2. 工程结构与数据模型NFA 怎么被读进内存这个项目没有上框架也没有引入第三方依赖一个 JDK 加几个 .java 文件就够跑。正因为简单它把「输入用什么格式表达」「状态子集用什么结构存」这两个决定后续所有代码形态的问题摆在了台面上。先看骨架再看数据。2.1 目录、运行方式与输入文件格式报告里的程序是控制台应用类分得比较散入口一个 Main工具方法一个 Utils剩下的是算法函数。按一线开发的习惯整理成下面这样跑起来最省事# 目录结构按实际代码整理 nfa-closure/ ├── src/ │ ├── Main.java # 入口读文件、调度各模块 │ ├── Utils.java # 字符串与数组互转、格式化输出 │ └── Closure.java # 读空、读字母、求子集 ├── data/ │ └── nfa.txt # 输入的 NFA 定义 └── out/ # 编译产物编译和运行只需要两条命令注意-encoding UTF-8输入文件里有 ε 这个字符不指定编码在部分环境下会读成乱码进而让后面的字符比较全部失效——这个坑后面还会细说。javac -encoding UTF-8 -d out src/*.java java -cp out Main data/nfa.txt输入文件的格式是三条内容拼起来的第一行是全部状态第二行是字母表之后每行一条产生式。下面这份对应报告里的例子一X,1,2,3,4,5,6,Y a,b (X,ε)→5 (5,a)→5 (5,b)→5 (5,ε)→1 (1,a)→3 (1,b)→4 (3,a)→2 (4,b)→2 (2,ε)→6 (6,a)→6 (6,b)→6 (6,ε)→Y读文件这一步没有太多花样按行 split第一行按逗号拆成状态数组第二行拆成字母表剩下的原样塞进String[] functionStrings。这里有一个隐含约定必须记住状态名和字母都只占一个字符。整个项目的解析逻辑建立在这个前提上一旦你把状态命名成q0、q10解析就全线崩具体原因见 2.2 节。2.2 产生式的字符串表示与下标解析报告里最「省事」也最脆的一处设计是把一条转移关系当成定长字符串(1,a)→3来对待然后用charAt按下标取字段。位置约定是这样的下标0123456字符(源状态,字母或 ε)→目标状态于是strings[i].charAt(1)取源状态charAt(3)取字母charAt(6)取目标状态。代码里到处是这种写法// 判断产生式 strings[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)); } }这段逻辑的意图很清楚拿当前状态的最后一个字符去和每条产生式的源状态下标 1比相等再看字母位下标 3是不是 ε是就把目标状态下标 6追加进来。问题在于它对输入格式的假设太硬——状态必须是单字符、箭头必须是单个→字符、括号和逗号一个都不能少。少一个空格没问题多一个空格比如(1, a)→3就会让字母位变成空格整个匹配静默失效程序不报错但结果错最难查。我一般会把这种定长下标解析换成一次正则拆分规则在启动时编译一次后续只做字段比较既快又不会因为格式微调翻车import java.util.regex.*; // 一条产生式(源状态,字母)→目标状态中间允许有空白 private static final Pattern RULE Pattern.compile(^\\(\\s*(.?)\\s*,\\s*(.?)\\s*\\)\\s*→\\s*(.?)\\s*$); /** * 把 (1,a)→3 拆成 [1, a, 3] * group(1) 源状态group(2) 字母ε 也在此列group(3) 目标状态 * 返回 null 表示这行不合法调用方跳过并提示行号 */ public static String[] parseRule(String line, int lineNo) { Matcher m RULE.matcher(line); if (!m.find()) { System.err.println(第 lineNo 行格式不对已跳过: line); return null; } return new String[]{ m.group(1), m.group(2), m.group(3) }; }用String[]而不是自定义类是为了和原代码里的String[] functionStrings平滑对接如果你想更彻底一点定义一个record Rule(String from, String symbol, String to)会让后面所有r[0].equals(...)变成r.from().equals(...)可读性直接上一个台阶而且状态名多字符也没问题。这一步改造的成本不到半小时收益是后面所有算法函数都不用再关心格式。2.3 数组、哈希表与 Set 在程序里各管什么报告里写「主要用到数组、图以及哈希表」落到代码上是三类容器各司其职String[] functionStrings一次性读入的全部产生式只读不改遍历成本低是这个规模下最合适的选择。SetString表示一个状态子集 I。选 Set 而不是 List 的理由很实在——子集构造里要频繁判断「这个状态子集是否已经出现过」用SetSetString的contains就是 O(1) 级别的哈希比较而且 Set 的equals与元素顺序无关{1,2,3}和{3,1,2}会被认为是同一个子集正好符合数学定义。MapSetString, SetString把每个状态子集映射到它的空闭包最后一次性输出。主循环里驱动子集展开的那层结构报告用的是 map 加迭代器其实换成双端队列更顺手import java.util.*; SetSetString dstates new LinkedHashSet(); // 已发现的全部子集保序 DequeSetString work new ArrayDeque(); // 待处理队列 SetString start Closure.closure(Set.of(X), rules); dstates.add(start); work.add(start); while (!work.isEmpty()) { SetString I work.poll(); for (String a : alphabet) { SetString next Closure.closure(Closure.move(I, a, rules), rules); if (next.isEmpty()) continue; // 空集不入表和报告的约定一致 if (dstates.add(next)) work.add(next); // add 返回 true 说明是新子集 } }这里用LinkedHashSet而不是HashSet是因为最后的输出要给人看。HashSet的迭代顺序依赖哈希值同一份输入两次运行可能打出不同的顺序调 bug 时会让你怀疑人生——明明代码没改输出怎么变了。LinkedHashSet按插入顺序迭代TreeSet按字典序两者都比HashSet适合做「有输出」的集合。提示状态 ID 如果用String存排序是按字典序的10会排在2前面。要输出好看可以在打印时套一个比较器按数值排。3. 三个函数撑起 ε-closure从 X 的闭包到全部状态子集整个项目的算法核心其实只有三件事给一个状态求它的 ε 闭包、给一个子集读一个字母做 move、把这两步串成子集构造。报告作者在「详细设计」里反复强调的一句话很到位读字母前后都要考虑读空否则经过 a 又经过 ε、或者先 ε 再 a 的情况就漏了。下面按调用顺序拆。3.1 先给 NFA 加一个初态 X 和一个终态 Y子集构造的标准做法是给 NFA 补一个唯一初态 X用 ε 弧连到原来的所有初态再补一个唯一终态 Y让原来所有终态用 ε 弧连到 Y。这样做的好处是 DFA 的初态就是 ε-closure({X})不用特判「有多个初态怎么办」。报告里对这一步做了简化X 只连到非空初态集合中的某一个状态Y 同理只从一个终态连过来并且直接把这两条 ε 弧写进状态转移函数里当作普通产生式处理。作者自己也说了当时觉得「引一条空弧到任意一个状态节点」写起来太麻烦往下做就做不下去了。这个取舍在课程设计的语境下可以理解——它不影响闭包算法的正确性只是丢掉了「多初态/多终态」的通用性。如果你要拿去处理真实自动机把 X 连到所有初态、所有终态连到 Y只是往rules里多 push 几条记录的事// 补唯一初态 X 与唯一终态 Y多初态/多终态都能覆盖 ListString[] rules new ArrayList(parsedRules); for (String s : initialStates) rules.add(new String[]{X, ε, s}); for (String s : finalStates) rules.add(new String[]{ε null ? s : s, ε, Y});参数说明initialStates是从输入文件里读出来的原始初态集合finalStates是原始终态集合。注意这里不要在原来的functionStrings上原地改拷贝一份再追加否则重复运行会重复追加X 的出边越跑越多——这是我在类似项目里真实翻过的车。3.2 对 X 读空递归求第一个状态子集补完 X 之后第一个状态子集就是 ε-closure({X})。报告里为此单独写了一个函数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; }先说参数string是「已经收集到的状态串」初始传Xstrings是全部产生式。返回值是扩展后的状态串。这段代码有两个必须点出来的问题。第一Java 的String是不可变对象string c等价于string string c改的是当前栈帧的局部变量递归调用RestltList(string, strings)里继续拼接只影响递归那一层的局部变量函数返回后这个新串就被丢掉了。结果就是闭包只扩了一层X→5→1→3这种链式 ε 路径收不全。第二如果 ε 弧构成环比如1→2、2→1递归没有任何判重直接栈溢出。修法有轻有重。轻的改一行把返回值接住string RestltList(string strings[i].charAt(6), strings);重的也是我推荐的是彻底放弃字符串拼接用「集合 显式栈」的迭代写法天然判重、天然没有递归深度问题/** * 求 states 的 ε 闭包 * param states 起始状态集合闭包结果一定包含其中每个元素 * param rules 全部产生式元素形如 [源状态, 字母, 目标状态] * return 闭包集合用 LinkedHashSet 保证输出顺序稳定 */ public static SetString closure(SetString states, ListString[] rules) { SetString result new LinkedHashSet(states); // 闭包首先包含自己 DequeString stack new ArrayDeque(states); while (!stack.isEmpty()) { String cur stack.pop(); for (String[] r : rules) { // 源状态匹配、字母是 ε、且目标状态是新的才入栈 if (r[0].equals(cur) ε.equals(r[1]) result.add(r[2])) { stack.push(r[2]); } } } return result; }result.add(r[2])的返回值在这里承担了两个职责既判断「是不是新状态」又顺手完成了去重。环状 ε 弧在第二次访问同一状态时add返回 false循环自然收敛。这套写法的时间复杂度是 O(|状态| × |产生式|)课程设计里几十条产生式跑起来毫无压力。3.3 只读字母的 Iamove 函数的极简版有了闭包函数接下来要给一个状态子集读一个字母。报告里对应的是RestltListA输入三个参数状态子集、待读字母、全部产生式输出读完之后到达的状态串。// 报告原实现 public static String RestltListA(String string, String s, String[] strings) { String resultA ; for (int i 0; i strings.length; i) { 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是单个状态注意这里传的不是子集报告在调用处对子集做了外层循环s是要读的字母strings是产生式数组。逻辑就是「源状态等于当前状态、字母等于 a就把目标状态拼进去」。这段代码本身没有致命问题只是把「一个子集的 move」拆成了外层循环加单状态函数调用方要自己套两层。换成集合版本更直观也顺便解决了结果重复的问题/** * move(I, a)子集 I 中所有状态经过字母 a 直达的状态集合 * 不包含 ε 闭包闭包在外面套 */ public static SetString move(SetString states, String symbol, ListString[] rules) { SetString result new LinkedHashSet(); for (String s : states) { for (String[] r : rules) { if (r[0].equals(s) r[1].equals(symbol)) { result.add(r[2]); } } } return result; }注意这里不能判断 ε——move 只处理字母弧闭包那一层另外算。报告作者在「6 总结」里写过一句很有价值的体会一开始想把读空和读字母塞进一个函数纠结很久写不出来后来拆成两个函数求子集的时候按「读空、读 a、再读空」的顺序串起来逻辑一下子就清楚了。这个拆法就是标准的 ε-closure(move(I, a))教科书上的公式和代码里的调用顺序一一对应。3.4 读空、读 a、再读空子集构造主循环把前两个函数拼起来就得到一条完整的推进规则。报告里写得很直白求 Ia 不只是看 a 弧还要看 a 弧到达的状态能不能再走 ε 弧到别处所以读字母前后都要读空。对应到代码是三层// 计算 ε-closure(move(I, a)) SetString moved move(I, a, rules); // 第一层只读 a SetString closed closure(moved, rules); // 第二层对结果读空 // 如果还要考虑先读空再读 a的情况I 本身应当已经是闭包第三层的「读 a 之前读空」其实藏在主循环里work队列里存的每个I都是上一轮closure(...)的产物本身就是闭包所以进入move之前不用再补。这也解释了为什么报告里DuKong那个函数传的参数是「子集读 a 之后的结果」而不是原始子集——它只补后半个闭包。理解这一点DuKong和RestltList看起来重复的问题就不成立了它们作用于链路上的不同位置。完整的主循环在 2.3 节已经给过这里补上「输出指定状态子集的空闭包」这个需求的落点。报告的基本要求里有一条是「输出给定状态子集的空闭包」实现上就是遍历输入字符把用户给的子集构造出来直接调closure// 用户输入的 I例如 1,3 SetString query new LinkedHashSet(Arrays.asList(input.split(,))); SetString answer closure(query, rules); System.out.println(ε-closure( query ) answer);参数说明input是从控制台读的一行逗号分隔closure内部会先把query的元素全部塞进结果所以 I 里的状态一定出现在答案里符合闭包「包含自身」的定义。如果用户输入了不存在的状态closure不会报错只会原样返回这一点在交互时最好加一句校验把非法状态提前拦下来。4. 状态转换图输出把转移函数画成能看懂的图报告的第四个基本要求是「以状态转换图方式输出用户输入的有限自动机要求状态结点大小位置布局合理具有通用性」。这一块常常被当成加分项糊弄过去实际上它比算法更考验工程判断结点位置是算出来的还是写死的直接决定了换个输入会不会糊成一团。4.1 结点布局先定层再定坐标最省事的画法是把所有结点摆在一个圆上半径随结点数增长。这种做法对课程设计规模的自动机十个上下状态足够而且「通用性」天然满足——不管输入几个状态坐标都由公式算不写死。/** * 环形布局把 n 个状态均匀摆在一个圆上 * param states 全部状态顺序决定谁在圆周的哪个位置 * return 状态名 - [x, y] 坐标 */ public static MapString, int[] ringLayout(ListString states) { int n states.size(); int radius Math.max(140, 36 * n); // 结点越多圆越大 int cx radius 60, cy radius 60; // 圆心留出边距 MapString, int[] pos new LinkedHashMap(); double step 2 * Math.PI / n; for (int i 0; i n; i) { double theta -Math.PI / 2 i * step; // 从正上方开始摆 pos.put(states.get(i), new int[]{ (int) Math.round(cx radius * Math.cos(theta)), (int) Math.round(cy radius * Math.sin(theta)) }); } return pos; }参数说明radius取36 * n和 140 的较大值保证结点之间至少留出约一个结点直径的间隙-Math.PI / 2的起始角让第一个状态落在正上方视觉上有明确的「入口」感。这套公式的代价是边会互相穿插但结点本身不会重叠满足「布局合理」的最低要求。真要讲究可以改成层次布局BFS 从 X 出发算每个状态的层号同层水平排开层间垂直拉开边的走向会干净得多代价是遇到不可达状态要单独处理。4.2 Swing 画布与 Graphviz 两条路线报告里选的是 Swing 直接画一个JPanel重写paintComponent用Graphics2D先画边后画结点。核心代码不长Override protected void paintComponent(Graphics g) { super.paintComponent(g); Graphics2D g2 (Graphics2D) g; g2.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON); g2.setStroke(new BasicStroke(1.6f)); int r 22; // 结点半径 // 先画边避免边压住结点文字 for (String[] rule : rules) { int[] a pos.get(rule[0]), b pos.get(rule[2]); if (a null || b null) continue; g2.setColor(Color.GRAY); g2.drawLine(a[0], a[1], b[0], b[1]); // 标签画在中点偏上的位置简单避让 g2.setColor(Color.DARK_GRAY); g2.drawString(rule[1], (a[0] b[0]) / 2, (a[1] b[1]) / 2 - 4); } // 后画结点 for (Map.EntryString, int[] e : pos.entrySet()) { int[] p e.getValue(); g2.setColor(new Color(0xF2F6FC)); g2.fillOval(p[0] - r, p[1] - r, r * 2, r * 2); g2.setColor(new Color(0x33507A)); g2.drawOval(p[0] - r, p[1] - r, r * 2, r * 2); g2.drawString(e.getKey(), p[0] - 6, p[1] 5); } }参数上要注意三点r是结点半径文字用drawString居中时要减去大约一半字宽、加上约 5px 的基线偏移paintComponent里不要改全局状态后不还原Swing 会复用Graphics对象密集图里中点标签一定重叠最少也要按边方向偏移几像素。另一条路线是生成.dot文件交给外部渲染几十行代码布局质量却高得多尤其是边多的时候/** * 生成 Graphviz dot 文本重定向到文件后用 dot -Tpng 出图 */ public static String toDot(ListString states, ListString[] rules) { StringBuilder sb new StringBuilder(digraph NFA {\n rankdirLR;\n node [shapecircle];\n); for (String s : states) sb.append( \).append(s).append(\;\n); for (String[] r : rules) { sb.append( \).append(r[0]).append(\ - \).append(r[2]) .append(\ [label\).append(r[1]).append(\];\n); } return sb.append(}\n).toString(); }rankdirLR让图从左往右排比默认的自上而下更接近自动机的阅读习惯。这份输出的价值在于「可复现」——同一份 NFA 任何时候生成的图一模一样方便写进报告。4.3 边的细节自环、多重边与 ε 标签真正让图画得难看的不是布局是边的细节处理。三件事必须提前想清楚自环。(5,a)→5这种边如果直接drawLine长度为零什么都看不见。常见做法是从结点上方引一个小圆弧再绕回来// 自环以结点正上方为顶点画一段二次曲线 if (rule[0].equals(rule[2])) { int[] p pos.get(rule[0]); g2.drawArc(p[0] - 14, p[1] - r - 22, 28, 26, 0, 360); g2.drawString(rule[1], p[0] - 4, p[1] - r - 26); continue; }多重边。两个状态之间既有一条 a 弧又有一条 b 弧时两条直线完全重合标签叠在一起。简单的解法是把第 k 条平行边整体平移k * 6像素或者改成曲线并控制弯曲度。ε 标签。输入文件里写的是希腊字母 εSwing 默认字体能不能显示要看系统。稳妥做法是设一个支持希腊字母的字体如Dialog或者在渲染时把ε替换成e并在图例里说明。这一点在报告里没有提但在实际运行时是肉眼可见的差异——标签位置出现一个空心方块多半就是这个原因。注意drawString画中文状态名在部分环境会走字形回退字号和位置都得重新量别沿用单字符时的那套偏移量。5. 踩坑排查字符串递归与集合遍历的五个翻车现场这个项目的代码量撑死几百行但我在复现和改造的过程中踩到的坑密度不低而且每一个都不是「写错了报个错」那么友好多数是不报错但结果不对。下面五条按「现象 → 原因 → 解决」组织都是可以直接对照自己代码的。5.1 闭包只扩了一层长 ε 链收不全现象输入(X,ε)→5 (5,ε)→1 (1,ε)→3期望ε-closure(X) {X,5,1,3}实际只得到{X,5}程序正常退出没有任何异常。原因RestltList里写了string ...之后调RestltList(string, strings)但没接返回值。Java 的String不可变只是把当前栈帧的局部变量指向新串递归里再拼出来的东西返回后就被丢了实际只生效了最外层一次。解决要么把返回值接住string RestltList(string c, strings)要么直接换成 3.2 节那套「Set 栈」的迭代写法。我现在的习惯是只要函数里出现递归改字符串第一反应就是换成可变容器省得下次又忘。5.2 ε 环把递归打成栈溢出现象输入里存在(1,ε)→2 (2,ε)→1运行几秒后抛StackOverflowError栈帧全是同一个函数名。原因递归实现没有任何「访问过」标记环上的两个状态互相触发无限深入。解决加一个visited集合每进一个状态先if (!visited.add(s)) return;。用 3.2 节的迭代版本连改都不用改result.add(r[2])的返回值本身就是判重逻辑。5.3 状态名换成多字符立刻数组越界现象把输入里的状态从1、2改成q1、q2程序在strings[i].charAt(6)处抛StringIndexOutOfBoundsException或者不抛异常但读出来的目标状态是半个名字。原因解析用的是定长下标charAt(1)取源状态、charAt(3)取字母、charAt(6)取目标态全部建立在「状态名和字母都只占一个字符」这个前提上。状态名一变长后面所有字段的位置全部右移。解决用 2.2 节的正则拆分代替charAt。这一步越早做越好等到算法写完再改所有函数都得跟着动。5.4 一边遍历 Set 一边往里加抛并发修改异常现象求「所有状态子集的空闭包」那段偶尔抛ConcurrentModificationException重跑一次可能又不抛了。原因外层用Iterator遍历状态子集内层调用的读空函数如果直接往同一个集合里add迭代器的modCount就对不上。这类 bug 的恶心之处在于「偶发」——取决于哈希顺序和元素个数测试时跑十次过一次。解决所有「遍历 扩展」的地方都把新元素收进一个独立的临时集合遍历结束后再addAll回去。或者干脆换成Deque驱动的工作队列天然避开迭代器失效。5.5 两次运行输出顺序不一样误以为算法有随机性现象同一份输入连跑两次状态子集的打印顺序变了肉眼看不出规律一度怀疑是某处用了随机数。原因HashSet的迭代顺序由元素的哈希值决定而字符串的哈希是稳定的——问题出在状态子集本身是SetStringSet的hashCode是元素哈希之和元素多了以后桶分布变化遍历顺序就跟着变。程序没错是输出没做归一化。解决存状态子集用LinkedHashSet保留插入顺序打印之前再套一层TreeSet按名字排序。调 bug 阶段这一步不能省输出稳定了才谈得上对比两次运行的结果。提示这五个坑里有四个的共同特征是「不抛异常、结果悄悄错」。写这类算法程序断言比打印更有用——每求出一个子集就断言它包含自己的所有 ε 后继错了当场停。6. 二次开发把课程级代码改成能用的子集构造工具这份代码作为课程设计是合格的逻辑讲清楚了测试用例也覆盖了带环、带空集、带多终态几种情况。但要拿去做二次开发我建议按下面的顺序动刀收益从高到低改造点现状改成收益产生式解析charAt定长下标正则拆分 /record Rule支持多字符状态名格式容错闭包计算递归拼字符串Set 显式栈消除栈溢出天然判重子集驱动map 加迭代器DequeLinkedHashSet输出稳定无并发修改空集处理字符串判空Set.isEmpty()语义清晰不会把{}当空集图输出Swing 手绘生成.dot布局质量高可复现改造的验证方法很简单也很有效自己手写三组 NFA一组纯 ε 链、一组带 ε 环、一组带不可达状态把程序输出和手算结果逐行对。特别是不可达状态那一组——子集构造从 X 出发永远走不到的状态不会出现在dstates里如果你的输出里出现了说明驱动循环写错了。如果想再往前走一步把「状态子集 → 空闭包」的映射顺手做成 DFA 的转移表这个项目就能直接给词法分析器当后端用DFA 的每个状态对应一个SetString转移表就是MapSetString, MapString, SetString输入一个字符查一次表。报告里已经把这个映射mapmax建出来了只是拿去打印而没有继续用稍微改几行就能接上。最后一个技巧关于「读空、读 a、再读空」这个顺序。很多人第一次写会想着把三步揉进一个函数包括报告作者自己也说在这上面纠结了好一阵。我的经验是死死守住closure(move(I, a))这个公式一个函数只干一件事调用处把顺序写死别想着优化。真出问题时你能一眼看出是 move 错了还是 closure 错了揉在一起就只能靠打印大法慢慢试。这份报告我是当成一面镜子看的——它记录的那些纠结我自己一行行写的时候一个不落地重新纠结了一遍。从那以后我每次写递归求闭包第一件事就是先把判重的 Set 建出来再动循环算是给自己留的后悔药。希望帮到你。本文还有配套的精品资源点击获取
