自己动手开发编译器（三）有穷自动机

在前两篇文章中，我们讨论了词法分析的基本概念和正则表达式。但正则表达式本身只是一串字符，真正让它们产生威力的是背后的自动机理论。有穷自动机（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_accept=False): 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_accept=True) start.add_transition(symbol, accept) return NFA(start, accept)def thompson_concat(nfa1, nfa2): """连接两个NFA：nfa1后跟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_accept=True) 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_accept=True) 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序列。