Python实现正则表达式转NFA、DFA确定化与最小化完整指南

简介这是一份面向编译原理课程设计或形式语言理论学习者的Python完整实现资源围绕正则式转NFA、NFA确定化及DFA最小化三个核心流程展开覆盖从状态定义、转移表构建到幂集构造与等价类合并的完整编码与报告说明适合高校学生对照课程要求完成作业或深入理解自动机原理。资源包共9个文件以3个Python源码文件为核心分别对应正则式转NFA、NFA确定化、DFA最小化的分模块实现另含3张PNG图片用于示意图或运行结果展示2个Markdown文档提供实现思路与课程设计说明并附带许可证文件压缩包大小仅243KB整体结构清晰、便于查阅。已有355人浏览学习适合正在做编译原理作业、需要可运行示例或参考资料的学生使用。通过该资源可掌握NFA与DFA的构建细节、最小化算法的实际编码思路并能直接复用代码进行扩展调试对提升算法设计能力与编译原理实践水平有直接帮助。1. 正则式转NFA、NFA确定化、DFA最小化完整链路为什么值得手写一遍正则表达式本身没有执行语义。它描述的是语言而不是匹配算法只有 NFA、DFA 这类自动机才真正知道怎么逐字符消耗输入并判定受理状态。把a(b|c)*这样的模式拿去匹配字符串时编译原理里那条「正则式转NFA → NFA确定化为DFA → DFA最小化」的链路正是很多生产级正则引擎在编译期真正走的路线。这篇文章用纯 Python 完整实现整条链路先构建带 ε 边的 NFA再用子集构造法做确定化最后用划分细化合并冗余状态。读完你可以拿到三个可验证的产物NFA 状态图、DFA 转移表、最小化后的 DFA。熟悉 Python 但没手写过编译器的读者也可以把这套实现当作词法分析器的最小样例来读。2. 正则式转NFAState类、调车场算法与Thompson构造的落地组合正则式转 NFA 的常见做法有两条对语法树做递归下降或者先把中缀正则转成后缀表达式再统一拼装。我一般用后者。输入a(b|c)*调车场算法会先补出显式连接符·得到后缀形式a b c | · *。后缀的好处是每个运算符都对应一个明确的时机——从栈里弹一个或两个片段再按 Thompson 构造的模板拼出新的 NFA 片段全程不需要维护递归调用栈。2.1 先把NFA数据结构定义清楚一个状态一张转移表NFA 本质是一张有向图状态只做两件事记唯一编号记出边。出边要么带一个普通字符要么带None表示 ε 边。使用邻接表而不是稠密二维表是因为 ε 边和字符边在实际构建中都比较稀疏遍历时只访问存在的边更高效。class NFAState: NFA状态id用于调试输出transitions保存全部出边。 def __init__(self, sid): self.id sid self.transitions [] def add_edge(self, symbol, target): # symbol为None时表示ε边否则是普通字符边 self.transitions.append((symbol, target)) class NFAFragment: 自动机片段对外只暴露start与accept两个状态。 def __init__(self, start, accept): self.start start self.accept accept class StateFactory: 全局状态编号生成器保证打印自动机图时状态不重名。 def __init__(self): self.counter 0 def new_state(self): s NFAState(self.counter) self.counter 1 return sNFAFragment是 Thompson 构造的核心抽象。拼接运算时只需要知道片段的入口和出口内部结构全部封装起来这样连接、选择、闭包都可以用统一的栈操作完成。NFAState没有自定义__eq__所以默认按对象身份哈希放进set或作为字典键都不会出错。2.2 中缀转后缀调车场算法让“|”和连接不再纠缠手写递归下降解析器当然可行但优先级关系会散落在多个parse_x()函数里调试时反而难定位。调车场算法把优先级集中在一张表里碰到运算符就按优先级弹栈对后续 Thompson 拼接更直接。def insert_concat_ops(pattern): 在相邻因子之间插入显式连接符·让连接变成可见的二元运算。 result [] for i, ch in enumerate(pattern): result.append(ch) if i 1 len(pattern): nxt pattern[i 1] # 当前字符能结束一个因子且后一个字符能开始一个因子时补连接符 if ch not in (| and nxt not in |*?): result.append(·) return .join(result) def shunting_yard(pattern): 正则中缀转后缀返回token列表。 pattern insert_concat_ops(pattern) prec {|: 1, ·: 2} out, ops [], [] for ch in pattern: if ch in (|, ·): while ops and ops[-1] ! ( and prec[ops[-1]] prec[ch]: out.append(ops.pop()) ops.append(ch) elif ch (: ops.append(ch) elif ch ): while ops and ops[-1] ! (: out.append(ops.pop()) ops.pop() # 弹出左括号本身 elif ch in (*, , ?): out.append(ch) # 一元后缀运算符不参与中缀优先级比较 else: out.append(ch) # 普通字符直接输出 while ops: out.append(ops.pop()) return out代码里的优先级只用在中缀二元运算符之间token类型优先级中缀选择·中缀连接2*?一元后缀不参与比较直接追加insert_concat_ops的边界条件要注意(a|b)内部不能插入·ab之间要插a*不能插。上面ch not in (|和nxt not in |*?)两个条件同时满足才插覆盖了所有常见组合。2.3 Thompson构造的四种运算符怎么拼NFA片段拿到后缀表达式后构建过程变成纯粹的栈运算。遇到字符就新建两个状态和一条字符边遇到运算符就弹出对应数量的片段按固定的 ε 边模板拼装。def thompson_build(postfix, factory): 按后缀表达式逐个运算栈里存的始终是NFAFragment。 stack [] for ch in postfix: if ch ·: right, left stack.pop(), stack.pop() # 连接left出口接right入口只需要一条ε边 left.accept.add_edge(None, right.start) stack.append(NFAFragment(left.start, right.accept)) elif ch |: right, left stack.pop(), stack.pop() # 选择新建公共入口和公共出口两条ε边分别引入 s factory.new_state() a factory.new_state() s.add_edge(None, left.start) s.add_edge(None, right.start) left.accept.add_edge(None, a) right.accept.add_edge(None, a) stack.append(NFAFragment(s, a)) elif ch *: frag stack.pop() # 闭包允许跳过frag也允许从内部回到入口重复执行 s factory.new_state() a factory.new_state() s.add_edge(None, frag.start) s.add_edge(None, a) frag.accept.add_edge(None, frag.start) frag.accept.add_edge(None, a) stack.append(NFAFragment(s, a)) elif ch : frag stack.pop() # e等价于至少出现一次不能跳过frag但可以循环 s factory.new_state() a factory.new_state() s.add_edge(None, frag.start) frag.accept.add_edge(None, frag.start) frag.accept.add_edge(None, a) stack.append(NFAFragment(s, a)) elif ch ?: frag stack.pop() # e?等价于出现0次或1次提供一条直接到公共出口的旁路 s factory.new_state() a factory.new_state() s.add_edge(None, frag.start) s.add_edge(None, a) frag.accept.add_edge(None, a) stack.append(NFAFragment(s, a)) else: # 普通字符新建起止状态连一条字符边 s factory.new_state() a factory.new_state() s.add_edge(ch, a) stack.append(NFAFragment(s, a)) return stack[0]这段代码里right, left stack.pop(), stack.pop()的顺序不能反后弹出的是左操作数。对于|和·而言顺序影响很大尤其是连接运算一但左右颠倒整个自动机读到字符的顺序就反了。*、、?都是单目操作只弹一个片段内部修改的是frag.accept这个状态的出边所以能实现“回到起点”或“跳到出口”的回路。2.4 为什么用后缀表达式而不是递归下降解析递归下降更接近人的阅读直觉但需要为每个优先级层次写一个函数还要处理“连接”这种隐式运算。后缀表达式把两层问题分离调车场算法负责解析Thompson 构造只关心拼接。另一个实际原因是后缀求值天然是左到右的线性扫描方便在函数里加入状态计数或断点日志排错时可以一行一行看栈里发生了什么。这里有个容易踩的坑同一个NFAFragment对象不能在同一时刻被复用两次。拼接运算会修改片段的accept出边如果拿同一个片段去构建两个不同的父运算后续调试会出现共享状态。常见写法是保证每个语法单位都新建独立片段。(a*)*这类嵌套不会出问题因为内层*已经返回了新片段外层*是在新片段上再包一层。3. NFA确定化子集构造法实现DFA转移表别漏算ε-闭包NFA 确定化的术语叫“子集构造法”核心思想是NFA 在某个时刻可能同时处于多个状态DFA 的一个状态就代表一组 NFA 状态的集合。读入一个字符后所有可能到达的状态合并成一个新集合这个集合就是下一个 DFA 状态。关键点在于任何一次跳转后都要补算 ε-闭包因为 ε 边不消耗字符但能改变当前活跃状态集合。3.1 ε-闭包的计算用栈实现避免递归深度翻车ε-闭包的定义是从一组状态出发只沿着 ε 边就能到达的所有状态集合。实现时不建议写递归因为自动机的 ε 环路很常见比如a*的内部就有回边递归容易栈溢出或无限循环。用显式栈做 BFS/DFS 更稳妥。def epsilon_closure(nfa_states): 求一组NFA状态的ε-闭包沿ε边能到达的所有状态都算进去。 result set(nfa_states) stack list(nfa_states) while stack: state stack.pop() for symbol, target in state.transitions: if symbol is None and target not in result: result.add(target) stack.append(target) return result def move(nfa_states, symbol): 返回从状态集合中经过一条symbol边到达的状态集合不展开ε闭包。 result set() for state in nfa_states: for edge_symbol, target in state.transitions: if edge_symbol symbol: result.add(target) return result参数symbol必须是具体字符而None表示 ε所以move里用比较不会误伤 ε 边。move不负责展开 ε 边调用方必须手动补epsilon_closure。这个分工能让两个函数的职责单一也便于单独测试。3.2 转移表构建frozenset当DFA状态键天然去重确定化的核心就是把“NFA状态集合”映射为“DFA状态编号”。Python 里最干净的做法是用frozenset作为字典键因为集合是无序的frozenset又是可哈希的相同的状态集合只会对应同一个 DFA 状态。def subset_construction(nfa, alphabet): 子集构造法把NFA转换为DFA转移表。 返回 dfa_states list[frozenset[NFAState]] dfa_transitions list[dict[str, int]] dfa_start int dfa_accept set[int] start_set frozenset(epsilon_closure([nfa.start])) dfa_states [start_set] dfa_transitions [{}] state_index {start_set: 0} unprocessed [start_set] dfa_accept set() while unprocessed: current unprocessed.pop() current_id state_index[current] # 当前集合里只要包含原NFA的接受状态这个DFA状态就是接受态 if nfa.accept in current: dfa_accept.add(current_id) for symbol in alphabet: nxt frozenset(epsilon_closure(move(current, symbol))) if not nxt: continue if nxt not in state_index: state_index[nxt] len(dfa_states) dfa_states.append(nxt) dfa_transitions.append({}) unprocessed.append(nxt) dfa_transitions[current_id][symbol] state_index[nxt] return dfa_states, dfa_transitions, 0, dfa_acceptstate_index就是从 NFA 状态集合到 DFA 编号的映射。出现新集合时分配一个新编号并加入工作列表已存在的集合直接复用编号。nfa.accept in current这个判断用的是对象身份比较前提是NFAState没有重写__eq__。如果自定义了相等比较这里要改成any(st is nfa.accept for st in current)。alphabet必须由调用方显式传入而且要保证顺序稳定。我一般从正则表达式里提取所有非运算符字符再排个序这样多次运行生成的转移表列顺序一致。3.3 缺失边与死状态确定化之后需要明确的约定自动机理论里 DFA 要求转移函数完全定义但工程实现通常偷懒没有可到达状态就不写这条边。两种做法各有取舍本文代码采用“省略转移”策略这样转移表更小最小化时也把缺失边统一看作指向同一个虚拟死状态。策略实现方式对最小化的影响省略转移字典里不存在该符号的键最小化时缺失边统一编码为-1共享同一个虚拟目标显式死状态所有缺失边指向一个非接受sink状态表的规模变大但最小化后 sink 可能被合并语义更显式省略转移对匹配引擎没有影响模拟 DFA 时遇到不存在的键直接返回False即可。但要注意如果你要输出“完整”的 DFA 状态图给别人看最好还是补一个死状态否则图上每个非接受态都缺了若干出边阅读者容易误解为缺陷。4. DFA最小化Moore划分细化算法及等价状态合并DFA 最小化的目标是把行为完全一致的状态合并成一个。两个状态等价必须满足两个条件接受属性相同并且对任意输入符号它们转移到的目标状态也等价。这件事用“划分细化”做最直观先假定所有状态归为一个大分区再逐轮按签名拆分直到没有状态被拆开。4.1 等价状态的定义与初始划分接受态与非接受态必须分开初始划分必须至少区分接受态和非接受态因为这两个集合的行为在“最终是否受理”上已经不同不可能等价。以(a|b)*abb为例确定化后得到 4 个 DFA 状态编号为 0、1、2、3其中 3 是接受态。初始划分是{0,1,2}与{3}。后续每一轮迭代都要检查同一分区内部每个状态在所有符号下的目标分区。目标分区不同状态就要拆到新分区。整个过程如下迭代分区结果说明0{0,1,2}{3}接受态与非接受态分离1{0,1}{2}{3}状态2在符号b下进入{3}与0、1不同2{0,1}{2}{3}继续细分无变化迭代终止迭代终止后0 和 1 被合并成同一状态整个自动机从 4 个状态缩到 3 个。4.2 划分迭代用转移签名判定状态是否继续拆散实现划分细化时我用“签名”来给状态分组对某个状态计算它分别在每个字符下到达的目标分区编号组成一个元组。同一分区里签名相同的状态归入同一新分区签名不同的必然拆开。def minimize_dfa(dfa_transitions, alphabet, dfa_accept): Moore划分细化返回最终分区列表和state-分区映射。 n len(dfa_transitions) accept_set set(dfa_accept) # 初始分区非接受态在前接受态在后 partitions [] non_accept [s for s in range(n) if s not in accept_set] accept_list [s for s in range(n) if s in accept_set] if non_accept: partitions.append(frozenset(non_accept)) if accept_list: partitions.append(frozenset(accept_list)) state_to_part {} for idx, part in enumerate(partitions): for s in part: state_to_part[s] idx while True: new_partitions [] new_state_to_part {} for part in partitions: groups {} for state in sorted(part): # 排序保证分区编号稳定 sig tuple( state_to_part.get(dfa_transitions[state].get(sym), -1) for sym in alphabet ) groups.setdefault(sig, []).append(state) for group in groups.values(): g frozenset(group) new_partitions.append(g) for s in g: new_state_to_part[s] len(new_partitions) - 1 # 分区数量不再增加说明没有任何状态被继续拆散 if len(new_partitions) len(partitions): return partitions, state_to_part partitions new_partitions state_to_part new_state_to_part签名里的-1对应缺失边。dfa_transitions[state].get(sym)返回None时state_to_part.get(None, -1)得到-1所有缺失边因此被视为转向同一个虚拟死状态。这个约定让省略转移的 DFA 也能正确参与最小化。终止条件用“分区数量不变”已经足够每一轮只会拆分区、不会合并分区因此只要数量不变就说明没有任何分区发生拆分结果收敛。如果想控制迭代次数可以在循环里加计数器最多跑n轮。4.3 从划分结果重建最小DFA转移表得到分区后再重建最小 DFA 的转移表。每个分区对应一个新状态转移表的目标指向目标状态所在的分区编号。def rebuild_minimized_dfa(dfa_transitions, alphabet, start_index, dfa_accept): 用最小化分区结果重建DFA转移表。 partitions, state_to_part minimize_dfa(dfa_transitions, alphabet, dfa_accept) min_table [] min_accept set() for part in partitions: rep min(part) # 取分区内最小编号做代表输出稳定 table {} for symbol in alphabet: target dfa_transitions[rep].get(symbol) if target is not None: table[symbol] state_to_part[target] min_table.append(table) if rep in dfa_accept: min_accept.add(len(min_table) - 1) return min_table, min_accept, state_to_part[start_index]min(part)只是为了输出稳定换成任意一个分区内状态都可以因为同一分区内的状态已经被判定为等价它们对每个符号的目标分区完全一致。起始状态的处理直接映射state_to_part[start_index]新起始状态永远是包含起始状态的那个分区。4.4 状态数大到什么程度才考虑Hopcroft优化本文的划分细化实现复杂度大约是O(n^2 * |Σ|)对几百个状态的 DFA 完全够用。课程设计和大部分编译原理作业里NFA 状态数通常只有几十个确定化后的 DFA 也很少超过几百直接跑这个版本最快。只有当 DFA 状态数上万、重复迭代轮数过高时才值得换成 Hopcroft 算法。Hopcroft 的精髓是维护一个待处理分区队列每轮只处理涉及某个符号的分区而不是扫描全部分区能把平均复杂度降到接近O(n log n)。但它的实现容易出边界问题我一般先用 Moore 版本验证正确性再按需替换。5. 用测试代码验证最小DFA与原始正则式的匹配一致性整条链路做完后验证逻辑其实很简单同一段字符串分别喂给 NFA、确定化后的 DFA、最小化后的 DFA三个结果必须完全一致。这个验证同时检验了确定化和最小化两个阶段有没有改变自动机接受的语言。5.1 三个阶段的匹配结果对照先写 NFA 和 DFA 的模拟函数再写一个汇总测试入口。NFA 模拟每次读入字符后都要做一次 ε-闭包DFA 模拟则是纯粹的查表。def run_nfa(nfa, text): 在NFA上跑一段字符串返回是否接受。 states epsilon_closure([nfa.start]) for ch in text: states epsilon_closure(move(states, ch)) if not states: return False return nfa.accept in states def run_dfa(trans_table, start, accept_set, text): 在DFA转移表上跑字符串缺失边直接返回False。 state start for ch in text: if ch not in trans_table[state]: return False state trans_table[state][ch] return state in accept_set def test_chain(pattern, alphabet, samples): factory StateFactory() postfix shunting_yard(pattern) nfa thompson_build(postfix, factory) dfa_states, dfa_table, dfa_start, dfa_accept subset_construction(nfa, alphabet) min_table, min_accept, min_start rebuild_minimized_dfa( dfa_table, alphabet, dfa_start, dfa_accept ) print(fpattern{pattern} postfix{ .join(postfix)}) print(fNFA{factory.counter} states, DFA{len(dfa_states)} states, MIN{len(min_table)} states) for text in samples: r1 run_nfa(nfa, text) r2 run_dfa(dfa_table, dfa_start, dfa_accept, text) r3 run_dfa(min_table, min_start, min_accept, text) ok (r1 r2 r3) print(f {text:8} NFA{r1} DFA{r2} MIN{r3} 一致{ok})用两个典型模式做回归一组是含闭包和选择的a(b|c)*一组是经典练手题(a|b)*abb模式测试串NFADFAMIN一致a(bc)*acbbcTrueTrueTruea(bc)*aTrueTrueTruea(bc)*abxFalseFalseFalse(ab)*abbabbTrueTrueTrue(ab)*abbaabbTrueTrueTrue(ab)*abbababFalseFalseFalse第二个模式的状态数变化很直观NFA 8 个状态确定化为 4 个 DFA 状态最小化后剩 3 个。如果这三处模拟结果出现不一致优先检查确定化阶段的 ε-闭包是否漏算其次检查最小化的初始分区是否误把接受态和非接受态放在了一起。5.2 典型踩坑把转移表打印出来对状态名排错时不要只在布尔结果里打转直接把三张转移表结构化打印出来。给每个 NFA 状态的出边按编号排序输出的行会更容易比对。我常用的一行调试是print(nfa.accept.id, [(st.id, [(s, t.id) for s, t in st.transitions]) for st in all_states])。习惯上我会给状态编号留出间隔方便中间插入新状态但这段实现里StateFactory自增计数器已经保证唯一性不需要预留。5.3 最小结果如何落盘复用最小 DFA 已经是一张纯粹的表状态编号、字符到目标编号的字典、接受状态集合。它可以直接序列化为 JSON在编译型项目的构建阶段生成一次运行时加载避免每次启动都重复做正则式转 NFA、确定化、最小化三件事。比如把min_table和接受集合写成{trans: [[{a: 1}], [{b: 2}]], accept: [2], start: 0}加载时逐行还原成原来的字典结构即可。这个缓存策略对词汇表数量很大的词法分析器收益明显一次最小化省掉的是整个编译前端的重复工作。本文还有配套的精品资源点击获取