简介面向编译原理课程学习者资源围绕NFA到DFA的转换实验展开以Python实现核心算法帮助理解子集构造法与词法分析底层的正则表达式机制。压缩包共3个文件、约607KB包括Python转换脚本、NFA描述文本和Word版实验报告分别对应算法实现、输入数据与理论总结结构简洁且可直接应用。资源已有1085人学习下载适合正在完成相关实验、期末复习或准备面试的学生参考。Python脚本采用类与函数清晰封装NFA和DFA的数据结构支持状态集合、转移规则及接受状态处理可运行并观察转换过程NFA数据文件提供现成的测试样例实验报告则系统梳理了NFA定义、子集构造法步骤、代码实现细节、实验状态图比较以及常见问题与调试思路既帮助读者深入理解非确定性与确定性自动机的差异也为独立实现或二次开发提供了良好起点。1. 从NFA到DFA词法分析器落地前必须跨过的那道坎写词法分析器时正则表达式写起来很爽比如(0|1)*101一行就完事但程序不会真的拿正则去逐字符匹配它需要一张“当前状态 输入字符 → 下一状态”的确定性跳转表。编译原理课上的 NFA 转 DFA做的就是这件事把正则对应的非确定自动机转换成确定的、可以直接驱动匹配的状态表。标题里这个 Python 实现核心就是子集构造法subset construction。适合正在做编译原理实验、或者想给自己写的词法分析器换掉一坨 if-else 的开发者。这篇文章会把原理、代码、验证和坑一次讲透让你能照着跑通。2. 子集构造法拆解epsilon闭包为什么是NFA转DFA的钥匙2.1 不确定性从哪来一条输入字符可能同时走多条边NFA 与 DFA 的根本差异就一个字确定与否。DFA 里每个状态遇到每个输入字符只有一个去向NFA 里同一个状态读同一个字符可能有好几条出边也可能一条都没有。更麻烦的是NFA 还允许“不消耗任何字符”的跳转也就是 epsilon 边。以(0|1)*101为例输入的字符串是101时NFA 在读入第一个1之后其实同时存在两种可能一是还在(0|1)*的循环里这是一条路径二是已经进入了后缀101的第一个1匹配阶段另一条路径同时也在往前走。两条路径都会继续读后面的0和1直到输入结束再看哪条路径落到了接受状态。真实程序不可能无限并行维护每一条路径遇到分支最多只能记录“当前可能在哪几个状态”。子集构造法就是把这个“可能在哪几个状态”打包成一个集合NFA 的一个状态集合对应 DFA 的一个状态。转换完成后DFA 每次只走一条路匹配复杂度降到 O(n)。2.2 epsilon闭包先走完所有不消耗字符的“免费跳转”epsilon 边是 NFA 里最反直觉的设计它不需要任何输入字符就能跳转。Thompson 构造法构造正则对应的 NFA 时会用大量 epsilon 边把子自动机拼接起来所以从某个状态出发不读任何字符就能走到很多其他状态。epsilon 闭包的定义就是从给定状态集合出发只沿 epsilon 边能到达的所有状态并且包含状态自身。def epsilon_closure(states, epsilon_transitions): 从 states 出发沿 epsilon 边能到达的所有状态包含自身。 epsilon_transitions: dict[int, set[int]]state - 能免费跳转到的状态集合 stack list(states) closure set(states) while stack: s stack.pop() for nxt in epsilon_transitions.get(s, set()): if nxt not in closure: closure.add(nxt) stack.append(nxt) return closure这段代码用的是显式栈而不是递归。原因很实际epsilon 边很容易成环比如(0|1)*的 NFA 里循环结构会让闭包计算在状态之间打转。递归写法一旦忘记标记 visited直接 RecursionError就算不炸状态一多也可能触及递归深度上限。显式栈配合closure集合做去重是编译原理实验里最稳的写法。参数上states可以是单个状态包成的集合也可以是move函数返回的集合epsilon_transitions.get(s, set())处理了“某状态没有 epsilon 出边”的情况避免 KeyError。这个函数的返回值会被反复用到建议把它作为整个转换流程的公共工具函数后面所有步骤都依赖它。2.3 move函数只在字符边上走一步不要顺手吃掉epsilonmove 函数负责“读入一个字符”这件事。它跟 epsilon 闭包刚好互补只沿着普通字符边前进不处理 epsilon 边。def move(states, symbol, transitions): 从 states 出发只沿 symbol 对应的字符边走一步返回到达的状态集合。 transitions: dict[tuple[int, str], set[int]]key 是 (状态, 字符) result set() for s in states: result.update(transitions.get((s, symbol), set())) return result这里最容易踩的坑是把 move 和 epsilon 闭包的顺序搞反。子集构造里每一步的标准姿势是先 move再对 move 的结果做 epsilon 闭包。因为 move 之后到达的状态很可能还有 epsilon 出边不闭包就会漏掉一批“免费可达”的状态反过来先闭包再 move 也会出错——epsilon 能到达的状态里可能存在能走当前字符出边的状态顺序乱了结果就完全不一样。所以两条规则要钉死epsilon 闭包不读字符move 只读一个字符两者必须组合使用且顺序永远是 move 在前、closure 在后。2.4 子集构造法完整流程NFA状态集合就是DFA状态子集构造法的整个过程可以归纳成五步计算 NFA 起始状态的 epsilon 闭包作为 DFA 的初始状态初始状态本身可能是个大集合。对这个 DFA 状态里的所有 NFA 状态逐个遍历字母表中的字符执行 move epsilon 闭包。如果计算出的集合非空先看它是否已经存在于 DFA 状态列表里不存在就添加并标记为待处理状态。记录下(当前DFA状态, 字符) → 目标DFA状态的跳转关系。重复直到没有新的 DFA 状态出现。“一个 NFA 状态集合对应一个 DFA 状态”这句话是整个算法的钥匙。NFA 的状态数量是有限的NFA 状态集合的数量最多是 2 的 n 次方所以算法必然终止。实际构造出来的 DFA 状态数通常远少于最坏情况比如(0|1)*101这个正则最终只有 5 个 DFA 状态这在下一章会实际跑出来。3. Python实现NFA转DFA状态表生成与编号3.1 NFA的数据结构字符转移和epsilon转移分开存为了让转换代码可读、不给自己挖坑NFA 的数据结构我会用一个轻量类来承载。关键原则是字符转移和 epsilon 转移必须分开存放千万不要共用一个字典。混在一起的话第五节会说到字母表里很容易多出一列垃圾转移。class NFA: 用字典表示转移关系的 NFA。 states: set[int]状态编号集合 alphabet: set[str]输入符号集合不含 epsilon transitions: dict[(int, str), set[int]]字符转移从某状态读某字符到哪些状态 epsilon_transitions: dict[int, set[int]]epsilon 转移从某状态免费跳到哪些状态 start_state: int开始状态 accept_states: set[int]接受状态集合 def __init__(self, states, alphabet, transitions, epsilon_transitions, start_state, accept_states): self.states states self.alphabet alphabet self.transitions transitions self.epsilon_transitions epsilon_transitions self.start_state start_state self.accept_states accept_states# 一个最简单的 NFA 示例识别以 1 结尾的串简化演示用 nfa NFA( states{0, 1, 2}, alphabet{0, 1}, transitions{(0, 0): {0}, (0, 1): {1}, (1, 1): {2}}, epsilon_transitions{0: {2}}, start_state0, accept_states{2}, )转移表用(状态, 字符)作为 key是很自然的选择查表只需要transitions.get((state, chr), set())缺边直接返回空集合不用写一堆条件判断。状态编号建议直接用整数不要用字符串后面生成 DFA 状态编号时比较好对应。3.2 核心转换函数从起点闭包迭代到没有新状态def nfa_to_dfa(nfa): 把 NFA 转成 DFA返回状态列表、转移表和接受状态集合。 # 初始状态NFA 起始状态的 epsilon 闭包 start_closure frozenset(epsilon_closure({nfa.start_state}, nfa.epsilon_transitions)) dfa_states [start_closure] # 每个元素是一个 frozenset即一组 NFA 状态 dfa_transitions {} # (dfa_state_id, symbol) - dfa_state_id pending [0] # 待处理的 DFA 状态下标 while pending: current pending.pop() current_set dfa_states[current] for symbol in sorted(nfa.alphabet): # 先 move再 epsilon 闭包顺序不能反 next_set frozenset(epsilon_closure( move(current_set, symbol, nfa.transitions), nfa.epsilon_transitions )) if not next_set: continue # 空集合这个字符在当前 DFA 状态下没有去向 if next_set not in dfa_states: dfa_states.append(next_set) pending.append(len(dfa_states) - 1) target dfa_states.index(next_set) dfa_transitions[(current, symbol)] target accept_states { i for i, s in enumerate(dfa_states) if s nfa.accept_states } return dfa_states, dfa_transitions, accept_states逻辑核心在while pending循环里。每个 DFA 状态本质上是一个 NFA 状态集合所以用dfa_states这个列表保存所有 DFA 状态pending记录还没处理过出边的状态下标每新增一个 DFA 状态就把它丢进pending直到没有新状态为止。next_set转成frozenset是有意为之。dfa_states里保存的是集合而 Python 的set不可哈希没法放进字典当 keyfrozenset可以。用next_set not in dfa_states做存在性检查时frozenset和set的比较是基于内容的{1,2} frozenset({1,2})成立不影响查找。accept_states的判定用s nfa.accept_states只要 DFA 状态这个集合里包含任意一个 NFA 接受状态那这个 DFA 状态就应当被标记为接受状态。这是子集构造法的标准做法不需要所有 NFA 状态都是接受状态。3.3 输出为跳转表让DFA真正能进词法分析器转换函数返回的dfa_transitions是(状态, 字符) - 状态的字典这就是词法分析器需要的跳转表。但调试阶段直接看字典很不直观我会用一个打印函数把它变成表格方便核对每个状态的行为。def print_dfa(dfa_states, dfa_transitions, alphabet, accept_states): 把 DFA 状态表打印成可读表格缺失转移显示为 -。 header DFA状态\t \t.join(sorted(alphabet)) \t接受 print(header) for i in range(len(dfa_states)): row [str(i)] for sym in sorted(alphabet): target dfa_transitions.get((i, sym)) row.append(- if target is None else str(target)) row.append(是 if i in accept_states else ) print(\t.join(row)) # 用法 # dfa_states, dfa_transitions, accept nfa_to_dfa(nfa) # print_dfa(dfa_states, dfa_transitions, nfa.alphabet, accept)sorted(alphabet)保证打印出来的列顺序是固定的。这点很重要如果把set直接拿来排序输出同一个字母表每次运行的显示顺序可能不同调试时会误导人。缺失的转移用-显示比空白更清晰一眼能看出哪个状态在哪个字符上没有出口。3.4 复杂度与规模边界什么时候该换实现方式子集构造的最坏复杂度是 O(2^n)NFA 状态一多DFA 状态数可能指数增长。但编译原理实验里常见的正则比如标识符、数字字面量、0|1*101 这种构造出来的 DFA 状态数通常只有十几个到几十个上面这份实现完全够用。如果 NFA 状态数超过 50且你发现dfa_states.index(next_set)每次都做线性扫描成了瓶颈可以加一个{frozenset: id}的映射字典把查找从 O(n) 降到 O(1)。替换方式很简单新增状态时同时写state_id_map[frozenset(next_set)] len(dfa_states) - 1查重时直接查字典。这个优化在实验规模下不是必须的但理解它有助于读懂更复杂的工业级实现。4. 用(0|1)*101跑通全流程从正则构造NFA到DFA状态表4.1 手工构造Thompson NFA(0|1)*101 的 11 状态版本要验证转换代码得先有一个带 epsilon 转移的 NFA。用 Thompson 构造法把正则(0|1)*101拆开(0|1)*是循环选择结构101是三个字符依次连接。下面这个 11 状态版本是手写构造的epsilon 转移集中在最前面的循环部分后面的101序列直接走字符边够用来验证 epsilon 闭包和子集构造。def build_nfa(): 构造 (0|1)*101 对应的 NFA。 状态说明 0 - 整个 NFA 的起点 1 - (0|1) 选择结构的入口 2,3 - 0 分支的起止状态 4,5 - 1 分支的起止状态 6 - (0|1) 选择结构的出口 7 - 进入 101 后缀的连接点 8,9,10 - 依次匹配 1、0、1 的状态10 为接受状态 states set(range(11)) alphabet {0, 1} transitions { (2, 0): {3}, (4, 1): {5}, (7, 1): {8}, (8, 0): {9}, (9, 1): {10}, } epsilon_transitions { 0: {1, 7}, # 进入选择结构或直接跳过循环去匹配 101 1: {2, 4}, # 选择 0 分支或 1 分支 3: {6}, # 0 分支结束后进入选择出口 5: {6}, # 1 分支结束后进入选择出口 6: {1, 7}, # 出口既可以回到循环也可以进入 101 后缀 } return NFA(states, alphabet, transitions, epsilon_transitions, start_state0, accept_states{10})这个 NFA 的关键在状态 0、6 这两处 epsilon 转移。状态 0 的{1, 7}表示可以从起点直接进入(0|1)*循环也可以跳过循环直接匹配101这对应正则里*允许匹配空串。状态 6 的{1, 7}表示读完一轮(0|1)之后可以选择继续循环也可以退出循环去匹配101。两个 epsilon 分支正是验证闭包函数的好素材。4.2 跑转换并打印DFA状态表验证5个状态的结构把第 3 章的nfa_to_dfa直接拿来跑完整的验证脚本如下nfa build_nfa() dfa_states, dfa_transitions, accept nfa_to_dfa(nfa) print_dfa(dfa_states, dfa_transitions, nfa.alphabet, accept)输出如下DFA状态01接受012112232314432是这里每一行都是一个“NFA 状态集合”。比如 DFA 状态 0 对应的集合是{0,1,2,4,7}意思是读完当前已输入的前缀后NFA 可能同时停留在 0、1、2、4、7 这五个状态上。DFA 状态 0 读字符0到 DFA 状态 1实际语义是“NFA 状态集合{0,1,2,4,7}在读入0后经过 move 和 epsilon 闭包变成集合{1,2,3,4,6,7}”。看到这里你应该能感觉到验证 DFA 状态表的正确性不需要逐个人肉跟踪集合只需要用几个关键输入字符串去跑匹配看结果是否符合预期。4.3 用四个关键用例验证行为空串、101、1101、1010匹配驱动的代码很简单就是沿着状态表走字符def run_dfa(text, start_state, dfa_transitions, accept_states): state start_state for ch in text: nxt dfa_transitions.get((state, ch)) if nxt is None: return False state nxt return state in accept_states四个用例验证如下输入状态路径预期结果空串0不接收不接收1010→2→3→4接收接收11010→2→2→3→4接收接收10100→2→3→4→3不接收不接收空串对应(0|1)*匹配空但没有匹配到101所以不接收。1101之所以能接收是因为第一个1走了循环后面101完整匹配。1010在完整匹配出101之后又多了一个0从接受状态 4 走到状态 3最终停在非接受状态上。这组用例覆盖了“空串”、“正常匹配”、“匹配完成后多读字符”三种情况。如果你自己构造了新的正则建议也准备一组类似用例至少包含一个长匹配、一个前缀重复、一个多读字符的输入。能用这组用例跑通nfa_to_dfa的正确性基本可以放心。5. NFA转DFA的5个典型翻车点现象、原因与修复5.1 epsilon闭包写递归运行时直接 RecursionError现象epsilon_closure一旦遇到带循环的 NFA比如(0|1)*的结构程序要么直接抛RecursionError: maximum recursion depth exceeded要么卡死不动。原因epsilon 转移天然带环。状态 0 能跳到状态 1状态 1 又能跳回状态 0递归写法如果没有 visited 集合就在环里永远出不来。就算加了 visited递归深度也可能在状态很多时超过 Python 默认的 1000 层限制。解决用显式栈 closure集合标记也就是第 2 章那版代码。每次把新状态加入closure时立刻去重保证每个状态只被处理一次。这也是我在第 2 章专门强调“不要用递归”的原因。5.2 拿 set 当字典 keyTypeError 拦在转换之前现象写dfa_state_map[next_set] new_id时直接报TypeError: unhashable type: set。原因next_set是一个setPython 的set可变不能作为字典 key。很多初学者在保存 DFA 状态时直接把set塞进字典程序还没开始算就崩了。解决存进dfa_states或用作 key 之前统一转成frozenset。注意frozenset和set内容相同时可以相互比较{1,2} frozenset({1,2})是True不影响查重逻辑。核心转换函数里所有next_set都在构造完闭包后包一层frozenset(...)。5.3 epsilon 混进字母表DFA 多出一列垃圾转移现象打印出来的 DFA 状态表里出现了一个名为epsilon或ε的列而且所有行这一列的值都一样。检查dfa_transitions发现多了(状态, epsilon) → 状态的转移。原因NFA 的数据结构里把 epsilon 转移跟普通字符转移存在同一个字典里key 用(state, epsilon)。子集构造遍历字母表时alphabet里如果包含了epsilon这个字符串就会把它当成普通输入符号处理。解决构建 NFA 时就用两个独立字典存储transitions只放真实输入字符epsilon_transitions单独存。这样alphabet天然不包含 epsilon。如果是从 JSON 或文件里读 NFA 定义读入后做一次校验alphabet里不允许出现epsilon或ε有就报错。5.4 忽略死状态匹配到一半无路可走现象转换完成后某个(dfa_state, symbol)对应的dfa_transitions里没有记录。驱动函数一查get返回None直接判定匹配失败。但如果这个输入应该被词法分析器拒绝结果是对的问题是如果后面还有字符程序就停在半路行为看起来像“卡住了”。原因子集构造中move结果为空时代码直接continue没有给缺失转移定义去向。这在语义上是允许的缺边就是“不接受”。但对于要做 DFA 最小化或者打印完整跳转表的场景缺边会导致状态表不完整。解决按用途分两种情况。只做匹配验证缺边返回False即可要输出完整跳转表就显式加一个死状态dead state编号设为-1或len(dfa_states)把所有缺失转移全部指向它死状态在所有字符下都回到自身。这样状态表是完整的方阵最小化算法也能正常处理。5.5 DFA 状态编号不稳定同一份 NFA 两次运行结果不同现象同一个 NFA两次运行nfa_to_dfa生成的 DFA 状态编号顺序不一致在有测试断言的项目里这种“随机失败”非常折磨人。原因epsilon_closure和move内部用到set而 Pythonset的迭代顺序取决于哈希值同一进程每次运行哈希随机化遍历顺序不稳定。状态集合的生成顺序变了DFA 状态编号自然就变了。解决在需要确定性顺序的地方用sorted。nfa_to_dfa里遍历字母表时已经用了sorted(nfa.alphabet)epsilon_closure的初始stack可以用sorted(states)保证处理顺序稳定。对实验规模的状态数排序开销可以忽略换来的是可复现的调试结果。6. 从DFA状态表到词法分析器最小化、驱动与集成6.1 最小化不是必须但状态多到影响效率时要做第 4 章转换出的 DFA 只有 5 个状态直接用没问题。但真实词法分析器里标识符、关键字、数字字面量的 NFA 合并后DFA 状态数可能上百其中有不少行为等价的状态能够合并。DFA 最小化标准的做法是划分法先把状态分成接受/非接受两组然后反复根据“读同一个字符落到哪个组”来细分组直到每个组内的状态行为完全一致。实现要点就两个一是初始划分必须以接受状态为界二是分组签名要看全部字符的落点。6.2 驱动DFA匹配的20行代码最长匹配与优先级状态表到手后词法分析器的驱动逻辑其实很短。这里给出一个支持最长匹配的版本词法分析器常用的策略是尽可能多读字符直到无法转移为止然后回退到最后一个接受状态。def lex_token(text, pos, start_state, dfa_transitions, accept_states): 从 text[pos:] 开始匹配一个 token返回(结束位置, 是否接受)。 如果匹配失败返回 (pos, False)如果接受返回最后一个接受状态的位置。 state start_state last_accept -1 i pos while i len(text): nxt dfa_transitions.get((state, text[i])) if nxt is None: break state nxt i 1 if state in accept_states: last_accept i if last_accept -1: return pos, False return last_accept, True这段代码的关键是last_accept每次进入接受状态就记录当前位置一旦后面的字符走不下去就回退到最近一次接受的位置。这样处理if和iff这类前后缀关系时才不会把iff错误地切成if加残留字符。实际集成时每个 token 类型对应一个 DFA按关键字、标识符、数字的顺序依次尝试匹配优先级靠顺序实现。做编译原理实验时我一般会先把run_dfa和lex_token写进测试脚本用十来条用例把转换结果钉死再去动状态表生成代码。NFA 转 DFA 这个环节的世界里状态表对了后面词法分析才谈得上正确状态表错了最小化和驱动写得再漂亮也是白搭。这也是我自己踩过最多坑之后养成的习惯——先花二十分钟跑验证用例胜过后面花两小时查一个莫名其妙的匹配错位。希望帮到你。本文还有配套的精品资源点击获取