正则引擎中的有限自动机 ③ 5个基础状态机

编译原理
字数统计: 5.8k   |   阅读时长≈ 22 分钟

1. 渐进式构造思想与架构不变量

在第一模块中，我们实现了面向对象的底层节点类 State。从本模块开始，我们将使用渐进式实现方法（Gradual Implementation Approach）：从最简单的原子级自动机片段开始，像搭积木一样逐步组合出支撑复杂正则表达式的高性能复合机器。

在进入具体机器之前，必须确立贯穿整个自动机引擎的核心架构法则：

核心架构不变量 (The Architectural Invariant)

无论一个自动机内部多么复杂（无论是单个字符、还是包含成百上千个状态的复合模式），每一个独立的 NFA 片段在对外抽象时，必须始终严格保持：

  1. 仅有唯一的一个起始状态（One Input State）；
  2. 仅有唯一的一个终止接受状态（One Output State / Accepting State）。
1
2
3
          ┌─────────────────────────────────────────┐
[输入状态] ───>│        NFA 片段内部逻辑 (黑盒)           │───> ((接受状态))
 (唯一入口)    └─────────────────────────────────────────┘      (唯一出口)

这个不变量是后续将不同子机器进行拼接、并联、嵌套的生命线。

2. 单字符机 (Single Character Machine)

2.1 语义与正则映射

单字符机对应于只显式接受一个指定字符的正则表达式（相当于被行首与行尾锚点锁定的单个字符，如 /^A$/）。

2.2 状态结构

根据不变量法则，单字符机仅由两个状态组成：

  • 一个起始状态（Input State）（accepting: false）；
  • 一个接受状态（Output State）（accepting: true）；
  • 两者之间通过一条标记为目标字符（如 'A'）的有向转移边相连。
1
2
3
( 状态 1 ) ────────── 'A' ──────────> (( 状态 2 ))
[Input State]                        [Output State]
                                    (accepting: true)

2.3 字符串纸带匹配模型 (Tape & Cursors)

在自动机运行跟踪中，输入字符串被抽象为一条字符纸带，末尾带有显式的结束标记 $（美元符）：

  • 状态游标（State Cursor）：指向当前停留的自动机节点；
  • 字符游标（Tape Cursor）：指向输入字符串的当前读取位置。

匹配执行流程演练：输入 "A$"

  1. 初始时刻：状态游标位于状态 1，字符游标指向 'A'。
  2. 字符消耗：状态 1 仅有一条出边，要求消耗字符 'A'。检查当前字符恰好是 'A'，条件满足！消耗该字符，字符游标前进指向 $，状态游标前进跃迁到状态 2。
  3. 结束判决：字符游标已到达字符串末尾 $，此时检查状态游标停留在状态 2。状态 2 的 accepting === true，判定匹配成功，接受该字符串！
  • 反例：如果输入是 "B$"，在状态 1 无法找到匹配 'B' 的出边，状态机死机卡住，判定匹配失败。

2.4 封装抽象：NFA 类与工厂函数实现

2.5 NFA 容器类的设计

我们需要一个专门的 NFA 类来包装整个片段。它对外暴露统一的输入输出接口：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class NFA {
  inState: State;
  outState: State;

  constructor(inState: State, outState: State) {
    this.inState = inState;
    this.outState = outState;
  }

  /**
   * 测试输入字符串是否被当前机器接受
   * （底层将委托给图遍历算法，后文将深入展开）
   */
  test(string: string): boolean {
    return this.inState.test(string);
  }
}

test 函数的四大核心职责

如果我们要写一个完整的 test(string)，它在内部必须承担以下四项职责：

1
2
3
4
5
6
7
8
9
10
11
       输入字符串: " a b c "
             │
             ▼
┌───────────────────────────────────────────────┐
│              test(string) 引擎                │
│                                               │
│  1. 游标控制: 逐字读取字符 (Cursor)             │
│  2. ε-闭包扩展: 遇到 ε 边立刻"瞬移"扩散 (Closure)│
│  3. 转移派发: 查找当前状态集合的 transitions    │
│  4. 终态裁决: 字符串读完时，是否停在 accepting?  │
└───────────────────────────────────────────────┘

职责 1：输入流游标推进（Input Stream Cursor）

  • 职责：它维护一个指针，指向当前正在匹配的字符（如 index 0, 1, 2...）。
  • 规则：只有当走过一条真实的字符边（比如 'a'）时，输入游标才往后移动一位；如果是 $\epsilon$ 边，游标原地不动。

职责 2：$\epsilon$-闭包展开（Epsilon-Closure 瞬移扩展）—— 最关键的调度逻辑！

  • 自动机处于某个状态时，只要这个状态身上有 ε 转移，就意味着不需要任何字符就可以到达下一个状态。
  • test 必须在每读入一个字符之前和之后，主动向外探测：“顺着 ε 边我还能免费到达哪些状态？”
  • 这一步叫做计算 $\epsilon$-闭包。比如在 concatenation 里，一旦到达 nfa1.outState，test 就会借助闭包算法自动把它扩散到 nfa2.inState。

职责 3：非确定性多分支派发（Nondeterministic Dispatching）

  • 因为是 NFA（非确定性有限状态机），对于同一个输入字符（例如 'a'），可能会有多条边都可以走，或者同时既可以走字符边也可以走 ε 边。
  • test 必须做出决策：
    • 策略 A（深度优先 / 回溯 DFS）：先选一条路走到底，如果撞墙死掉了，回溯退回来走另一条路（传统 PCRE 正则引擎做法）。
    • 策略 B（广度优先 / 集合并行 BFS，即 Thompson VM）：维护一个“当前活跃状态的集合 Set<State>”，遇到分支时让分身同时存在于多个状态中，并行向前推进（Go/Rust 等现代正则引擎做法）。

职责 4：停机与接受判定（Halting & Acceptance）

  • 当输入字符串的所有字符被消耗完毕（EOF）时：
  • test 检查当前停留在哪些状态上；
  • 如果这些状态中有至少一个状态标记了 accepting === true，则判定成功，返回 true；
  • 否则判定失败，返回 false。

架构解耦之美：数据与逻辑彻底分离

之所以要把它们拆开，是因为这种架构具备极高的工业美感：

模块 角色 关注点
char, concatenation, union, rep 图构建器（Graph Builder） 只关注拓扑关系（谁和谁相连，入口是哪，出口是哪）。不管字符串长什么样。
test(string) 图遍历求值器（Evaluator / VM） 只关注运行规则（状态搜索、闭包计算、分支推进、匹配结果）。不管图是怎么拼出来的。

2.6 单字符机工厂函数：char(symbol)

封装一个简明、通用的构造工厂，生成任意单字符的 NFA 片段：

1
2
3
4
5
6
7
8
9
function char(symbol: string): NFA {
  const inState = new State({ accepting: false });
  const outState = new State({ accepting: true });

  // 连接单字符转移边
  inState.addTransitionForSymbol(symbol, outState);

  return new NFA(inState, outState);
}

3 空串机工厂函数：epsilon()

利用特殊的 EPSILON 标记复用转移逻辑：

1
2
3
4
5
6
7
8
9
10
11
const EPSILON = 'ε';

function epsilon(): NFA {
  const inState = new State({ accepting: false });
  const outState = new State({ accepting: true });

  // 连接空转移边
  inState.addTransitionForSymbol(EPSILON, outState);

  return new NFA(inState, outState);
}

基石地位：单字符机与空串机是整个正则表达式理论中唯二的原子级基本构建块。正则表达式中的其余一切高阶语法（连接、选择、闭包、字符集等），全部是基于这两个原子组合嵌套出来的。
不变量至上：坚持“单入单出”设计原则，使我们无需关心黑盒内部结构即可实现任意复杂度的模块化组合。

4. 状态机结构与连接机制

在正则表达式的全部五大基础机器中，连接模式（Concatenation Pattern）是第一个由基础原子拼装出的复合机器。

  • 语义含义：表示“模式 A 紧随模式 B”（$A \text{ followed by } B$），在正则表达式中直接书写为顺序排列，例如 /AB/。
  • 匹配规则：该机器仅接受由“能够被机器 A 接受的前缀”加上“能够被机器 B 接受的后缀”拼接而成的完整字符串。
  • 抽象普适性：虽然我们常拿字符 A 和 B 举例，但连接模式中的 $A$ 和 $B$ 可以是任意复杂的子机器（例如：a+[0-9]* 本质上是一个重复子机与字符集子机的连接）。连接模式不需要知道内部细节，它将子机器视作黑盒。

4.1 构造拓扑图

如何将两个独立的 NFA 串联在一起？核心秘诀正是 $\epsilon$-空转移（Epsilon Transition）。

1
2
3
4
5
6
              [ 子机器 A (黑盒) ]                              [ 子机器 B (黑盒) ]
         ┌───────────────────────────┐                    ┌───────────────────────────┐
( S0 ) ──┤                           ├── ( S1 ) ─── ε ──> ( S2 ) ──┤                           ├── (( S3 ))
(输入)   └───────────────────────────┘                     └───────────────────────────┘   (接受)
                                      [原接受态:                  [新输入态]
                                       降级为普通态]

4.2 维护架构不变量（关键细节）

为了确保整个复合机器依然符合“唯一输入、唯一输出”的架构铁律，当用 $\epsilon$ 连接 $A$ 的出口和 $B$ 的入口时，必须执行一个至关重要的操作：

  • 重置第一台机器的终止标记：必须将子机器 $A$ 的输出状态的 accepting 显式重置为 false！
  • 此时，整台复合机器唯一的入口是 $A$ 的输入态，唯一的出口是 $B$ 的接受态。

4.3 为什么需要 4 个状态而不是 3 个？

可以简单理解为，通过空状态机消除了，两个状态机之间的状态引用，相当于一次克隆。

如果让你拿笔在纸上画正则表达式 /AB/ 的状态机，任何一个正常人都会画出 3 个状态：
$$S_0 \xrightarrow{\text{ A }} S_1 \xrightarrow{\text{ B }} S_2$$
这没有任何毛病，在结果上也完全正确。

那为什么汤普森（Ken Thompson）和编译原理教材偏偏要多造一个状态，画成 4 个状态呢？
$$S_0 \xrightarrow{\text{ A }} S_1 \xrightarrow{\quad \epsilon \quad} S_2 \xrightarrow{\text{ B }} S_3$$

这背后的根本原因，不是理论不行，而是“手画图”与“写通用代码算法”之间的巨大鸿沟。

我们用代码实现的视角，来彻底拆解为什么必须用 4 个状态 + $\epsilon$ 边：

4.3.1 看一下函数的入参：你在连接的是两个“黑盒子”

请看你写的代码函数签名：

1
function concatPair(first: NFA, second: NFA): NFA

在这个函数被调用的时候，请问你作为这个函数的作者，你知道 first 和 second 到底长什么样吗？

你完全不知道！

  • 它可能是两个单字符机器（a 和 b）；
  • 但它更有可能是极其复杂的两个子机器：比如 first 是 (x|y)*，second 是 (p|q)+！
1
2
3
4
[ first 机器: 可能是包含20个状态的复杂迷宫 ]        [ second 机器: 也是个庞大迷宫 ]
         ┌───────────────────────────┐                 ┌───────────────────────────┐
inState ─┤                           ├─ outState       inState ─┤                           ├─ outState
         └───────────────────────────┘                 └───────────────────────────┘

此时，你要把这两个机器按顺序串起来：

4.3.2 方案 A（汤普森的做法：4个状态，拉一条 $\epsilon$ 边）

你只需要写一行极其优雅、绝对不会出错的代码：

1
first.outState.addTransitionForSymbol(EPSILON, second.inState);

不管里面有多复杂，两个机器的内部丝毫未动，你只是在它们之间搭了一座桥。
这个操作的耗时是严格的 $O(1)$，并且绝对不会破坏子机器内部原有的逻辑。

4.3.3（强行做成 3 个状态：合并节点）

如果你坚持要让连接处“只保留 1 个状态”，意味着你必须把 first.outState 和 second.inState 融合成同一个对象！

在内存图结构中，把两个已有的节点融合成一个节点，是一场极其痛苦的“开颅手术”：

  1. 指针重定向：原来整张图里所有指向 second.inState 的有向边，你必须全部找出来，把它们的指针改指向 first.outState；
  2. 状态合并：原来 second.inState 身上的所有出边，你必须全部复制挪动到 first.outState 上；
  3. 销毁旧节点：从内存中把 second.inState 删掉。

这不仅要把算法复杂度从 $O(1)$ 拖慢到遍历整张图的 $O(V + E)$，而且极容易写出内存引用错乱的 Bug！

4.3.4 致命风险：直接合并节点会“污染”子机器内部逻辑

如果你觉得“节点合并虽然麻烦，但我硬写代码也能做”，那看下面这个逻辑灾难：

假设我们要连接的是 first = a，和 second = (b*)（即匹配 /ab*/）：

  • 机器 second（即 b*）是一个循环机器，它的内部有这样一条逻辑：**每读完一个 b，就有一条回环边跳回自己的入口 second.inState**。

如果你强行把 first.outState 和 second.inState **融合成同一个状态 $S_{\text{middle}}$**：

1
2
3
              ┌───────── b ─────────┐
              ▼                     │ (循环回环)
( S0 ) ──a──> ( S_middle ) ─────────┘

灾难发生了！
现在这个 $S_{\text{middle}}$ 既是第一台机器的出口，又是第二台机器的入口。
机器二的回环边指回了 $S_{\text{middle}}$，两台机器的内部边界彻底被击穿了！在某些更复杂的嵌套（比如多层闭包、多层或运算）中，这种破坏边界的合并会导致系统意外地在不该循环的地方循环，彻底破坏原有的正则语义！

而如果用 $\epsilon$ 边连接：
$$A_{out} \xrightarrow{\quad \epsilon \quad} B_{in}$$
两台机器井水不犯河水。$B$ 内部怎么循环都只在 $B_{in}$ 这一侧打转，绝对不会把脏数据或者控制流回退到 $A$ 的底盘里！

4.3.5 编译器的设计哲学：分阶段治之（Separation of Concerns）

看到这里你可能会问：“难道为了算法好写，我们就容忍状态机里留着这么多冗余的 4 状态和 $\epsilon$ 边吗？”

汤普森和所有编译器设计大师的回答是：

“在构造期（NFA），我们追求极致的通用、简洁与无 Bug；在优化期（DFA），我们再用数学算法把多余的边狠狠砍掉！”

现代编译器的标准流水线是分工极其明确的：

1
2
3
4
5
6
7
8
9
[步骤 1: AST -> NFA]
采用最无脑、最规范的汤普森构造法（拉一条 ε 边）。
状态多没关系、有 ε 边没关系，保证 100% 模块化不出错！
         │
         ▼
[步骤 2: NFA -> DFA (子集构造法)]
在这个阶段，编译器会运行 ε-闭包算法（Epsilon Closure）。
它会自动识别出：从 S1 到 S2 既然只是一个无需消耗字符的 ε 边，
算法在这一步会自动把它们无缝压缩压成 1 个状态！

4.4 链接状态机实现的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
export function concatenation(nfa1: NFA, nfa2: NFA): NFA {
    nfa1.outState.accepting = false;
    nfa2.outState.accepting = true;

    nfa1.outState.addTransitionForSymbol(EPSILON, nfa2.inState);
    return new NFA(nfa1.inState, nfa2.outState);
}

export function concat(first: NFA, ...rest: NFA[]): NFA {
    for (const frag of rest) {
        first = concatPair(first, frag);
    }
    return first;
}

5. 并集模式的语义与数学定义

在五大基础构建块中，并集模式（Union Pattern，也称析取 Disjunction）对应正则表达式中的“或运算”（OR），用竖线管道符 | 表示，如 /A|B/。

  • 语义含义：表示“接受模式 A 或者接受模式 B”。只要输入字符串能够被两个分支中的任意一个完整接受，整台复合机器即判定匹配成功。
  • 黑盒普适性：参与并集的两个子机器可以是基础单字符机，也可以是高度复杂的复合模式（如 [0-9]+ | [a-zA-Z]+）。

为了让整台机器能够“二选一”，并且严格维持“唯一输入、唯一输出”的架构不变量，并集模式需要引入两个全新的外界包裹状态：

  • 一个全新的起始状态（$S_{in}$）；
  • 一个全新的接受状态（$S_{out}$）。

5.1 构造拓扑图

1
2
3
4
5
6
7
8
9
               ε               [ 子机器 A (黑盒) ]               ε
        ┌─────────────> ( A.in ) ─── ... ───> ( A.out ) ─────────────┐
        │                                                            │
        │                                                            ▼
 ( S_in )                                                         (( S_out ))
[全新起始态]                                                      [全新接受态]
        │                                                            ▲
        │      ε               [ 子机器 B (黑盒) ]               ε   │
        └─────────────> ( B.in ) ─── ... ───> ( B.out ) ─────────────┘

5.2 构造四部曲

  1. 分叉连接（Fan-out）：从全新的 $S_{in}$ 向子机器 $A$ 的入口与子机器 $B$ 的入口分别拉出一条 $\epsilon$-转移边。
  2. 汇聚连接（Fan-in）：从子机器 $A$ 的出口与子机器 $B$ 的出口向全新的 $S_{out}$ 分别拉出一条 $\epsilon$-转移边。
  3. 状态降级：必须显式重置两个子机器的原接受态：A.out.accepting = false; B.out.accepting = false;。
  4. 统一出口：将全新的 $S_{out}$ 设为唯一的接受状态（accepting = true）。

5.3 非确定性（Non-determinism）的执行与性能探讨

5.3.1 尝试匹配 "A$" 的执行轨迹

在起始状态 $S_{in}$，机器有两个 $\epsilon$-分支可以选择：

  • 单线程深度优先（DFS / 回溯视角）：

    1. 假设系统先盲目走入下方的 $B$ 分支：通过 $\epsilon$ 瞬移到 $B.in$。
    2. 进入子机器 $B$，要求消耗字符 'B'。但当前纸带字符是 'A'，路断了（Dead End）！
    3. 回滚回溯：撤销刚才的转移，退回分叉点 $S_{in}$，尝试走上方的 $A$ 分支。
    4. 顺着 $\epsilon$ 瞬移到 $A.in$，成功消耗字符 'A' 到达 $A.out$。
    5. 顺着 $\epsilon$ 汇聚到全局接受状态 $S_{out}$，纸带到达 $，匹配成功！

  • 多线程并行探索（NFA 状态集合视角）：
    在 $S_{in}$ 处遇到两条 $\epsilon$ 边，系统分裂为两个并发线程（或将状态放入集合 {A.in, B.in}）。当下层分支遇到字符不匹配时，自动消亡淘汰；上层分支顺利存活并最终抵达终点。

5.3.2 为什么 NFA 往往要转化为 DFA？

直接遍历 NFA 图在遇到死胡同时需要尝试不同分支。如果状态分支极其深邃复杂，单纯在 NFA 上回溯搜索会造成严重的性能浪费。
因此在工业界编译器中，我们先借助 $\epsilon$-NFA 的超强灵活性拼装出结构，随后再通过算法将其统一确定化为 DFA（消除所有 $\epsilon$ 边和多分支，实现无回溯的 $O(n)$ 高速执行）。

5.4 二元并集工厂：orPair(first, second)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function orPair(first: NFA, second: NFA): NFA {
  // 1. 创建全新的外层单入、单出节点
  const inState = new State({ accepting: false });
  const outState = new State({ accepting: true });

  // 2. 维护不变量：重置两个子机器的原接受态
  first.outState.accepting = false;
  second.outState.accepting = false;

  // 3. 入口分叉：从新入口通过 ε 边瞬移到两个子机器的入口
  inState.addTransitionForSymbol(EPSILON, first.inState);
  inState.addTransitionForSymbol(EPSILON, second.inState);

  // 4. 出口汇聚：从两个子机器的原出口通过 ε 边汇聚到新接受态
  first.outState.addTransitionForSymbol(EPSILON, outState);
  second.outState.addTransitionForSymbol(EPSILON, outState);

  return new NFA(inState, outState);
}

5.5 多元并集工厂：or(...fragments)

支持任意多个选择分支（如 A | B | C）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function or(...fragments: NFA[]): NFA {
  if (fragments.length === 0) {
    return epsilon();
  }

  // 递归或迭代拼装成嵌套的二元并集树
  return fragments.reduce((acc, current) => orPair(acc, current));
}

// 构建匹配 /a|b|c/ 的 NFA
const abcOrMachine = or(char('a'), char('b'), char('c'));

abcOrMachine.test('a'); // true
abcOrMachine.test('b'); // true
abcOrMachine.test('c'); // true
abcOrMachine.test('ab'); // false
abcOrMachine.test('d'); // false

6. 克莱恩闭包的语义与历史渊源

在五大基础构建块中，克莱恩闭包（Kleene Closure / Kleene Star）是最后一个复合机器，也是正则表达式中最核心的重复算子。

  • 历史命名：以正则表达式与正则语言的发明者——数学家斯蒂芬·克莱恩（Stephen Kleene）命名。
  • 语义定义：表示“将某个模式重复零次或多次”（$0 \text{ or more times}$）。在正则表达式中用星号 * 表示，如 /A*/。
  • 接受集合：对于 /A*/，合法字符串包括：空串 ""、单个 "A"、两个 "AA"、三个 "AAA" 等无穷多个可能。
  • 黑盒普适性：闭包算子可以作用于任意复杂的子机器上（例如：(a|b)* 代表由 a 或 b 构成的任意组合）。

如何用状态机同时表达“跳过（0次）”和“循环重入（多次）”？我们需要引入一对新的起始与接受状态，并布设 4 条关键的 $\epsilon$-转移边。

6.1 构造拓扑图

1
2
3
4
5
6
7
8
9
10
11
                   ε (进入子机)                ε (出子机)
              ┌────────────────> ( A.in ) ────┐
              │                               │
              │               [ 子机器 A ]    │
 ( S_in ) ────┤                  (黑盒)       ├───> (( S_out ))
[全新起始态]  │                               │    [全新接受态]
              │        ε (回环重入: 多次重复)  │
              │   ┌───────────────────────────┘
              │   │
              ▼   ▼ ε (旁路跳过: 0次重复)
              └─────────────────────────────────────►

6.2 四条 $\epsilon$-边的分工使命

  1. 旁路边（Bypass: 零次重复）：
    $$S_{in} \xrightarrow{\epsilon} S_{out}$$
    允许整个子机器被完全绕过。即使输入为空字符串，也能瞬间抵达终点，满足“重复 0 次”的定义。
  2. 进入边（Enter）：
    $$S_{in} \xrightarrow{\epsilon} A.in$$
    引导机器走入实际子模块进行至少一次的字符消耗。
  3. 出机边（Exit）：
    $$A.out \xrightarrow{\epsilon} S_{out}$$
    完成一次或多次循环后，从子机器出口安全引导到全局接受态。
  4. 回环边（Loopback: 多次重复）：
    $$A.out \xrightarrow{\epsilon} A.in \quad (\text{或从 } S_{out} \xrightarrow{\epsilon} A.in)$$
    每当子机器完成一轮匹配到达出口时，提供一条无需消耗字符的“传送门”将控制流瞬间拉回到子机器入口，为下一轮循环匹配做好准备。

[!NOTE]
关于回环边起点位置的说明：
在理论实现中，回环边可以从 $A.out$ 直连 $A.in$，也可以从 $S_{out}$ 连回 $A.in$。二者在语义上完全等价。本课程采用标准的原始规范版本（直接连接 $A.out \xrightarrow{\epsilon} A.in$ 或 $S_{out} \xrightarrow{\epsilon} A.in$）。

6.3 双游标纸带执行演练

场景 A：匹配空字符串 ""（即 "$"）

  1. 状态机在 $S_{in}$，纸带游标指向 $。
  2. 走最下方的旁路边：$S_{in} \xrightarrow{\epsilon} S_{out}$，直接进入终点。
  3. 纸带在 $，状态在接受态，判定成功（匹配 0 次）！

场景 B：匹配字符串 "AA$"（即重复 2 次）

  1. 状态机在 $S_{in}$，纸带指向第 1 个 'A'。
  2. 走进入边：$S_{in} \xrightarrow{\epsilon} A.in$。
  3. 消耗第 1 个字符 'A'，到达 $A.out$，纸带指向第 2 个 'A'。
  4. 顺着回环边：$A.out \xrightarrow{\epsilon} A.in$，重新回到子机入口。
  5. 消耗第 2 个字符 'A'，再次到达 $A.out$，纸带指向 $。
  6. 顺着出机边：$A.out \xrightarrow{\epsilon} S_{out}$，到达全局终点。
  7. 纸带在 $，状态在接受态，判定成功（循环匹配 2 次）！

6.4 代码工程实现

闭包工厂函数：rep(fragment) / kleene(fragment)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
function rep(fragment: NFA): NFA {
  // 1. 创建全新的单入、单出节点
  const inState = new State({ accepting: false });
  const outState = new State({ accepting: true });

  // 2. 重置子机器的原接受状态
  fragment.outState.accepting = false;

  // 3. 边1: 旁路跳过（重复 0 次）
  inState.addTransitionForSymbol(EPSILON, outState);

  // 4. 边2: 进入子机器（进行匹配）
  inState.addTransitionForSymbol(EPSILON, fragment.inState);

  // 5. 边3: 退出子机器到接受态
  fragment.outState.addTransitionForSymbol(EPSILON, outState);

  // 6. 边4: 回环重入（支持重复多次）
  // 方式一：从 outState 回环到 fragment.inState
  // 也可以从 fragment.outState 回环到 fragment.inState
  outState.addTransitionForSymbol(EPSILON, fragment.inState);

  return new NFA(inState, outState);
}

// 构建匹配 /a*/ 的 NFA
const aStar = rep(char('a'));

aStar.test('');    // true (0次)
aStar.test('a');   // true (1次)
aStar.test('aaa'); // true (3次)
aStar.test('b');   // false

// 复杂子机器测试：/(a|b)*/
const abStar = rep(or(char('a'), char('b')));
abStar.test('');      // true
abStar.test('a');     // true
abStar.test('b');     // true
abStar.test('abba');  // true
abStar.test('abbac'); // false
打赏
  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
  • Copyrights © 2015-2026 SunZhiqi

此时无声胜有声！

支付宝
微信