正则与自动机

正则表达式描述一个字符串集合，有限自动机判断输入是否属于这个集合。词法分析器在此基础上还要回答：从当前位置开始，应该截取多长、归为哪一种 token？理解这三个问题的区别，才能把自动机理论用到真实词法器中。

正则语言：能记住有限种情况

连接 ab、交替 a|b、重复 a* 加上空串与空语言，构成经典正则表达式的基本运算。字符类和 +、? 等通常是便利写法。例如 [0-9]+ 表示一个或更多十进制数字。

有限自动机的“有限”指状态数量固定，不随输入增长。它可以记住当前数字是否已经出现小数点、字符串是否以某个固定后缀结尾；一般不能靠固定状态数记住任意深度的括号嵌套。嵌套注释等语言规则可以由词法器附加计数器处理，但这已超出纯有限自动机。

现代正则库的语法不全等于经典正则语言。⁠捕获组记录匹配位置，本身不使语言超出正则范围；反向引用要求再次匹配先前任意长度的内容，则可能描述非正则语言。 RE2 支持捕获组，但不支持反向引用。RE2 语法

NFA：并行保留所有仍可能成功的路径

NFA 允许同一状态在同一字符上走向多个状态，也可允许不消费字符的 ε 转移。输入被接受的条件是存在一条接受路径，不要求所有路径都成功。

Thompson 构造把每个正则子表达式变成带入口、出口的片段，再组合片段：连接把前一个出口接到后一个入口；交替增加 ε 分叉与汇合；星号同时增加“跳过整个片段”和“从出口回到入口重复”的路径。缺少回边的图只能表示可选一次，不能表示任意重复。

对展开后的基本正则表达式，构造的状态数与表达式规模成正比。这个结论讨论的是自动机大小，不能用来直接比较回溯引擎的匹配时间。

NFA 模拟维护活跃状态集合，每读一个字符更新集合，并把 ε 能到达的状态补齐。每一轮对状态去重，可避免反复探索相同的“状态、输入位置”组合。设 NFA 有 m 个状态，输入长度为 n，简单 Thompson 模拟的时间界为 O(mn)，活跃集合空间为 O(m)。固定模式时常简称对输入线性。Russ Cox：NFA 模拟

DFA：把一组 NFA 状态当成一个状态

DFA 对每个状态和输入符号只有一个下一状态。子集构造把“可能处于哪些 NFA 状态”提前编码成一个 DFA 状态。

图中读入 ab 后包含 q2，因此接受；若继续读 a，又回到集合 B，当前整串不再以 ab 结尾。状态表达的是读完整个当前前缀后仍需记住的信息。

子集构造的步骤是：

1. 起始集合为 ε-closure({start})，闭包包含集合自身。
2. 对一个集合 S 和字符 c，计算 T = ε-closure(move(S, c))。
3. 若 T 尚无编号，分配新状态并放入工作队列；记录 S 在 c 上到 T 的转移。
4. 直到没有新集合。包含任意 NFA 接受状态的集合标记为接受。

空集合可以表示显式死状态，也可以用缺失转移表示。实际实现常按字符等价类或区间处理，无须枚举所有 Unicode 码位。

若 NFA 有 m 个状态，潜在子集最多有 2^m 个；只生成可达集合仍可能指数增长。不能保证真实词法规则的 NFA 与 DFA 状态数相近。

一个直观例子是 (0|1)*1(0|1){k-1}：要求倒数第 k 个字符为 1。NFA 可以猜测哪个 1 是目标，DFA 则需要区分最近 k 位的组合；不同的 k 位后缀可用后续输入区分，因而需要至少 2^k 种状态。反之 (a*)* 与 a* 是同一语言，不是说明最小 DFA 指数增长的例子。

子集构造落地：把图中的三个集合全部算出来

图中的 NFA 不需要 ε 边，因此 move 后的集合本身就是下一集合。下面既直接模拟 NFA，又构造可达 DFA，最后对字母表 {a,b} 上长度 0 到 6 的全部 127 个串比较结果。

from collections import deque
from itertools import product

edges = {(0, "a"): {0, 1}, (0, "b"): {0}, (1, "b"): {2}}
start, accept = frozenset({0}), {2}


def move(states, char):
    return frozenset().union(*(edges.get((q, char), set()) for q in states))


numbers, subsets, transitions = {start: 0}, [start], {}
work = deque([start])
while work:
    current = work.popleft()
    for char in "ab":
        target = move(current, char)
        if target not in numbers:
            numbers[target] = len(subsets)
            subsets.append(target)
            work.append(target)
        transitions[numbers[current], char] = numbers[target]

assert set(subsets) == {frozenset({0}), frozenset({0, 1}), frozenset({0, 2})}
for length in range(7):
    for letters in product("ab", repeat=length):
        text = "".join(letters)
        nfa, dfa = start, 0
        for char in text:
            nfa = move(nfa, char)
            dfa = transitions[dfa, char]
        assert bool(nfa & accept) == bool(subsets[dfa] & accept) == text.endswith("ab")

转移表展示了为什么接受状态不是“永远成功”：C 读 a 后回 B，读 b 后回 A。这里判断的是整个输入是否以 ab 结尾；若需求是搜索任意位置出现的 ab，接受后的控制逻辑或自动机就要另行定义。

加入 ε 边后，起点与每次 move 的结果都要取闭包。下面的闭包模型允许 ε 环，通过 visited 集合保证每个状态只扩展一次：

def closure(seeds, epsilon):
    seen, work = set(seeds), list(seeds)
    while work:
        state = work.pop()
        for target in epsilon.get(state, ()):
            if target not in seen:
                seen.add(target)
                work.append(target)
    return frozenset(seen)


assert closure({0}, {0: {1}, 1: {0, 2}}) == frozenset({0, 1, 2})
assert closure({7}, {}) == frozenset({7})
assert closure(set(), {0: {1}}) == frozenset()

一个 DFA 状态，装着哪些 NFA 状态？

这里最容易混淆的是“只走一条路径”和“只保存一个集合名字”。下面把同一次前缀扫描的两种表示放在一起：NFA 保留所有可能状态，DFA 用 A、B、C 命名整个集合。直接改输入或选取前缀，可以检验两者的接受结果始终一致。读完 ab 后再读 a，接受状态也会离开；“已经接受过”不是永久接受。

$$S_{k+1}=\epsilon \text{-closure}(\mathrm{move}(S_k,c_k))$$

最小化：只有未来行为相同才可合并

两个 DFA 状态等价，是指从它们出发，任何后续字符串都得到相同的接受结果。最小化先按输出分类，再不断拆开未来行为不同的状态。

普通识别器可先分接受与非接受。⁠词法器必须进一步区分接受动作⁠：Identifier 与 Number 即使都是接受，也不能因为只看布尔接受性而合并，否则会丢掉 token 类型和规则优先级。

Hopcroft 算法用分割器及其转移前驱细化分区，并通过工作队列和较小子块策略控制重复处理。只写“反复扫描直到不再变化”是一般划分细化，并不足以证明 Hopcroft 的复杂度。对 n 个状态、字母表大小 k 的常见表述是 O(kn log n)；固定字母表时简写 O(n log n)。这也不是对所有计算模型宣称统一最优下界。

最小状态数不等于最快机器码。分支布局、表大小、缓存命中和向量化也影响吞吐；是否最小化及具体生成形式由工具与配置决定。

最长匹配与规则优先级

把多条 token 规则组成识别器后，一次扫描要保留最近接受位置及接受动作，直到不能继续，再回到该位置输出 token。若一直没有接受位置，则进入词法错误处理。

re2c 的规则选择就是先比较匹配长度，再在等长时选择较早规则。关键字也可以先按标识符扫描，再查表分类，两条路线都有效。re2c 手册

“单次 DFA 转移常数时间”也不自动保证整个最长匹配词法器线性。例如规则 a 与 a*b，输入为大量 a 后接 c：朴素扫描器每次为寻找 b 扫到尾部，再退回只接受一个 a，重复后可能达到平方级。需要结合规则的回退距离、实现的记忆化或其他扫描策略讨论整体复杂度。

量化回退代价：转移便宜，但同一字符可能被访问很多次

对规则 a 与 ab，输入 aaaaac。从位置 0 开始，为尝试更长的 ab 读过 5 个 a，直到 c 才确认不能完成；最近接受位置只允许输出一个 a。下一轮从位置 1 重来，又读 4 个 a，依此类推。仅 a 上的推进就有 5+4+3+2+1=15 次。

def rescans(n):
    source = "a" * n + "c"
    visits = 0
    for start in range(n):
        cursor = start
        while source[cursor] == "a":
            visits += 1
            cursor += 1
        # a*b 失败；退回单个 a 的接受位置，下一轮从 start+1 开始。
    return visits


assert rescans(5) == 15
for n in (1, 10, 100):
    assert rescans(n) == n * (n + 1) // 2

这里单独统计成功跨过 a 的次数，不含每轮在 c 上失败的检查。二次项已经来自重复后缀扫描，不必把每次状态转移本身变成昂贵操作。改善需要约束规则回退、记录失败后缀信息或采用适当扫描算法；不能把“使用 DFA”当作整个 token 流处理自动线性的证明。

转移很便宜，为什么扫描仍会变成平方级？

复杂度要数同一个输入位置被访问了几次。将一轮扫描画成一行，就能看到结尾 c 产生的三角形：第一行跨过 n 个 a，下一行跨过 n−1 个，最后只跨过一个。结尾换成 b 后，规则 a*b 一次覆盖整串，不再重复扫描后缀。图只统计 a 上的推进，错误字符 c 的处理另算。

$$W(n)=\sum _{i=1}^{n}i=\frac{n(n+1)}{2}$$

自动机与回溯引擎怎么比较

真实库可能组合多种策略。捕获位置和贪婪消歧需要额外信息，但并不迫使实现采用指数回溯。对不可信模式还应考虑编译内存限制；对不可信输入则需考虑匹配工作量，二者不能混为一个“线性安全”的标签。

继续阅读

词法器设计 将这些规则落到 token、位置、缓冲与错误恢复接口；递归下降与 LL 分析 继续处理 token 之间的嵌套结构。

Keywords: regular language, Thompson construction, NFA, DFA, subset construction, epsilon closure, Hopcroft, maximal munch, capture, backreference, ReDoS