简介：一个面向编译原理课程设计的完整Python实现项目，围绕正则表达式转NFA、NFA确定化为DFA、DFA最小化三个核心步骤展开。压缩包共9个文件，大小约243KB，包含3个Python源码文件、3张原理示意图、2份Markdown说明文档和1份LICENSE许可文件；源码分别对应NFA构建、子集构造法确定化及Hopcroft风格最小化，图片和文档用于辅助理解关键概念。该项目适合计算机专业学生巩固编译原理和形式语言知识，也可作为课程作业或期末设计的完整参考方案。预览显示目录结构清晰，附有编译原理第一次作业说明，能帮助读者快速理解类设计、状态转移、变量选择与实现思路。目前已有356人学习，对于希望掌握正则引擎底层构造逻辑的开发者而言，这份资源能从代码和理论两个层面提供完整的闭环体验，兼具学习与复用价值。
1. 为什么要自己写一个正则转自动机：题目值在哪
如果你只把 Python 的re模块当黑匣子用，永远理解不了正则背后的匹配逻辑。正则式转 NFA、NFA 确定化、DFA 最小化这一套流程，正是编译原理里词法分析器的骨架——从表达式到自动机，再从自动机到最小等价机。很多从业者遇到自定义 DSL、协议报文解析、敏感信息扫描时，会发现内置正则引擎根本不给你控制内部结构的机会：不能拆状态、不能打日志、不能按需合并等价分支。自己用纯 Python 把这条链路跑通之后，你能看懂任何正则引擎的报错，能自定义 NFA 状态的动作回调，还能把最终 DFA 无损导出成 JSON 给别的语言复用。
这篇文章写给两类人：一类是刚啃完编译原理课程、想用 Python 把理论落到代码却不知道从哪起步的学生；另一类是工作中要手写词法分析器或规则引擎的工程师。完整的可运行代码、每一步的参数含义、以及我踩过的坑都会放在后面，照着敲就能得到一个能匹配、能打印、能最小化的完整自动机工具链。
2. 正则式转 NFA：AST 解析与 Thompson 构造法
2.1 先设计一个能表达优先级的 AST 节点
很多人一上来就直接把正则字符串往 NFA 上怼，结果处理括号和优先级时一团糟。我的做法是先做一层语法解析，把正则字符串变成 AST（抽象语法树），再对着 AST 做 Thompson 构造。这样等于把一个“字符处理”问题降维成“树遍历”问题，所有优先级关系都在建树时解决了。
AST 节点我用了四类：字符节点Char、连接节点Concat、并选择节点Union、闭包节点Star。连接是隐式的——ab就是两个Char的Concat。这里不单独建 Epsilon（空串）节点，因为空串在连接运算里就是个无操作，后面用 None 表示即可。
from dataclasses import dataclass from typing import Optional, Union as TypingUnion @dataclass class Char: """单个字符节点""" value: str @dataclass class Concat: """连接节点：左右两个子表达式按顺序匹配""" left: TypingUnion[Char, 'Concat', 'Union', 'Star'] right: TypingUnion[Char, 'Concat', 'Union', 'Star'] @dataclass class Union: """并选择节点：左右两个子表达式二选一""" left: TypingUnion[Char, 'Concat', 'Union', 'Star'] right: TypingUnion[Char, 'Concat', 'Union', 'Star'] @dataclass class Star: """闭包节点：子表达式重复零次或多次""" child: TypingUnion[Char, 'Concat', 'Union', 'Star']建的这四类节点覆盖了正则的完整表达能力：单个字符、顺序连接、分支选择、重复。后面的 Thompson 构造法就是针对这四种节点写递归函数。解析器我用的是递归下降：先解析 Union，再往下一层解析 Concat，最底层解析 Star 和 Char。这里有一个很多人翻车的细节——*的优先级最高，必须最先被处理，否则ab*会被解析成(ab)*。
class RegexParser: def __init__(self, pattern: str): self.pattern = pattern self.pos = 0 def parse(self): node = self.parse_union() if self.pos != len(self.pattern): raise ValueError(f"Unexpected char at pos {self.pos}: {self.pattern[self.pos]}") return node def parse_union(self): """处理 | 运算符，优先级最低""" left = self.parse_concat() while self.pos < len(self.pattern) and self.pattern[self.pos] == '|': self.pos += 1 right = self.parse_concat() left = Union(left, right) return left def parse_concat(self): """处理隐式连接，遇到 ) 或 | 或结尾就停""" items = [] while self.pos < len(self.pattern): ch = self.pattern[self.pos] if ch == '|' or ch == ')': break items.append(self.parse_star()) if not items: # 允许空表达式，表示空串 return None node = items[0] for item in items[1:]: node = Concat(node, item) return node def parse_star(self): """处理 * 闭包和单个字符""" ch = self.pattern[self.pos] if ch == '(': self.pos += 1 node = self.parse_union() if self.pos >= len(self.pattern) or self.pattern[self.pos] != ')': raise ValueError("Missing closing parenthesis") self.pos += 1 elif ch == '*' or ch == '|' or ch == ')': raise ValueError(f"Unexpected char: {ch}") else: node = Char(ch) self.pos += 1 while self.pos < len(self.pattern) and self.pattern[self.pos] == '*': node = Star(node) self.pos += 1 return node这段解析器里最关键的是parse_concat：它循环收集子节点然后左折叠成Concat树，遇到|或)就停下来交给上层处理。注意parse_star里处理括号的方式——先递归调用parse_union，然后再检查闭包，这样(ab)*才能正确套上Star。我在解析器里留了两个明显报错：缺右括号和裸*（如*a），这两类非法表达式在生产场景里必须第一时间暴露，而不是等 NFA 构造时才崩。
参数方面，RegexParser只维护两个字段：pattern原字符串和pos游标。递归下降不需要额外的栈结构，函数调用栈本身就承担了括号嵌套的层级关系。如果遇到超长的嵌套括号（比如一万层），Python 的递归深度限制会拦下来，这个我在后面避坑部分会讲怎么处理。
2.2 用 Thompson 构造法把 AST 拼成 NFA
拿到 AST 后，我按 Thompson 构造法递归生成 NFA。核心思路是：每个子表达式都对应一个 NFA 片段，片段有一条初态边和一条终态边，拼接时只改边不新建重复逻辑。字符节点生成两个状态加一条转移边；Concat把左边终态和右边初态合并；Union新建初态终态，用 ε 边连接两边；Star新建状态，用 ε 边绕回初态。
class NFAState: """NFA 状态：transitions 是 dict，key 为字符或 None(ε)""" def __init__(self, sid: int): self.id = sid self.transitions = {} # 字符 -> set[NFAState] def add_edge(self, char: Optional[str], target: 'NFAState'): self.transitions.setdefault(char, set()).add(target) class NFA: def __init__(self, start: NFAState, accept: NFAState): self.start = start self.accept = accept把 AST 节点传给build_nfa返回(start, accept)两个状态引用。Thompson 构造法的精妙之处在于每个子结构都留有唯一的“接口状态”，拼接时只要操作接口状态就行。比如Char('a')就生成两个状态，中间连一条'a'的边；Concat结构则是把左右两个子片段串起来——左片段的终态状态对象不变，只是往右片段的初态补了一条 ε 边。
class NFAConstructor: def __init__(self): self.state_counter = 0 def new_state(self) -> NFAState: self.state_counter += 1 return NFAState(self.state_counter) def build(self, node) -> tuple: """返回 (start_state, accept_state)""" if isinstance(node, Char): s = self.new_state() a = self.new_state() s.add_edge(node.value, a) return s, a if isinstance(node, Concat): left_s, left_a = self.build(node.left) right_s, right_a = self.build(node.right) left_a.add_edge(None, right_s) # ε 连接 return left_s, right_a if isinstance(node, Union): s = self.new_state() a = self.new_state() left_s, left_a = self.build(node.left) right_s, right_a = self.build(node.right) s.add_edge(None, left_s) s.add_edge(None, right_s) left_a.add_edge(None, a) right_a.add_edge(None, a) return s, a if isinstance(node, Star): s = self.new_state() a = self.new_state() child_s, child_a = self.build(node.child) s.add_edge(None, child_s) s.add_edge(None, a) child_a.add_edge(None, child_s) # 回环，支持重复 child_a.add_edge(None, a) return s, a if node is None: # 空正则直接用一个 ε 边连接 s = self.new_state() a = self.new_state() s.add_edge(None, a) return s, a raise TypeError(f"Unknown node type: {type(node)}")这里有个容易被忽略的边界：空表达式node is None。比如正则()或者解析失败时的占位，我直接生成一个 ε 边连接两个状态，这个片段在后续确定化时会膨胀成一个 ε-闭包的大集合，但逻辑上完全自洽。NFAState.transitions用了setdefault(char, set())，这保证了同一字符多条边的并存——NFA 的“非确定性”就靠 set 来承载，而不是像 DFA 那样用单值 dict。
2.3 构造完成后检查 NFA 的连通性
NFA 构造完不是终点，最好遍历一遍确认所有转移都指向合法状态。常见的隐藏 bug 是 AST 出现了空指针——某个子表达式没解析出来，导致build返回了(None, None)，然后构造继续往下走，最后accept状态是None，确定化时一访问就崩。我通常在build入口加一个断言，断言node非空，凡是合法正则表达式必然经过Char/Concat/Union/Star四条路径之一。
3. NFA 确定化：子集构造法和 ε-闭包的计算顺序
3.1 ε-闭包：用栈而不是递归去求
NFA 确定化的第一步是算 ε-闭包：从一个状态集合出发，沿着 ε 边能到达的所有状态全部收集进来。很多教程用递归写，但我建议用显式栈，两个原因：第一，深度嵌套的闭包会导致递归栈溢出；第二，stack 版本调试时能直接打印中间状态，看每一步从哪个状态延伸出去。闭包计算本身就是把“状态集合”不断扩充直到稳定。
def epsilon_closure(states: set, nfa_states: dict) -> set: """输入一个状态集合，返回包含所有 ε 可达状态的闭包集合 nfa_states: {state_id: NFAState} 的映射表 """ stack = list(states) # 用栈模拟递归 closure = set(states) while stack: s = stack.pop() st = nfa_states[s] for target in st.transitions.get(None, set()): # ε 边 if target.id not in closure: closure.add(target.id) stack.append(target.id) return closure注意这里的nfa_states参数：我实现时把所有 NFA 状态用一个全局字典{id: NFAState}管理起来，避免拿着状态对象到处传引用。用状态 id 而不是对象本身作为集合元素，是为了后面确定化时能对集合做哈希。epsilon_closure的核心就是“发现新状态就入栈，直到栈空”——这保证了闭包的传递性：a 能到 b、b 能到 c，那么 a 到 c 也会被收进来。
3.2 子集构造法：move 之后做闭包
子集构造法的主体流程是：从 NFA 初态的 ε-闭包开始，作为 DFA 的初始状态；然后对每个 DFA 状态，遍历字母表里的每个字符，求 move（所有状态沿着该字符的边能到达的 NFA 状态集合），再对这个集合求 ε-闭包，得到新的 DFA 状态。如果新状态未出现过，就入队继续处理。循环直到队列为空。注意 move 不包含 ε 转移——字符边的目标状态要先收集，再由 ε-闭包扩展出去。
def nfa_to_dfa(nfa: NFA, nfa_states: dict, alphabet: set) -> dict: """子集构造法：NFA -> DFA 返回 dfa: dfa['start'] = 初始状态编号 dfa['transitions'] = {state: {char: next_state}} dfa['accept'] = set(接受状态编号) """ start_closure = epsilon_closure({nfa.start.id}, nfa_states) dfa_state_map = {} # frozenset(NFA状态集) -> DFA状态编号 state_counter = 0 dfa_state_map[frozenset(start_closure)] = state_counter unprocessed = [state_counter] dfa_transitions = {} dfa_accept = set() while unprocessed: current_dfa_id = unprocessed.pop() current_nfa_set = {s for s, dfa_id in dfa_state_map.items() if dfa_id == current_dfa_id} current_nfa_set = set(list(current_nfa_set)[0]) # 取第一个匹配的 frozenset dfa_transitions[current_dfa_id] = {} for ch in sorted(alphabet): move_result = set() for nfa_sid in current_nfa_set: st = nfa_states[nfa_sid] for target in st.transitions.get(ch, set()): move_result.add(target.id) if not move_result: continue # 没有该字符上的转移，跳过 closure = epsilon_closure(move_result, nfa_states) key = frozenset(closure) if key not in dfa_state_map: state_counter += 1 dfa_state_map[key] = state_counter unprocessed.append(state_counter) dfa_transitions[current_dfa_id][ch] = dfa_state_map[key] # 原 NFA 接受状态若在当前集合中，则该 DFA 状态为接受态 if nfa.accept.id in current_nfa_set: dfa_accept.add(current_dfa_id) return { 'start': 0, 'transitions': dfa_transitions, 'accept': dfa_accept, }这段里有三个细节值得讲。第一，我用frozenset作为字典dfa_state_map的键，set 本身不可哈希，但 frozenset 可以，这样“NFA 状态集合”才能作为 key 去查状态编号。第二，查找当前 DFA 状态对应的 NFA 状态集时，用了列表推导式再取第一个——这写法稍显别扭，但避免了额外维护一张反向表；实际工程里我会同时维护id_to_nfa_set和nfa_set_to_id两张表，写法更直白。第三，接受态判断是“当前 NFA 集合里是否包含原 NFA 的唯一接受状态”，这在多接受态的 NFA 场景下同样成立，只要把接受状态列表传入判断即可。
这里还要注意sorted(alphabet)：字母表需要预先确定。我一般从正则字符串里收集所有Char节点中的字符，再加上一个 ε 占位符。如果你要支持大写小写混合，直接收集字符串里出现的所有字符即可。若字母表很大（比如全 ASCII 字符），DFA 的转移表会变成一个稀疏矩阵，这时候用 dict 存储比二维数组更省内存。
4. DFA 最小化：划分法、Hopcroft 与边界参数
4.1 划分法的一个可运行实现
DFA 最小化本质上是状态等价类合并。两个 DFA 状态等价当且仅当：二者同为接受或同为非接受，并且对字母表中每个字符，它们转移到的新状态属于同一个等价类。求等价类最朴素的方法是反复划分：初始把所有接受态放一组、非接受态放另一组，然后每一轮根据转移目的地所属的组号重新细分，直到组别不再变化。
def minimize_dfa(dfa: dict) -> dict: """划分法最小化 DFA，返回新的 DFA 结构""" transitions = dfa['transitions'] accept = dfa['accept'] all_states = set(transitions.keys()) alphabet = set() for t in transitions.values(): alphabet.update(t.keys()) # 初始划分：接受态 / 非接受态 groups = [] acc_group = [s for s in all_states if s in accept] non_acc_group = [s for s in all_states if s not in accept] if acc_group: groups.append(set(acc_group)) if non_acc_group: groups.append(set(non_acc_group)) changed = True while changed: changed = False new_groups = [] for group in groups: # 用该组第一个状态作为参照，遍历组内状态归类 representatives = {} for state in sorted(group): # 生成该状态的签名：每个字符的转移目标落在哪个组 signature = [] for ch in sorted(alphabet): nxt = transitions[state].get(ch) if nxt is None: signature.append(-1) else: for gi, g in enumerate(groups): if nxt in g: signature.append(gi) break signature = tuple(signature) if signature not in representatives: representatives[signature] = set() representatives[signature].add(state) if len(representatives) > 1: changed = True new_groups.extend(representatives.values()) groups = new_groups # 组编号 -> 新状态编号 new_start = None new_accept = set() new_transitions = {} old_to_new = {} for new_id, group in enumerate(groups): for old_state in group: old_to_new[old_state] = new_id for old_state, new_id in old_to_new.items(): new_transitions[new_id] = {} for ch in sorted(alphabet): nxt = transitions[old_state].get(ch) if nxt is not None: new_transitions[new_id][ch] = old_to_new[nxt] if old_state in accept: new_accept.add(new_id) if old_state == dfa['start']: new_start = new_id return { 'start': new_start, 'transitions': new_transitions, 'accept': new_accept, }这里给每个状态算了一个“签名”：对字母表里每个字符，看转移目标落在哪个划分组里。只有当签名完全一致的状态才会留在同一组。初始划分把接受态和非接受态分开，这是最小化正确性的前提——接受状态永远不能和非接受状态合并。循环终止条件是changed = False，说明所有组已经无法再细分，此时每组内的状态就是两两等价的。
我在签名里给缺失转移设了-1，当作一个特殊的“error 组”。这个设计在词法分析场景里很重要：如果你把所有缺失转移统一指向死状态，那么最终 DFA 里会出现一个巨大的死状态组；如果不建死状态，缺失转移在签名里就要有独立标记，否则两个“都缺某个边”的状态可能被错误合并。具体取舍取决于你的匹配语义——是做完整匹配（需要死状态）还是做前缀匹配（直接丢弃死状态）。
4.2 Hopcroft 比划分法好在哪，什么时候值得换
上面这个划分法的复杂度是 O(n²·k)，n 是状态数，k 是字母表大小。当状态数达到几千，字母表达到两百多个字符时，肉眼可见地慢。Hopcroft 算法引入了一个“反向传播”机制：每次分裂一个组时，只对被影响到的组重新检查，复杂度可以降到 O(n·log n)。但代价是代码复杂度陡然上升。
我的取舍是：如果 DFA 状态数少于 500，用划分法，因为实现简单、不容易写错、瓶颈不在性能。如果要做超大词法分析器（几万个状态），我会把划分法当作正确性参考实现，再用 Hopcroft 重写核心循环。这里给一个判断依据：状态数 n 和字母表大小时的签名计算量是 n·k，分组细查时每轮最坏要遍历全组状态，如果你的正则集合来自几十条手写规则，n 基本在 100 以内，划分法完全够用。
实际工程里还有第三招可以大幅减少最小化压力：在做确定化时就给 NFA 状态集做“分组预剪枝”——两个 NFA 状态如果连字符边都不同，根本不需要合并。这个优化放到 Thompson 构造阶段做，能直接让生成的 DFA 状态数下降一个量级。
5. 自动机项目必踩的五个坑：现象、原因、解决
5.1 深层嵌套括号导致递归爆栈
现象：正则((((...))))嵌套深度到一千层时，RegexParser.parse_union递归抛RecursionError。
原因：递归下降解析器的调用深度和括号嵌套深度成正比，Python 默认递归上限约 1000 层，课堂样例的深度刚好卡在边界上。
解决：两个思路。一个是在解析器外部用迭代器替代递归，把pos游标放进显式栈；另一个是接受这个限制，在入口捕获RecursionError并提示“正则嵌套过深”。我一般建议项目里统一捕获，因为正则嵌套深度超过 200 的场景本就极少，把有限的时间花到更常见的坑上。
5.2 拿 set 直接当 dict 的 key 崩溃
现象：dfa_state_map[closure_set] = state_id直接抛TypeError: unhashable type: 'set'。
原因：子集构造法求出的闭包结果是 set，set 是可变对象，Python 不允许可变对象作为字典键。
解决：使用frozenset(closure)作为 key。注意一个隐藏问题：如果集合内含状态对象而非状态 id，而状态对象是自定义 class，那类里有无__hash__会影响 frozenset 本身能否创建。我统一用NFAState.id整数作为集合元素，最大程度规避哈希问题。
5.3 最小化之后发现“死状态”消失，匹配结果反而错了
现象：某条边缺失时，最小化后的自动机直接报 KeyError 或返回 False，但原始 DFA 在缺失边时应该进入一个不可接受状态并继续耗尽输入。
原因：DFA 定义里转移函数是全函数，每个状态对每个字符都必须有定义；而你实现时用 dict 省略了缺失边，最小化签名里把“缺失边”当成同一类，与真实语义不符。
解决：如果你要严格匹配“从初态到终态且整串耗尽”，必须显式建死状态DEAD，把缺失转移全部指向它，再参加最小化。如果你做的是前缀匹配（比如流式解析，失败就停止），可以直接删掉死状态，但要保证所有接受路径不依赖它。这个选择必须写死在代码注释里，否则三个月后自己都会忘。
5.4 字符集太大导致 DFA 转移表膨胀
现象：要匹配任意 Unicode 字符，用ord(ch)把字符作为转移矩阵的列索引，结果矩阵稀疏到浪费大量内存，最小化慢到无法接受。
原因：DFA 的转移表是按“字符”展开的，字符集多大转移表就有多宽。全 Unicode 十多万字符，矩阵解法直接不可行。
解决：把字符按类别压缩到等价类。比如数字0-9、小写字母、标点符号各自归为一个类。做法是在做 Thompson 构造时就给Char节点打上“字符类”标记，转移表只按类索引。常见的符号类不超过 20 个，矩阵规模和最小化耗时瞬间降低几个数量级。代价是冲突检测变复杂，两个字符类若有交集，状态分裂时需要按交集补拆。
5.5 最小化后状态编号错乱，无法对照原始 DFA
现象：最小化输出的状态编号重排后，想回查“哪个原始状态被合并了”发现 info 丢失。排错时只能靠重新跑一轮、打印中间划分结果才能看懂。
原因：old_to_new字典记录了映射，但只存在于闭环内部；输出时只保留新状态，原始分组信息全部丢弃。
解决：返回的 DFA 结构里加一个字段groups，值是{new_state_id: frozenset(old_state_ids)}。调试时直接打印它，一眼看出哪些旧状态等价。这个附加信息还能用于生成状态合并报告，或者做“ NFA 状态到 DFA 状态的追溯链”，在词法分析器报错时定位到具体正则片段。
6. 验证与进阶：证明你的自动机和 re 模块等价
6.1 随机生成正则做等价性测试
手动测试永远测不完所有分支。我的做法是写一个随机正则生成器，批量生成带闭包、连接、并选择的表达式，然后对同一段随机文本跑两遍：一遍用我写的自动机匹配，一遍用 Pythonre模块全匹配，比对结果。这个测试脚本写好后挂进 CI，一旦失败就说明实现里还有没覆盖的边界。
import random import re def random_regex(depth=0): """生成一个随机的简单正则表达式字符串""" chars = ['a', 'b', 'c', '1', '2'] if depth > 3: return random.choice(chars) kind = random.choices( ['char', 'union', 'concat', 'star'], weights=[4, 2, 2, 1] )[0] if kind == 'char': return random.choice(chars) if kind == 'union': return f"({random_regex(depth+1)}|{random_regex(depth+1)})" if kind == 'concat': return f"{random_regex(depth+1)}{random_regex(depth+1)}" return f"({random_regex(depth+1)})*" def run_matching(automaton, text: str) -> bool: """对完整文本做自动机匹配，遍历直到耗尽或失败""" state = automaton['start'] for ch in text: trans = automaton['transitions'].get(state, {}) if ch not in trans: return False state = trans[ch] return state in automaton['accept'] def test_equivalence(rounds=2000): for i in range(rounds): pattern = random_regex() nfa = build_pipeline(pattern) # 你自己的全流程函数 dfa = nfa_to_dfa(nfa) min_dfa = minimize_dfa(dfa) for _ in range(20): text = ''.join(random.choice(['a','b','c','1','2','']) for _ in range(6)) mine = run_matching(min_dfa, text) builtin = re.fullmatch(pattern, text) is not None if mine != builtin: print(f"Mismatch! pattern={pattern} text={text!r} mine={mine} re={builtin}") return False print(f"All {rounds} patterns passed.") return True测试时有两个参数要留意：random_regex的depth控制嵌套深度，深度太浅测不到闭包套并选的组合；文本长度设为 6 是因为短文本更容易撞上边界——比如空串匹配a*、单字符匹配(a|b)*。我把re.fullmatch作为标准答案，因为自动机做的是整串匹配而不是子串搜索，两者语义必须对齐。如果你做的是前缀匹配，就要改用re.match做对照，否则测试本身就会给出错误的失败信号。
随机测试的覆盖面广，但也有盲区：字符集中不含特殊字符，括号和|的复杂组合可能生成不出来。补一层定向测试：手写一组“教科书陷阱”正则，比如(a|)*这种空并选择、()*这种空闭包、(a*)*这种嵌套闭包，确保它们在两种实现下行为一致。这组用例在改动解析器后一定要重新跑一遍，我吃过一次亏：优化了parse_concat的空列表逻辑，结果()意外匹配了任意字符串，随机测试因为不生成空括号完全没发现。
6.2 让最小化 DFA 能输出动作码
最后给这个工具链加一个词法分析器常用的升级：给接受状态带上动作码。在最小化后的 DFA 分组信息基础上，我们把每个接受状态映射到一个 token 类型，比如ID,NUM,OP。这样匹配到终态时，不仅知道“匹配成功”，还知道“匹配的是什么类型的词法单元”。这一步需要在前面nfa_to_dfa时记录“DFA 状态是否接受、来自哪些 NFA 接受状态”，最小化时按分组合并动作码。
我惯用的做法是给transitions加一个accept_action字段，accept集合改成{state_id: action}的字典。正规表达式每组对应一种 token 类型后，手写词法分析器的最长匹配就变成“跑 DFA 记录最近一个接受状态，输入耗尽后回溯到那个状态”。这个方法比每次重新尝试所有正则要快得多，也是 Lex/Flex 这类工具的真正工作方式。
这个项目的血泪经验如果用一句话收，就是：NFA 确定化和 DFA 最小化的坑大多不在算法本身，而在边界条件的取舍——ε-闭包的集合表示、缺失转移的语义、字符集的粒度、状态编号的匹配。把这些想清楚了，自动机代码看起来是编译原理的习题，实际上已经是可以交付到生产环境的基础构件。希望帮到你。
本文还有配套的精品资源，点击获取
