正则引擎中的有限自动机 ④ 复杂组合、语法糖、优化

1. 组合与分解

拥有了五大基础构建块后，面对真实世界中复杂的正则表达式，我们如何将其转化为等价的状态机？

答案是经典的软件工程方法学：

1. 分解（Decomposition）：自顶向下，将一个宏观复杂的表达式拆解为层层嵌套的小型子表达式。
2. 组合（Composition）：自底向上，利用我们编写的工厂函数（char, concat, or, rep），将微型状态机积木一层层封装、组装为巨大的复合机器。

---

1.1 操作符优先级阶梯 (Operator Precedence)

就像数学算术中有“先乘除后加减”一样，正则表达式中的操作符也有严格的优先级次序。在进行分解和求值时，必须严格遵守从高到低的优先级：

+────────────────────────────────────────────────────────+
| 优先级 1 (最高):   单个字符 / 字符集 (Literals: a, b)    |
| 优先级 2:          星号闭包 (Kleene Star: *)             |
| 优先级 3:          连接运算 (Concatenation: 隐式邻接 ab)  |
| 优先级 4 (最低):   并集运算 (Union: 管道符 |)             |
+────────────────────────────────────────────────────────+

1.2 运算优先级的实战指导意义

当遇到一个表达式时，优先级最低的操作符反而决定了整棵语法树的最顶层根节点！
因为要评估低优先级的操作符，必须先把它左右两侧的高优先级子表达式先完整计算出来。

1.2.1 经典案例实战拆解：/xy*|z/

考虑正则表达式：/xy*|z/
该模式能接受的合法字符串包括："x", "xy", "xyy", "xyyy", "z" 等。

树形递归分解过程 (AST 视角)

1. 第 1 层（最低优先级：Union |）：
   • 将表达式拆为左右两半：左半部分为 xy*，右半部分为 z。
2. 第 2 层（次低优先级：Concatenation 连接）：
   • 深入左半部分 xy*，它是一个连接模式：由字符 x 紧随子表达式 y* 构成。
3. 第 3 层（高优先级：Kleene Star 闭包）：
   • 深入 y*，它是一个克莱恩闭包运算：作用在单字符 y 之上。
4. 第 4 层（最高优先级：单字符）：
   • 最终到达原子基石：字符 'x'，字符 'y'，字符 'z'。

              Union (|)  <--- 顶层根节点 (最后执行)
             /         \
   Concatenation        Char ('z')
     /       \
Char ('x')  Kleene (*)
                |
            Char ('y')

1.2.2 两种工程实现范式的对比

范式	递归下降解释器 (AST Interpreter)	自动机编译器 (State Machine, 本课程范式)
工作原理	解析成 AST 语法树，运行时在树节点上递归遍历匹配。	将 AST 节点一对一编译为 NFA 状态图片段并最终生成状态转移表。
匹配速度	较慢（受限于函数递归调用开销与树遍历开销）。	极快（运行时脱离语法树，只剩下轻量的图指针跳转或数组查表）。

1.2.3 代码组装实战

假设我们已经实现了前面的工厂函数，构造 /xy*|z/ 的状态机代码就像拼积木一样清晰直观：

// 自底向上组装状态机
const yStarMachine = rep(char('y'));                  // y*
const xyStarMachine = concat(char('x'), yStarMachine); // xy*
const zMachine = char('z');                           // z

// 最终的大机器：xy* | z
const complexMachine = or(xyStarMachine, zMachine);

// 测试验证
complexMachine.test('x');    // true  (走上面分支，y 重复 0 次)
complexMachine.test('xy');   // true  (走上面分支，y 重复 1 次)
complexMachine.test('xyyy'); // true  (走上面分支，y 重复 3 次)
complexMachine.test('z');    // true  (走下面分支)
complexMachine.test('y');    // false
complexMachine.test('xyz');  // false

2. 什么是语法糖 (Syntactic Sugar)？

在计算机科学与编程语言设计中，语法糖（Syntactic Sugar）指的是一种语言构造：

• 它并不给语言引入任何新的核心表达能力（Expressive Power）；
• 它仅仅是一种更甜美、更符合人类阅读与书写习惯的语法外壳；
• 它的语义完全可以通过已有的基础特性组合表达出来。

为了支持这些便民语法，编译器通常只需要在编译前端执行一道自动脱糖（Desugaring / Rewriting）工序，将其还原为基础语法的等价形式即可。

常见正则语法糖的理论等价转换 (用 $\equiv$ 表示语义等价)

五大基础构建块中只包含了单字符、$\epsilon$、连接、并集和星号闭包。我们在现代正则中常见的 +、?、[...] 全部都可以用五大基础模型完美重写：

2.1 加号算子：+ (重复一次或多次)

• 人类直觉：匹配至少 1 次，往后不限。
• 理论等价重写：等于“该模式自身，紧随该模式的零次或多次闭包”（即连接运算 + 星号闭包）：
  $$A^+ \equiv A A^*$$
• 代码脱糖映射：

  function plus(fragment: NFA): NFA {
    return concat(fragment, rep(fragment));
  }

2.2 问号算子：? (零次或一次 / 可选匹配)

• 人类直觉：该模式是可选的（要么出现一次，要么完全没有）。
• 理论等价重写：等于“该模式自身”与“空串 $\epsilon$”的并集运算（即并集运算 + $\epsilon$ 机器）：
  $$A? \equiv A \mid \epsilon$$
• 代码脱糖映射：

  function opt(fragment: NFA): NFA {
    return or(fragment, epsilon());
  }

2.3 字符类 / 字符集：[abc]

• 人类直觉：匹配括号内列出的任意一个字符。
• 理论等价重写：等于这些单字符机器之间的多元并集（Union）：
  $$[a-c] \equiv a \mid b \mid c$$
• 衍生简写糖：
  • \d（数字） $\equiv [0-9] \equiv 0 \mid 1 \mid 2 \mid \dots \mid 9$
  • \w+ $\equiv ([a-zA-Z0-9_])^+$

---

2.4 理论重写实战演练

考虑带有语法糖的表达式：
$$/a+[0-9]?/$$

通过纯理论脱糖重写，它被无缝还原为仅含 5 大基础原语的等价长表达式：
$$\underbrace{(a \cdot a^*)}{a^+} \cdot \underbrace{((0 \mid 1 \mid \dots \mid 9) \mid \epsilon)}{[0-9]?}$$

2.5 理论优雅 vs. 工程灾难（抛出矛盾）

将语法糖重写为理论等价的组合，在数学理论上无可挑剔、无懈可击。
但是在工业级软件工程实现中，直接采用这种理论脱糖方案会引发严重的性能灾难！

• 例如：考虑一个常见的字符集重复 [0-9]+。如果盲目展开成：
  $$(0 \mid 1 \mid \dots \mid 9) \cdot (0 \mid 1 \mid \dots \mid 9)^*$$
  每一个并集都要引入 2 个新状态和 4 条 $\epsilon$ 边，连接又要引入状态，闭包再引入状态……生成出来的 NFA 状态节点数量会发生失控爆炸！
• 内存开销巨大，并且庞大臃肿的 $\epsilon$ 转移链会严重拖垮匹配执行速度。

3. 理论与工程的冲突：状态爆炸之痛

在上一讲中，我们看到加号操作符在理论上等价于 $A^+ \equiv AA^*$，字符集 $[a-c] \equiv a \mid b \mid c$。

现在我们来看看，如果盲目死板地使用理论脱糖去为一个微小的正则模式 [a-c]+ 构建 NFA，会发生什么恐怖的事情：

1. [a-c] 展开为 3 个字符的并集：产生 8 个状态；
2. 再加上星号闭包 [a-c]*：又引入外层状态与回环边；
3. 再通过连接运算把两者连起来：

• 最终结果：仅仅为了匹配一个简单的 [a-c]+，状态机图谱竟然膨胀到了整整 22 个状态节点和数十条 $\epsilon$ 空转移边！

这种机器在内存占用和图遍历执行效率上都是极其低劣且不可接受的。

---

核心优化哲学：语义等价下的极简化重构

系统工程第一军规：
只要最终对外呈现的语言识别语义（Semantics）得到 100% 完整保留，你可以采用任何更高效、更轻量级的内部实现，而不必拘泥于死板的理论构造步骤！

针对高频使用的语法糖，我们可以直接定制专属的轻量级 NFA 片段：

3.1 优化 1：字符集（Character Class）定制优化

• 痛点：原版把 $[abc]$ 展开为多重 Union 树，生成一堆辅助节点和 $\epsilon$ 边。
• 优化思路：
  既然单字符机是从起始态到接受态连一条字符边，那字符集为什么不直接在同一对起始和接受态之间拉出多条平行的字符边？
• 拓扑结构：仅需 2 个状态！

           ┌──── 'a' ────┐
           ├──── 'b' ────┤
  ( In ) ──┼──── 'c' ────┼──> (( Out ))
           └──── ... ────┘

• 效果：状态数从膨胀的数十个，被瞬间秒杀压缩到了仅剩 2 个状态！

export function optimizedChar(...characters: string[]): NFA {
    const inState = new State({ accepting: false });
    const outState = new State({ accepting: true });

    for (const char of characters) {
        inState.addTransitionForSymbol(char, outState);
    }
    return new NFA(inState, outState);
}

---

3.1 优化 2：加号算子（+）定制优化

• 语义：必须至少消耗一次，随后可以重复多次。
• 拓扑结构：仅需 2 个状态！

           ┌──────────── 'A' ────────────┐
           │                             ▼
  ( In ) ──┘                          (( Out )) 
           ▲                             │
           └───────────── ε ─────────────┘

• 核心差异：
  相比于星号闭包 *，加号 + 唯独去掉了最下层“从 In 直达 Out 跳过 0 次”的 $\epsilon$ 旁路边！
  必须先通过字符边至少踏入一次终点，随后再靠回环 $\epsilon$ 边返回起点继续循环。

export function plus(frag: NFA): NFA {
    frag.outState.addTransitionForSymbol(EPSILON, frag.inState);
    return frag;
}

3.3 优化 3：问号算子（?）定制优化

• 语义：可选（出现 0 次或 1 次）。
• 拓扑结构：仅需 2 个状态！

     ┌────────── ε (跳过0次) ──────────┐
     ▼                                 ▼
  ( In ) ────────── 'A' (匹配1次) ──> (( Out ))

• 效果：一条字符边管“出现 1 次”，一条 $\epsilon$ 边管“跳过 0 次”，干脆利落。

export function optional(frag: NFA): NFA {
    frag.inState.addTransitionForSymbol(EPSILON, frag.outState);
    return frag;
}

3.4 优化 4：星号闭包（*）的轻量级紧凑形态

• 原始版本需要 4 个状态维护严格的层级包裹。
• 优化版本：压缩为 2 个状态！

     ┌────────── ε (跳过0次) ──────────┐
     ▼                                 ▼
  ( In ) ────────── 'A' ──────────> (( Out ))
     ▲                                 │
     └────────── ε (多次回环) ─────────┘

---

3.5 优化前后的惊人对比

以匹配 [a-c]+ 为例：

维度	理论纯脱糖版本 ($AA^*$)	定制工程优化版本
状态节点总数	22 个状态	仅需 2 个状态！
$\epsilon$ 空转移数量	数十条冗余跳转	仅 1 条回环边
内存占用	庞大臃肿	极低
匹配穿透耗时	漫长试探与图跳转	几乎无损直达

打赏