5.4 Regular Expressions：Thompson NFA、epsilon closure与GREP

5.4 · Regular Expressions覆盖 5 个作者站正式主题，以章专属状态模型、逐步轨迹、反例恢复和独立预言机验收。

学习目标

  • 能解释“5.4 · Regular Expressions”如何把正则表达式编译为 Thompson NFA，并以 epsilon 闭包和字符转换执行识别
  • 能逐项核对 正则表达式、非确定有限状态自动机、空字符转换、NFA模拟、正则表达式grep，并区分作者站内容与本页独立补充
  • 能按“NFA 模拟对长度 M 的正则和长度 N 的文本最坏时间 O(MN)，空间 O(M)”手算一个最小输入，逐步检查“每轮状态集恰为读完当前文本前缀后可达的 NFA 状态 epsilon 闭包”
  • 能注入“构造交替或闭包时操作符栈配对错误，或字符转换后没有再次求 epsilon 闭包”，保存基线、首个分叉、恢复和同输入重放证据

来源、版次与独立重写边界

“5·4 · Regular Expressions”对应 Robert Sedgewick 与 Kevin Wayne 的 Algorithms, Fourth Edition（Addison-Wesley Professional，2011）。对这一节，作者维护的本节页面提供与教材协同的浓缩正文、Java 实现、图示、习题和部分答案；全书作者站给出 6 章、30 节的完整结构，并明确区分在线资料与纸质教材的学习用途。

“5·4 · Regular Expressions”的作者页公开经授权的在线节选和配套资源，但不是整本教材全文。因此“5·4 · Regular Expressions”采用 independent-rewrite / authorized-sample：中文讲解、推导与实验独立组织，不声称逐段翻译；算法名称、API 和示例边界以作者页、官方代码索引及官方勘误交叉核对。

作者站章节坐标：5.4 · Regular Expressions

  • 1. 正则表达式：在本页通过“解析正则 token”连接解释、交互状态和练习验收。
  • 2. 非确定有限状态自动机：在本页通过“建立 epsilon 转换”连接解释、交互状态和练习验收。
  • 3. 空字符转换：在本页通过“求初始闭包”连接解释、交互状态和练习验收。
  • 4. NFA模拟：在本页通过“消费一个文本字符”连接解释、交互状态和练习验收。
  • 5. 正则表达式grep：在本页通过“再闭包并判断接受”连接解释、交互状态和练习验收。

从“同一个输入位置，可以同时有多条合法路径”开始

正则表达式（regular expressions）不是“逐字符照着走的一条路线”，而是一张允许分支、跳过和循环的程序图。表达式 (A*B|AC)D 描述两类strings：零个或多个A后接BD，或者ACD。

先预测：输入 ACD 读到第一个A以后，应立刻断定走 A*B branch，还是同时保留“继续A*”与“转到AC”两种可能？若贪心地只猜一条路径，后续C可能让第一次选择失败；非确定有限状态自动机保留整个possible-state set，直到输入提供足够证据。

表达式E所描述的正则语言记作 (L(E))。三种核心组合的集合语义是：

L(E∣F)=L(E)∪L(F),L(EF)={xy:x∈L(E), y∈L(F)},L(E∗)=⋃k≥0L(E)k.\begin{aligned} L(E|F) &= L(E)\cup L(F),\\ L(EF) &= \{xy:x\in L(E),\,y\in L(F)\},\\ L(E^*) &= \bigcup_{k\ge 0}L(E)^k. \end{aligned}

Dot . 匹配任意一个character；parentheses控制分组。官方NFA recognizer判断整个input是否属于language，而不是默认寻找任意substring。

5.4.1 从regexp位置到NFA states

非确定有限状态自动机（nondeterministic finite automata）为length M的regexp建立M+1个states：

  • State i对应regexp character re[i]。
  • Literal或dot在匹配当前input character后从i进入i+1。
  • Parenthesis、alternation和star不消费input，它们由epsilon edges表达控制流。
  • State M是accept state；只有输入全部消费后M仍reachable才接受。

字符边无需存进digraph，因为从state i读到匹配字符时目标固定为i+1。Digraph只保存空字符转换（epsilon transitions）。

形式上，若当前states为S，读字符c后先计算character move：

move⁡(S,c)={i+1:i∈S∧(rei=c∨rei=.)}\operatorname{move}(S,c) =\{i+1:i\in S\land(re_i=c\lor re_i=\texttt{.})\}

然后再沿epsilon edges扩张。把literal edges与epsilon edges分开，是实现能使用普通Digraph与DirectedDFS的关键。

5.4.2 Thompson construction：单次扫描建立epsilon digraph

Thompson构造扫描regexp一次，用operator stack保存left parentheses和alternation positions。对普通token不加epsilon edge；对三个控制结构分别建图。

Parentheses与single alternation

遇到 ( 或 | 时把index压栈。遇到 ) 时弹栈：

  • 若弹出的是 (，它就是当前group的left endpoint。
  • 若弹出的是 |，再弹出matching (；从left parenthesis跳到right branch start，并从|跳到right parenthesis。
  • ( 与 ) 自己还各有pass-through epsilon edge，让control进入和退出group。
if (re[i] == '(' || re[i] == '|') {
    ops.push(i);
} else if (re[i] == ')') {
    int or = ops.pop();
    if (re[or] == '|') {
        lp = ops.pop();
        graph.addEdge(lp, or + 1);
        graph.addEdge(or, i);
    } else {
        lp = or;
    }
}

这段官方代码一次只处理parenthesized group中的single alternation。(A|B)可用；(A|B|C)不能直接假定正确，因为到)时stack上有多个|，需要扩展构造逻辑或改写为nested alternation。

Kleene star的forward与back edges

若token i的next character是*，令lp为该token或其group的left endpoint：

if (i < M - 1 && re[i + 1] == '*') {
    graph.addEdge(lp, i + 1);  // skip: zero copies
    graph.addEdge(i + 1, lp);  // repeat: another copy
}
if (re[i] == '(' || re[i] == '*' || re[i] == ')')
    graph.addEdge(i, i + 1);

Forward edge允许zero copies，back edge允许one more copy；*本身的pass-through edge允许退出循环。闭包作用于前一个atom或parenthesized expression，不是“任意字符”。

每个regexp position只进出stack常数次，也只添加constant number of epsilon edges。因此合法expression的构图时间与space都是 (O(M))。Production parser还应在构图前拒绝unbalanced parentheses、dangling operators和非法metacharacters；不能让stack underflow成为用户可见语义。

5.4.3 Epsilon closure：不读字符也能到达哪里

Epsilon闭包是NFA simulation的基本操作。给定source set S：

ε-closure(S)={v:∃s∈S, s⟶ε∗v}\varepsilon\text{-closure}(S) =\{v:\exists s\in S,\ s\overset{\varepsilon^*}{\longrightarrow}v\}

它就是epsilon digraph上的multiple-source reachability，可用DFS或BFS：

boolean[] marked = new boolean[M + 1];
Stack<Integer> stack = new Stack<>();
for (int source : sources) stack.push(source);
 
while (!stack.isEmpty()) {
    int v = stack.pop();
    if (marked[v]) continue;
    marked[v] = true;
    for (int w : graph.adj(v))
        if (!marked[w]) stack.push(w);
}

Visited set不可省略：star会制造epsilon cycles，不标记会无限遍历。Closure还必须包含source自身，否则literal state没有outgoing epsilon edge时会凭空消失。

一个可单独测试的closure certificate包含三条：

  1. S的每个state都在result中。
  2. Result内每个state都可由S沿epsilon-only path到达。
  3. Result对epsilon outgoing edges封闭，不存在result内state指向result外state。

5.4.4 NFA simulation：字符一步，再做闭包

NFA模拟（NFA simulation）从state 0的epsilon closure开始。每个input character执行两个阶段：

DirectedDFS dfs = new DirectedDFS(graph, 0);
Bag<Integer> pc = reachableStates(dfs);
 
for (int i = 0; i < txt.length(); i++) {
    Bag<Integer> match = new Bag<>();
    for (int v : pc) {
        if (v == M) continue;
        if (re[v] == txt.charAt(i) || re[v] == '.')
            match.add(v + 1);
    }
    dfs = new DirectedDFS(graph, match);
    pc = reachableStates(dfs);
}
return pc.contains(M);

读完input prefix x0…xj−1x_0\ldots x_{j-1} 后，possible set P的invariant是：

Pj=ε-closure({v:存在一条消耗恰好 j 个字符的NFA path到 v})P_j=\varepsilon\text{-closure} \left( \left\{v:\text{存在一条消耗恰好 }j\text{ 个字符的NFA path到 }v\right\} \right)

Initialization由state-0 closure成立。Character move把每条合法path延长恰好一个匹配字符；随后closure补齐所有zero-input moves，因此induction保持。最终接受条件是：

input∈L(re)⟺M∈PNinput\in L(re)\quad\Longleftrightarrow\quad M\in P_N

不能只问“某一步曾到过M吗”。若M在input尚未结束时reachable，而后续character无法消费，full-string recognizer仍必须reject。

另一个常见错误是只在initialization做一次epsilon closure。Alternation join、group exit和star loop都可能发生在任何character move之后，所以每次consume之后都必须重新闭包。

5.4.5 为什么上界是O(MN)，而不是指数回溯

NFA有M+1个states和O(M)条epsilon edges。每个input character：

  • 扫描possible states最多O(M)。
  • Multiple-source DFS最多访问O(M) vertices与edges。

所以官方Thompson NFA：

Tbuild=O(M),Trecognize=O(MN),S=O(M)T_{\mathrm{build}}=O(M),\qquad T_{\mathrm{recognize}}=O(MN),\qquad S=O(M)

Naive backtracking engine按path递归，ambiguous repetitions可能产生指数数量的选择序列。Thompson simulation把同一input position上抵达同一state的paths合并成一个set member，相当于memoize (state, input-index) pairs；最多只有 ((M+1)(N+1)) 个pair。

这不是说所有工业regex engine都指数，也不是说Thompson支持全部工业语法。Backreferences等feature不能由普通finite automaton直接表达；lookaround、captures和Unicode character classes也需要额外状态或engine machinery。本节保证只属于这里定义的regular subset。

5.4.6 GREP：把substring query变成full-string language

正则表达式grep（regular-expression grep）要判断“line中某个substring匹配query”。官方做法是包装：

String regexp = "(.*" + args[0] + ".*)";
NFA nfa = new NFA(regexp);
while (StdIn.hasNextLine()) {
    String line = StdIn.readLine();
    if (nfa.recognizes(line)) StdOut.println(line);
}

前后 .* 分别消费match之前与之后的任意characters，使whole-line recognition等价于substring search。GREP的contract仍应说明line boundaries、empty query、metacharacters与input encoding。

若query来自untrusted literal search，不能直接拼进regexp；A、parentheses、dot等是否是syntax必须由API明确。Literal grep应escape metacharacters，regex grep才把query解释为pattern。

5.4.7 官方实现边界：不要把subset说成完整regex

本节当前NFA.java支持concatenation、parentheses、single alternation、Kleene star和dot。以下不由当前代码直接支持：

  • + one-or-more operator。
  • 一个group中的multiway alternation。
  • Character classes与ranges，例如bracket notation。
  • Text自身含有regexp metacharacters时的literal escaping contract。
  • Capturing groups、backreferences、lookaround、anchors或lazy quantifiers。

这些边界不是理论上的regular-language限制，而是当前parser和construction的实现范围。扩展multiway alternation需要在matching parenthesis内收集所有or positions并为每个branch建entry/join edges；扩展+只要保留repeat back edge而不建立zero-copy skip。Character classes则要让一个state携带character predicate，而非单个literal。

5.4.8 Independent certificate：图、闭包和language corpus三层验收

只用一个accepted string不能证明recognizer正确。独立证书应分层：

  1. Construction：对known regexp比对expected epsilon edge set，尤其是alternation entry/join与star forward/back edges。
  2. Closure：对每个source set检查reachability、source inclusion和epsilon-closed invariant。
  3. Language：accepted与rejected corpus都与small reference oracle对照。
  4. Whole input：accept state只在全部N characters消费后判定。
  5. Boundary：invalid syntax被明确拒绝，不误当literal。
function verifyCandidate(re, corpus, expectedEdges, candidate) {
  assert(setEqual(candidate.epsilonEdges(), expectedEdges));
  for (const sourceSet of sampledSourceSets)
    assert(isExactEpsilonClosure(sourceSet, candidate.closure(sourceSet)));
  for (const [input, expected] of corpus)
    assert(candidate.recognizes(input) === expected);
}

Mutation tests尤其有效：删除star back edge应让multiple repetitions失败；伪造false accept应被negative corpus抓到；删除one branch应被accepted corpus抓到。Certificate使用图结构与external decisions，而不是复述candidate自己的trace。

5.4.9 逐步运行路线

先预测，再操作三个本节实验

分步1 / 3

1. 对象、操作与成本模型

先在“5.4 · Regular Expressions”的两个最小情境间切换，再逐项选择正式概念。预测“NFA 模拟对长度 M 的正则和长度 N 的文本最坏时间 O(MN)，空间 O(M)”在哪个前提下成立，并解释输入、操作和证书之间的关系。

Section model

5.4 · Regular Expressions：对象、操作与不变量

把正则表达式编译为 Thompson NFA，并以 epsilon 闭包和字符转换执行识别

选择最小情境

切换正式概念

输入合同操作证书algs4-5.4 · 先给前提，再执行，再验收当前概念：1/6
闭包路径
正则 A*B，文本 AAAB
当前观察
regular expressions：每次 A 后都可经 epsilon 返回闭包，最终 B 到达接受状态
NFA 模拟对长度 M 的正则和长度 N 的文本最坏时间 O(MN)，空间 O(M)

本节易错边界与可重放合同

练习与答案

练习

问题 1：目录与状态映射。 对下列正式概念逐项指出正文解释、交互状态和练习证据：

  • 正则表达式：在实验 1 中指出对应状态，并写出一个通过条件。
  • 非确定有限状态自动机：在实验 2 中指出对应状态，并写出一个通过条件。
  • 空字符转换：在实验 3 中指出对应状态，并写出一个通过条件。
  • NFA模拟：在实验 1 中指出对应状态，并写出一个通过条件。
  • 正则表达式grep：在实验 2 中指出对应状态，并写出一个通过条件。

问题 2：最小推演。 怎样证明“NFA 模拟对长度 M 的正则和长度 N 的文本最坏时间 O(MN)，空间 O(M)”不是孤立结论？

问题 3：故障恢复。 怎样证明“构造交替或闭包时操作符栈配对错误，或字符转换后没有再次求 epsilon 闭包”已经修复？

小结

  • Regular expressions以concatenation、alternation、closure和dot描述regular language。
  • Thompson nondeterministic finite automata把regexp position变成state，把control flow变成epsilon transitions。
  • Epsilon closure是epsilon digraph上的multiple-source reachability，包含sources并对epsilon edges封闭。
  • NFA simulation维护possible-state set，每个character执行matching move再取closure，最终只在input耗尽后检查accept state。
  • Construction O(M)，recognition O(MN)，因为相同state/input pair被set合并，而不是重复回溯。
  • Regular-expression grep用 (.*query.*) 把substring semantics转换为full-string recognition。
  • 官方实现是明确的regex subset；+、multiway-or、classes和工业regex features不能被悄悄假定支持。
  • Independent certificate同时核对epsilon graph、closure invariants、positive/negative corpus与whole-input contract。

资料与写作方式声明

本章以Algorithms, Fourth Edition的合法公开试读核定可见范围，并以目录限定未公开部分，并结合正文列出的技术资料独立重写；不宣称复现原书正文，也不沿用原作表述。

原作版权归作者与出版社所有；本站原创教学结构与表述仅供学习交流。

讨论

评论区加载中…