自己动手开发编译器三有穷自动机在前两篇文章中我们讨论了词法分析的基本概念和正则表达式。但正则表达式本身只是一串字符真正让它们产生威力的是背后的自动机理论。有穷自动机Finite Automaton是词法分析器的核心引擎它负责将正则表达式转化为可执行的匹配逻辑。本文将从数学定义出发逐步构建一个可用的确定性有穷自动机DFA并展示它如何驱动一个简单的词法分析器。### 从正则表达式到NFA再到DFA编译器教材通常会介绍两条路径一是直接将正则表达式转换为非确定性有穷自动机NFA再通过子集构造法转为DFA二是直接构造DFA如Brzozowski导数法。这里我们采用经典的Thompson构造法因为它直观且易于实现。NFA的定义一个五元组 (Q, Σ, δ, q0, F)其中- Q状态集合- Σ输入字母表- δ状态转移函数允许ε空串转移- q0起始状态- F接受状态集合NFA的“非确定性”体现在同一状态对同一输入可能有多个转移且存在ε转移。而DFA则要求每个状态对每个输入符号有且仅有一个转移。子集构造法的核心思想是将NFA的状态集合映射为DFA的单一状态。DFA中的每个状态是NFA状态的一个子集。通过计算ε-闭包即从某状态出发仅通过ε转移能到达的所有状态来消除不确定性。### 实现一个NFA的Thompson构造器我们先定义NFA的数据结构。这里使用Python因为它简洁且适合教学。pythonclass NFAState: NFA状态节点 def __init__(self, is_acceptFalse): self.is_accept is_accept self.transitions {} # 键输入符号None表示ε值目标状态列表 def add_transition(self, symbol, target): self.transitions.setdefault(symbol, []).append(target)class NFA: 完整的NFA包含起始和接受状态 def __init__(self, start, accept): self.start start self.accept accept接下来实现Thompson构造法的核心函数。对于基本符号、连接、选择和闭包操作我们分别构造子NFA并组合。pythondef thompson_basic(symbol): 构建匹配单个字符的NFA start NFAState() accept NFAState(is_acceptTrue) start.add_transition(symbol, accept) return NFA(start, accept)def thompson_concat(nfa1, nfa2): 连接两个NFAnfa1后跟nfa2 nfa1.accept.is_accept False nfa1.accept.add_transition(None, nfa2.start) # ε转移连接 return NFA(nfa1.start, nfa2.accept)def thompson_union(nfa1, nfa2): 选择匹配nfa1或nfa2 start NFAState() accept NFAState(is_acceptTrue) start.add_transition(None, nfa1.start) start.add_transition(None, nfa2.start) nfa1.accept.is_accept False nfa2.accept.is_accept False nfa1.accept.add_transition(None, accept) nfa2.accept.add_transition(None, accept) return NFA(start, accept)def thompson_star(nfa): 闭包匹配0次或多次 start NFAState() accept NFAState(is_acceptTrue) start.add_transition(None, nfa.start) start.add_transition(None, accept) nfa.accept.is_accept False nfa.accept.add_transition(None, nfa.start) # 循环 nfa.accept.add_transition(None, accept) return NFA(start, accept)以上代码实现了正则表达式的基本操作。例如正则表达式a(b|c)*可以用这些函数组合出来。但实际编译器还需要解析正则表达式的语法树这里我们简化处理假设已有AST。### 子集构造法将NFA转换为DFA有了NFA我们下一步是将其转换为DFA。子集构造法的步骤如下1. 计算起始状态的ε-闭包作为DFA的起始状态一个NFA状态集合。2. 对每个DFA状态和每个输入符号找出所有可能的NFA转移并计算这些目标的ε-闭包形成新DFA状态。3. 重复直到没有新状态出现。下面给出完整实现pythondef epsilon_closure(states, nfa): 计算给定NFA状态集合的ε-闭包 stack list(states) closure set(states) while stack: state stack.pop() for target in state.transitions.get(None, []): if target not in closure: closure.add(target) stack.append(target) return frozenset(closure)def nfa_to_dfa(nfa, alphabet): 子集构造法NFA转DFA start_closure epsilon_closure({nfa.start}, nfa) dfa_states [start_closure] # 存储DFA状态每个是frozenset dfa_transitions [] # 对应每个DFA状态的转移表 dfa_accept [] # 是否为接受状态 unprocessed [0] # 待处理状态索引 while unprocessed: idx unprocessed.pop() dfa_transitions.append({}) # 判断是否包含NFA接受状态 dfa_accept.append(any(s.is_accept for s in dfa_states[idx])) for symbol in alphabet: # 计算所有可转移的NFA状态 targets set() for nfa_state in dfa_states[idx]: for t in nfa_state.transitions.get(symbol, []): targets.add(t) if targets: closure epsilon_closure(targets, nfa) if closure not in dfa_states: dfa_states.append(closure) unprocessed.append(len(dfa_states)-1) dfa_transitions[idx][symbol] dfa_states.index(closure) return DFA(dfa_states, dfa_transitions, dfa_accept)这里我们定义了DFA类来存储结果。注意alphabet需要预先确定通常是从正则表达式中提取的字符集合。### 用DFA驱动一个迷你词法分析器现在我们有DFA可以编写一个简单的词法分析器。它接受输入字符串从起始状态开始根据每个字符进行状态转移如果最终停在接受状态则成功否则失败。为了提高效率我们采用“最长匹配”策略在处理过程中记录最后一个接受状态的位置。pythonclass DFA: def __init__(self, states, transitions, accept): self.states states self.transitions transitions self.accept accept def longest_match(self, text, start_pos): 从start_pos开始寻找最长匹配的token current_state 0 last_accept_pos -1 for i in range(start_pos, len(text)): char text[i] if char not in self.transitions[current_state]: break current_state self.transitions[current_state][char] if self.accept[current_state]: last_accept_pos i 1 # 记录接受位置不含当前字符 return last_accept_posdef tokenize(dfa, text): 使用DFA进行词法分析 tokens [] pos 0 while pos len(text): # 跳过空白 while pos len(text) and text[pos].isspace(): pos 1 if pos len(text): break end dfa.longest_match(text, pos) if end -1: raise ValueError(f无法识别字符: {text[pos]} at position {pos}) tokens.append(text[pos:end]) pos end return tokens# 示例识别标识符字母开头后跟字母数字# 正则表达式 [a-zA-Z][a-zA-Z0-9]*# 我们手动构建NFA简化只处理a和b来演示# 实际可用thompson函数构建这里为了可读性直接构造上述代码展示了DFA如何应用于词法分析。longest_match函数实现了最长匹配这是词法分析中避免“if”被识别为“i”和“f”两个token的关键。### 最小化DFADFA构造完成后可能包含冗余状态。最小化可以显著减少状态数提升运行效率。常用的方法是Hopcroft算法或Moore算法。核心思想是划分等价类两个状态等价当且仅当它们对任何输入都转移到等价状态且接受性相同。这里我们简要介绍分区细化法pythondef minimize_dfa(dfa, alphabet): 简单分区细化法最小化DFA # 初始分区接受状态和非接受状态 partition [set(), set()] for i, acc in enumerate(dfa.accept): partition[0 if acc else 1].add(i) partition [p for p in partition if p] changed True while changed: changed False new_partition [] for group in partition: # 按转移行为细分 split {} for state in group: signature tuple(dfa.transitions[state].get(s, -1) for s in alphabet) # 将签名映射到分组编号 key None for i, g in enumerate(partition): if signature in [tuple(dfa.transitions[s].get(c, -1) for c in alphabet) for s in g]: key i break split.setdefault(key, set()).add(state) if len(split) 1: changed True new_partition.extend(split.values()) else: new_partition.append(group) partition new_partition # 构建新DFA state_map {} new_states [] new_transitions [] new_accept [] for group in partition: rep next(iter(group)) state_map[rep] len(new_states) new_states.append(group) new_accept.append(dfa.accept[rep]) new_transitions.append({}) for rep, idx in state_map.items(): for sym in alphabet: if sym in dfa.transitions[rep]: target dfa.transitions[rep][sym] new_transitions[idx][sym] state_map[target] return DFA(new_states, new_transitions, new_accept)这个实现虽然简单但时间复杂度较高O(n^2)实际编译器会使用更高效的Hopcroft算法。不过对于教学目的它足够清晰。### 总结有穷自动机是词法分析的理论基石。本文从NFA的Thompson构造出发实现了子集构造法将其转化为DFA并展示了DFA如何驱动一个支持最长匹配的词法分析器。最后给出了一个简单的DFA最小化方法。通过亲手实现这些算法我们不仅理解了编译原理中的经典理论也掌握了构建高效词法分析器的核心技术。实际生产级的编译器如Lex、Flex还会处理字符类、优先级、状态复用等复杂问题但核心框架与本文一致。下一步我们将进入语法分析阶段看看如何用上下文无关文法来解析token序列。