简介面向编译原理课程初学者的实验型资源聚焦“正则表达式→NFA→DFA→最小化DFAMFA”这一完整转换流程既适合完成课程作业也可用于期末复习与自动机理论实践。资源内含3个Python程序分别实现正则式转NFA、NFA确定化为DFA、DFA最小化为MFA同时附带设计报告Word文档逐一说明程序模块设计、关键变量含义及算法思路帮助读者从原理到代码逐层打通。压缩包共10个文件除3个Python源码和1份Word报告外还包含3张结果示意图、2个Markdown说明文档以及1个许可证文件整体约498KB结构清晰、轻量易用。目前已有1050人学习下载对正在学习形式语言与自动机、需要动手实现编译前端状态转换模块的在校学生和自学者而言是一份能直接运行和对照参考的实用资料特别适合用于理解NFA子集构造法、状态转化表构建及DFA最小化步骤。1. 拿到一个正则转DFA的工具包先分清它是不是你想要的那条路线解压这种zip的场景多半在编译原理课设、词法分析器、手写正则引擎这三处。标题里的正则式、NFA、DFA、DFA最小化是一条经典转换链正则式先经Thompson构造变成NFANFA再经子集构造变成DFADFA最后做最小化旧教材也叫MFAminimal finite automaton得到状态最少的等价DFA。整套东西要解决的是把一行人能读的正则文本变成一台机器可以逐字符模拟的确定性状态机用于匹配、校验、协议字段识别。适合谁正在写编译原理大作业的学生想剥离re模块自己实现匹配逻辑的工程师以及需要在无正则库环境里做输入校验的嵌入式开发。后文会全程用构造1(0|1)*101相应的DFA这个经典练习当例子把每一步落到可运行的Python代码上。先说一个反直觉结论这套转换链上卡住大多数人的不是算法本身而是NFA的数据表示——用list当状态集合的key、move之后忘了取ε闭包、最小化之前不清不可达状态。表示选对了算法只是体力活。2. 正则式转NFA用Thompson构造把每个算子变成子图2.1 从AST到子图四条规则和两个展开宏Thompson构造的思路不是翻译整条正则而是把正则先拆成AST再按节点类型递归拼装子图。普通字符、连接、并、闭包各对应一套子图骨架。常见做法是直接把ε也算一个节点因为a?要展开成a|ε空分支在很多推导里绕不开。四条核心规则字符节点生成两个新状态和一条字符边连接节点把左子图的接受态通过ε边接到右子图的开始态并节点新增开始/接受两个状态分别用ε边连两个分支星号节点让子图可以整段跳过也可以循环。加号和问号我习惯在AST层做宏展开a变成a·a*a?变成(a|ε)而不是在NFA构造里再写两套转移模式。这样NFA构造器的分支只有六种出bug的面小一半。为什么不直接在NFA层特判加号和问号因为宏展开后的AST每次构建时状态编号都是新分配的不会出现两个子图共享内部状态的副作用。共享状态在子集构造时会让ε闭包多出很多不存在的路径排查起来非常玄学不建议碰。2.2 递归下降解析正则并生成NFA可直接跑的最小实现下面这段分成两部分前半是迷你正则解析器后半是Thompson构造器。解析器支持a-z、0-1、ε、括号、|、*、、?优先级按union最低、concat次之、repeat最高处理。# ---------------------------------------------------------------------- # 第1步迷你正则解析器递归下降 # 支持的语法expr union # union concat (| concat)* # concat repeat # repeat atom (* | | ?)* # atom 字符 | ( expr ) | ε # AST 用 tuple 表示 # (char, c) / (eps,) / (cat, l, r) # (alt, l, r) / (star, child) # (plus, child) / (opt, child) # ---------------------------------------------------------------------- class Parser: def __init__(self, pattern): self.pattern pattern self.pos 0 def peek(self): return self.pattern[self.pos] if self.pos len(self.pattern) else def parse(self): ast self.parse_union() if self.peek() ! : raise ValueError(funexpected token {self.peek()} at {self.pos}) return ast def parse_union(self): left self.parse_concat() while self.peek() |: self.pos 1 right self.parse_concat() left (alt, left, right) return left def parse_concat(self): nodes [] while self.peek() not in (, |, )): nodes.append(self.parse_repeat()) if not nodes: return (eps,) left nodes[0] for rhs in nodes[1:]: left (cat, left, rhs) return left def parse_repeat(self): node self.parse_atom() while self.peek() in (*, , ?): op self.peek() self.pos 1 if op *: node (star, node) elif op : node (plus, node) else: node (opt, node) return node def parse_atom(self): ch self.peek() if ch (: self.pos 1 node self.parse_union() if self.peek() ! ): raise ValueError(missing )) self.pos 1 return node if ch ε: self.pos 1 return (eps,) if ch and ch not in |*?(): self.pos 1 return (char, ch) raise ValueError(fbad token {ch} at {self.pos})这里有个容易翻车的细节连接concat的循环条件是遇到 |、) 或结尾才停而不是遇到运算符就停。因为正则里连接是隐式的ab中间没有任何字符必须靠parse_repeat逐段吃掉。如果把写进parse_concat的停止条件a* b会被拆成两个奇怪分支这类bug在作业里最常见的症状是匹配结果偶尔对、偶尔不对。# ---------------------------------------------------------------------- # 第2步Thompson 构造把 AST 变成 NFA # NFA 数据结构 # states : set[int] 状态编号从1开始自增 # trans : dict[(int, str)] - set[int] 普通字符转移 # eps : dict[int] - set[int] ε转移 # start : int # accept : set[int] # ---------------------------------------------------------------------- def build(ast, nfa, counter): def new_state(): counter[0] 1 s counter[0] nfa[states].add(s) return s def add_trans(i, ch, j): nfa[trans].setdefault((i, ch), set()).add(j) def add_eps(i, j): nfa[eps].setdefault(i, set()).add(j) kind ast[0] if kind eps: s, t new_state(), new_state() add_eps(s, t) return s, t if kind char: s, t new_state(), new_state() add_trans(s, ast[1], t) return s, t if kind cat: s1, t1 build(ast[1], nfa, counter) s2, t2 build(ast[2], nfa, counter) add_eps(t1, s2) return s1, t2 if kind alt: s, t new_state(), new_state() s1, t1 build(ast[1], nfa, counter) s2, t2 build(ast[2], nfa, counter) add_eps(s, s1) add_eps(s, s2) add_eps(t1, t) add_eps(t2, t) return s, t if kind star: s, t new_state(), new_state() s1, t1 build(ast[1], nfa, counter) add_eps(s, s1) add_eps(s, t) add_eps(t1, s1) add_eps(t1, t) return s, t if kind plus: return build((cat, ast[1], (star, ast[1])), nfa, counter) if kind opt: return build((alt, ast[1], (eps,)), nfa, counter) def regex_to_nfa(pattern): ast Parser(pattern).parse() nfa {states: set(), trans: {}, eps: {}, start: None, accept: set()} counter [0] start, accept build(ast, nfa, counter) nfa[start] start nfa[accept].add(accept) return nfa nfa regex_to_nfa(1(0|1)*101) print(sorted(nfa[states])) print(start , nfa[start], accept , sorted(nfa[accept])) print(trans , nfa[trans]) print(eps , nfa[eps])这里有几个参数值得说明。状态编号从1开始自增是为了打印时和教材里的状态图编号对齐从0开始也可以不改逻辑只影响可读性。ε转移和普通字符转移分开存是因为下一步子集构造时ε闭包和符号move是两个独立步骤合在一张表里会让闭包计算变得很绕。trans的key用(i, ch)二元组value用set因为NFA本来就是一状态对一符号可以走到多个状态。如果你要处理多字节字符或中文输入把Parser里的单字符处理改成先tokenize再解析即可NFA构造部分完全不用动。ε字符在代码里直接写中文ε文件存UTF-8没问题介意编码的可以把Parser里的ε替换成chr(0)逻辑等价的。2.3 先给NFA配个小模拟器避免带着坏NFA往下走转DFA之前强烈建议先验证NFA没建错。常见做法是写一个十几行的模拟器把NFA的ε闭包和符号move各做一遍逐字符吃输入串。def match_nfa(nfa, word): def eps_closure(states): seen set(states) stack list(states) while stack: s stack.pop() for nxt in nfa[eps].get(s, ()): if nxt not in seen: seen.add(nxt) stack.append(nxt) return frozenset(seen) current eps_closure((nfa[start],)) for ch in word: moved set() for s in current: for nxt in nfa[trans].get((s, ch), ()): moved.add(nxt) current eps_closure(moved) if not current: return False return bool(current nfa[accept]) print(match_nfa(nfa, 101)) # True print(match_nfa(nfa, 1101)) # True print(match_nfa(nfa, 1111101)) # True print(match_nfa(nfa, 01)) # False不以1开头 print(match_nfa(nfa, 1010)) # False结尾不是101match_nfa里的当前状态集用frozenset可哈希、可去重后面的子集构造会直接复用这段逻辑。这里的参数是word按字符拆单字符字母表没问题如果字母表是token级比如关键字IDENTIFIERword要预切成token列表再喂进来函数本体不用改。这层模拟器虽然慢但它给了你一个转换链的语义锚点后面DFA出问题全靠它对比。3. NFA转DFA用子集构造法求等价的DFA状态命名别用list3.1 ε闭包先行move后必须再接一次闭包NFA转DFA的所有教科书算法都长一个样DFA的每个状态是NFA状态的一个子集从NFA开始状态的ε闭包出发对字母表的每个符号求movemove结果再求ε闭包得到新的DFA状态重复直到没有新状态。为什么move后还要再取一次闭包因为move只吃到一个符号但落到目标状态后这些状态可能还有ε边能继续走不走完闭包DFA就漏了不需要消耗字符就能到达的状态。这是整个转换里最容易漏的一步漏了的表现是某些短串匹配成功、长串匹配失败而且长度越长城越明显。队列实现比递归实现稳。原因很实际子集构造的状态集合集合并集是2^n级别的递归写法一旦状态集多了容易反复计算同样的闭包还可能在超深递归里爆栈。队列加frozenset判重闭包最多对每个出现过的集合算一次。3.2 用队列实现的子集构造frozenset判重字符串命名# ---------------------------------------------------------------------- # NFA - DFA子集构造法 # DFA 数据结构 # states : set[str] 状态名形如 {1,3} # trans : dict[(str, str)] - str # start : str # accept : set[str] # ---------------------------------------------------------------------- from collections import deque def nfa_to_dfa(nfa, alphabet): def eps_closure(states): seen set(states) stack list(states) while stack: s stack.pop() for nxt in nfa[eps].get(s, ()): if nxt not in seen: seen.add(nxt) stack.append(nxt) return frozenset(seen) def state_name(state_set): # 用 {1,3} 这样的字符串命名 DFA 状态调试时直接对应回 NFA 编号 return { ,.join(str(s) for s in sorted(state_set)) } start_set eps_closure((nfa[start],)) dfa { states: set(), trans: {}, start: state_name(start_set), accept: set(), } queue deque([start_set]) seen_sets {start_set} while queue: cur_set queue.popleft() cur_name state_name(cur_set) dfa[states].add(cur_name) if cur_set nfa[accept]: dfa[accept].add(cur_name) for ch in sorted(alphabet): moved set() for s in cur_set: for nxt in nfa[trans].get((s, ch), ()): moved.add(nxt) if not moved: continue next_set eps_closure(moved) next_name state_name(next_set) dfa[trans][(cur_name, ch)] next_name if next_set not in seen_sets: seen_sets.add(next_set) queue.append(next_set) return dfa dfa nfa_to_dfa(nfa, {0, 1}) print(DFA states :, sorted(dfa[states])) print(DFA start :, dfa[start]) print(DFA accept :, sorted(dfa[accept])) for (s, ch), t in sorted(dfa[trans].items()): print(f {s} --{ch}-- {t})这段代码有三个必须说清的选择。第一seen_sets用frozenset做key而不是用state_name字符串。sorted后join生成的字符串和集合确实一一对应用字符串判重理论上也行但frozenset直接保留集合结构后续如果要回溯具体NFA状态省一次解析字符串的开销。第二对没有定义的转移我选择跳过而不是补死状态。这会让DFA缺转移匹配时返回False。对匹配器够用若要形式化证明DFA完备需要补一个对所有符号回到自身的死状态。第三alphabet必须显式传入因为DFA的转移表要为每个符号都求一次move如果从NFA的trans里猜alphabet会漏掉没有任何转移的字母手工做题时这就是漏行。输出里DFA状态名类似{1,2,4}这就是子集构造的子集本体。你可能注意到状态名变长了没关系第4章最小化会把它们重新缩回去。3.3 怎么求nfa等价的dfa手工填表与队列实现是同一套逻辑手工做题时老师讲的填表法本质上就是队列实现的纸上版本第一列写ε闭包(开始状态)对每个符号算move再取闭包得到的新状态集继续填行。区别只在队列换成纸上的待处理标记。所以程序跑出来的dfa[start]对应手工表第一行dfa[trans]的每一行对应手工表里已处理/未处理两栏。做题时有一个能救命的口诀先闭包、再move、再闭包。凡是卡住的地方按这个顺序重推一遍基本都能救回来。这也是怎么求nfa等价的dfa这个搜索词底下最常被问到的环节——很多人卡在move之后忘了最后一步闭包。这个转换最坏情况的状态数是2的NFA状态数次方这是理论上的指数爆炸。实际场景里爆炸很少发生因为ε边和并结构通常会共享大量子集真要爆了优先检查正则里是不是写了a(a|b)*这种本可以化简的冗余结构而不是急着改算法。4. DFA最小化与避坑MFA说法澄清等价划分的5个翻车现场4.1 MFA就是最小化后的DFA别把它当成新自动机先澄清标题里的MFA。形式语言教材里没有独立的MFA类自动机这个缩写通常指minimal finite automaton也就是最小化之后的DFA。它和DFA的接受能力完全一样只是状态数最少。所以DFA转MFADFA最小化翻译过来就是先把正则变成NFA再变成DFA然后合并DFA里的等价状态。最小化的价值不是省那几十个状态而是让DFA可读。子集构造给出的DFA状态名是{1,3,7,9}这种集合数量经常是NFA的几倍人根本看不过来最小化之后状态数接近正则的真实复杂度转移表才谈得上人工审查。我在做协议匹配器的时候最小化这一步是调试入口——拿最后的最小DFA去对需求比拿中间产物对靠谱得多。算法选型上教材的填表法等价划分复杂度O(n²)Hopcroft算法O(n log n)。状态数五百以内我无脑选等价划分代码短、不容易写错两三千状态再上Hopcroft。4.2 用等价划分实现最小化先删不可达再反复分裂def remove_unreachable(dfa, alphabet): reachable {dfa[start]} stack [dfa[start]] while stack: s stack.pop() for ch in alphabet: nxt dfa[trans].get((s, ch)) if nxt is not None and nxt not in reachable: reachable.add(nxt) stack.append(nxt) new_trans {} for (s, ch), t in dfa[trans].items(): if s in reachable and t in reachable: new_trans[(s, ch)] t return { states: {s for s in dfa[states] if s in reachable}, trans: new_trans, start: dfa[start], accept: {s for s in dfa[accept] if s in reachable}, } def minimize_dfa(dfa, alphabet): dfa remove_unreachable(dfa, alphabet) accept frozenset(dfa[accept]) non_accept frozenset(dfa[states] - accept) partition [g for g in (accept, non_accept) if g] changed True while changed: changed False new_partition [] for group in partition: subgroups {} for s in group: sig [] for ch in sorted(alphabet): t dfa[trans].get((s, ch)) group_idx next( (i for i, g in enumerate(partition) if t in g), None ) sig.append(group_idx) key tuple(sig) subgroups.setdefault(key, set()).add(s) if len(subgroups) 1: changed True new_partition.extend(subgroups.values()) partition new_partition rep {} for group in partition: r min(group) # 取组内状态名最小的一个当代表 for s in group: rep[s] r min_dfa { states: set(), trans: {}, start: rep[dfa[start]], accept: set(), } for group in partition: r min(group) min_dfa[states].add(r) if r in accept: min_dfa[accept].add(r) for ch in sorted(alphabet): t dfa[trans].get((r, ch)) if t is not None: min_dfa[trans][(r, ch)] rep[t] return min_dfa min_dfa minimize_dfa(dfa, {0, 1}) print(min states:, sorted(min_dfa[states])) print(min accept:, sorted(min_dfa[accept])) for (s, ch), t in sorted(min_dfa[trans].items()): print(f {s} --{ch}-- {t})三个必须调对的参数。第一partition初始化的空组过滤如果DFA所有状态都是接受态或都不是接受态accept和non_accept里有一个是空集不过滤会在while循环里产生空组分裂逻辑直接卡死。第二未定义转移的group_idx回退None等价划分里缺失的转移必须当进入另一个组处理否则两个转移表一个缺0边、一个缺1边的状态会被错误地当成等价。第三重建转移时用rep[t]而不是t组内状态已经合并t要映射到代表状态漏了这步会产生指向旧状态名的悬空边也就是俗称的幽灵状态。这里有个取舍值得说我在remove_unreachable里把死状态删掉了。严谨的教材流程是先补显式死状态、再删不可达、再划分。但匹配器场景下死状态本身不可达而且永不接受删掉它对划分结果没有影响代码还少一套。如果要跑形式化验证工具再按教材顺序来。4.3 五个高频踩坑现象、原因、解决翻车点一最小化后状态数没变少甚至变多。 现象min_dfa和dfa的状态数几乎一样转移表看不出规律。 原因大概率没删不可达状态不可达状态参与划分后把等价组切碎了。 解决minimize第一步强制remove_unreachable并在日志里打印删除了几个状态如果删完还是没变化检查正则本身是不是已经很简比如a|ab这类正则确实有多个不等价状态。翻车点二move之后忘了再取ε闭包长串匹配全错。 现象短串如101能过稍微长一点的110111101开始挂而且错误没有规律。 原因子集构造里move之后直接用moved当新DFA状态没对moved做eps_closureε边产生的路径全丢。 解决把3.2里的next_set eps_closure(moved)当模板永远先闭包、再move、再闭包。这条写在代码注释里都不嫌多。翻车点三带?和的正则直接报语法错误或表现像普通字符。 现象a?匹配出来的结果是a?这个字符串本身或者ab?抛出bad token。 原因parse_atom里把?、当普通字符吃了或者parse_repeat的循环顺序写反。 解决先打印AST验证Parser(ab?).parse()应该输出(cat, (plus,(char,a)), (opt,(char,b)))。AST不对就别往下走解析器是这条链的地基。翻车点四最小化后接受语言全变了原来能匹配的串被拒。 现象min_dfa跑match原本接受的101被拒。 原因重建转移时用了原状态t而不是代表状态rep[t]新DFA的接受态集合里混入了组内非接受状态或者初始划分时accept和non_accept空组没过滤。 解决在minimize_dfa入口加一个和原dfa的随机串对比测试第5章有现成代码任何一步改完都重跑。我当时第一次写等价划分就是死在rep映射上加了这个测试之后两分钟定位。翻车点五小正则秒出大正则直接卡死。 现象换个几十个运算符的正则nfa_to_dfa跑不完。 原因子集构造最坏指数爆炸NFA状态多、ε边多时DFA状态数可以到2^n。 解决先确认不是死循环——在队列循环里加个状态数上限的断言超过就报错真爆了优先检查正则里是不是有a(a|b)*这种能合并的写法或者把正则先做AST层面的简化。工程上不要指望所有正则都能转出小DFA词法分析器的token正则通常是几十个小正则拆开匹配而不是一个大而全的正则。5. 用re模块交叉验证整条转换链再把这套DFA接进词法匹配5.1 随机串对齐四层语义正则、NFA、DFA、最小DFA整套转换链做完最重要的一件事是用随机串把四层语义对齐。re模块是现成的参考实现不用自己造轮子。生成一万条随机01串分别用re.fullmatch、match_nfa、match_dfa去判定任何不一致都说明中间某一步改了语言。def match_dfa(dfa, word): s dfa[start] for ch in word: nxt dfa[trans].get((s, ch)) if nxt is None: return False s nxt return s in dfa[accept] import random, re pattern 1(0|1)*101 for _ in range(10000): length random.randint(0, 12) s .join(random.choice(01) for _ in range(length)) r1 bool(re.fullmatch(pattern, s)) r2 match_nfa(nfa, s) r3 match_dfa(min_dfa, s) assert r1 r2 r3, (s, r1, r2, r3) print(10000 random tests passed)这段测试能当后悔药用。改完AST、子集构造、最小化任何一个环节跑一遍随机对比语义有没有变立刻现形。要注意re.fullmatch和match_dfa的语义必须一致——fullmatch要求整串匹配所以match_dfa也要吃完整条输入再判断接受不能中途一遇到缺失转移就False。缺失转移返回False是安全的因为DFA一旦走进死路就是永久拒绝。5.2 把最小DFA接进词法匹配的两个习惯玩具匹配器用dict转移表没有问题但真要进词法分析器我一般会做两件事把转移表拍平成二维数组维度是状态数乘字母表大小再把死状态显式加回去让每个格子都有值。二维数组的好处是读入一个字符只需一次数组索引没有字典哈希开销死状态显式化则让非法字符的报错路径和正常路径共用同一套转移逻辑不用在循环里写if。另一个习惯是把多个正则合并成一个大NFA再转换。词法分析器要同时识别关键字、标识符、数字、空白别为每个token单独跑一个DFA——把所有token正则放一起每个正则有自己的起始状态和接受标记合并后子集构造出来的DFA天然共享公共前缀状态数比分开跑小得多。最后说个我自己的教训。最早做DFA最小化时我自信满满跳过不可达清理结果最小化后的转移表出现指向幽灵状态的边排查了一整天才发现是没删不可达状态代表状态却来自等价组这个组合问题。后来我立了个规矩任何自动机转换代码第一行写随机对比测试第二行才写算法。这个规矩让我少熬了好几个夜希望帮到你。本文还有配套的精品资源点击获取
