#compilers #词法分析
本页目录

正则与自动机

词法分析的第一步:把正则表达式变成可高效执行的自动机。正则→NFA→DFA→最小化 DFA 这条转换链,决定了词法器的速度和正确性,也分出了回溯引擎和自动机引擎两条路线。

概述

词法分析(lexing)是编译的第一道工序:把源码字符串切成 token 序列。这道工序的数学基础是正则语言和有限自动机⁠。理解"正则→NFA→DFA→最小化 DFA"这条转换链,不仅知道词法器为什么这样工作,也能分清两类正则引擎:基于自动机的 RE2/Hyperscan(线性时间,无回溯)和基于回溯的 PCRE(指数级最坏情况)。这篇把转换链每一步的算法和数据流讲清楚。

正则表达式:描述模式的代数

正则表达式用三种基本运算描述字符串集合(语言):

  • 连接⁠:ab 匹配 "a" 后跟 "b"
  • 交替⁠:a|b 匹配 "a" 或 "b"
  • Kleene 闭包⁠:a* 匹配零或多个 "a"

合法正则在这三种运算下封闭——任意组合仍是正则,这是后面"一定能转成自动机"的代数基础。

现代词法器里的正则加了便利语法(字符类 [a-z]、重复 +/?、捕获组),但核心不超出这三种运算。

NFA:Thompson 构造

NFA(Nondeterministic Finite Automaton) 是一个有穷状态集 + 转移关系,同一输入字符可以从一个状态到多个下一状态(非确定)。

Thompson 构造(1968)给出了从正则到 NFA 的系统性翻译。核心是 NFA 有一个明确的开始状态和一个明确的接受状态⁠,每种运算对应一个拼接模式:

Thompson 构造:正则运算 → NFA 拼接模式

基本单元 匹配字符 'a' start accept a

连接 e1e2 e1 的 NFA e2 的 NFA ε accept₁ → start₂

交替 e1|e2 start e1 的 NFA e2 的 NFA accept ε ε ε ε

Kleene 闭包 e* start e 的 NFA accept ε ε ε ↑ 重复循环 ↑ 跳过 e,匹配零次

ε 转移不消耗输入字符,是交替/闭包分叉与合并的关键机制; 状态数与正则长度成正比,不会像回溯引擎那样指数膨胀。

状态数和正则的长度成正比(每个字符/运算符产生少量新状态),不像回溯引擎可能指数膨胀。ε 转移(空转移:不消耗输入字符的状态跳转)在这里是关键机制——交替和闭包都靠 ε 分叉。

DFA:子集构造

NFA 的"非确定"意味着同一输入字符,当前可能处于多个状态的集合⁠。DFA 的核心洞察是把这些"状态集合"当成 DFA 的一个新状态——子集构造(subset construction):

算法:
  dfa_start = ε-closure({nfa_start})       ← 从 NFA 开始状态, 不消耗输入, 能到的所有状态
  worklist = [dfa_start]
  while worklist not empty:
    S = worklist.pop()
    for each input character c:
      T = ε-closure(move(S, c))            ← 从 S 中任一状态, 通过 c 能转移, 再 ε-闭包
      if T is new:
        worklist.push(T)
      添加 DFA 转移: S ─c─► T
  • move(S, c):从状态集 S 中,沿字符 c 能到达的所有状态(只看字符转移,不看 ε)。
  • ε-closure:从一组状态,不消耗输入、只沿 ε 转移能到达的所有状态(包括自身)。

这两个操作是子集构造的全部。最坏情况下 DFA 状态数是 NFA 状态数的指数级——但实际的词法正则极少触发最坏情况:大多数词法器的 DFA 状态数大致等同于 NFA 状态数。

这就是为什么词法器用 DFA(状态少、确定、每个字符 O(1)转移),而通用正则库(PCRE)用回溯——DFA 不能处理捕获组和反向引用,这两样是正则语法超出"真·正则语言"的部分。

DFA 最小化:Hopcroft 算法

子集构造产出的 DFA 可能有多余状态(两个状态对任何输入行为完全一样)。Hopcroft 算法把等价状态合并:

算法 (Hopcroft, O(n log n)):
  初始划分: 接受状态一堆, 非接受状态一堆
  while 划分还在变细:
    取一个划分块 A
    对于每个输入字符 c:
      如果 A 中的状态在 c 上的转移分别落到不同的划分块
        → 按"转移到哪块"把 A 进一步分裂

分裂到稳定状态——同一块内的状态对任何输入行为完全一致,可以合并成一个。Hopcroft 的 n log n 是目前理论最优(DFA 最小化的理论下界为 Ω(n log n), Hopcroft 算法已达到此最优;DFA 等价性判定则是另一个独立问题,可在 O(n) 时间内解决)。

实践中,多数词法生成器(lex/flex/re2c)做 DFA 最小化——词法器的 DFA 通常只有几百个状态,线性或近线性算法完全足够,没必要在常数优化上投入过多。

从自动机到词法器:longest match 与优先级

词法器不是简单地"跑 DFA 到第一个接受状态",而是最长匹配 + 优先级⁠:

算法 (maximal munch):
  从当前源码位置出发, 跑 DFA, 记录沿途遇到的每个接受状态及其位置
  直到 DFA 无法继续(死状态 / 无转移)
  回到最近一个接受状态 → 切出该 token
  从下一个字符重新开始
  • 最长匹配⁠:if 不会在识读了 i 后就停下来(即使 i 是合法的标识符 token),必须读完 if 且再读一个字符无法继续时才确认 token。
  • 优先级⁠:if 既是关键字又是合法标识符——关键词有更高优先级。在 DFA 构造时,把关键词的接受状态标记更高优先级;最长匹配后,如果多个接受状态匹配等长,选优先级最高的。

两类正则引擎:为什么这不仅仅是课本知识

理解 NFA→DFA 这条链,直接对应真实世界的正则引擎选型:

回溯引擎 (PCRE, Python re, JS)自动机引擎 (RE2, Hyperscan, Rust regex)
实现递归回溯NFA→DFA(或 NFA 模拟)
时间复杂度指数级最坏 (某些正则可触发)O(n)(输入长度线性)
捕获组支持有限/不支持
反向引用支持不支持(超出正则语言)
用途一次性小文本匹配高吞吐/不可信输入/流式

回溯引擎的本质是在 NFA 上做 DFS(深度优先),自动机引擎是"先构造 DFA,再对输入走 O(n) 扫描"。正则注入攻击(ReDoS)的根因就是回溯引擎对精心构造的正则指数爆炸——构造 DFA 则不存在这个问题。

这条边界也解释了词法器的正则和通用正则的区别:词法器的正则是"真·正则"(不需要捕获/反向引用),所以可以用 DFA;通用正则加了太多超正则能力,只能用回溯。

权衡与失败模式

  • DFA 状态爆炸⁠:某些正则(如嵌套量词 (a*)* 或 Kleene 星后跟复杂交替)会让子集构造产出指数级状态 → 实践中极少见,真触发时用 NFA 模拟(按需计算状态集)替代全量 DFA。
  • 最长匹配吃到不该吃的⁠:>> 可能被误认为嵌套泛型 >> vs 右移 → 词法器本身不能处理(需要语法分析器给上下文),词法器只管切。
  • Unicode 下的字符类⁠:\w 在 ASCII 和 Unicode 下含义不同,DFA 的字母表从 128 个暴涨到百万级 → 现代引擎用字符区间编码⁠(不枚举每个 Unicode 码位,而是存转移区间),alphabet 大小仍旧可控。

参考

  • Dragon Book(Aho, Lam, Sethi, Ullman): Chapter 3, Lexical Analysis — 正则→NFA→DFA→最小化的完整链条
  • Ken Thompson(1968): "Regular Expression Search Algorithm" (CACM 11(6)) — NFA 模拟的源头
  • Russ Cox(2007): "Regular Expression Matching Can Be Simple And Fast" — 透彻对比两类引擎

Keywords: regular expression, finite automaton, NFA, DFA, Thompson construction, subset construction, ε-closure, ε-transition, Hopcroft minimization, maximal munch, longest match, backtracking, RE2, ReDoS, character class, Unicode character intervals

相关页面

© 2026 liz's doc