DFA 转换表与子集构造算法 (DFA Transition Table: Subset Construction)

1. 为什么需要向 DFA 演进？

在前面两讲中，我们构建了 NFA 以及它的转换表。NFA 最大的优势在于模块化拼装极其简单，但它在运行时面临两大固有缺点：

1. 非确定性（Nondeterminism）：同一字符可能导致多个可选目标状态；
2. $\epsilon$ 转移存在：允许状态机在不消耗字符的情况下“瞬移”。

为了彻底消除不确定性与空转移，使状态机在任何时刻面对任何字符都具有唯一确定的下一步跳跃（$O(1)$ 速度），我们必须将 NFA 转换为 DFA（确定性有限状态机）。

2. DFA 转换表的核心特征

与 NFA 转换表相比，DFA 转换表有三个根本性的结构转变：

1
2
3
4
5
6
7

       ┌────────── 字母表字符列 (Alphabet Σ) ──────────┐
       │                                               │
DFA 状态│               'a'             'b'             │   （无 ε* 列！）
───────┼───────────────────────────────────────────────┤
> 1,2,5│              "3,4"           "6,4"            │   <-- 单一状态值，非数组！
* 3,4  │                -               -              │   <-- 接受状态
* 6,4  │                -               -              │   <-- 接受状态（允许多个接受态！）

1. 没有 $\epsilon$ 列：DFA 语法严格禁止空转移，所有隐式跳跃必须在转换前全部被“吸收”消除；
2. 单元格内容是单一状态：对于任意状态和输入字符，目标至多是一个确定的状态标签，不再是状态数组；
3. 允许多个接受状态：NFA 依靠不变量始终保持单一出口，但在 DFA 中，任何包含了原 NFA 接受态的组合状态，全都是合法的 DFA 接受态！

3. 子集构造法（Subset Construction Algorithm）

将 NFA 转化为等价 DFA 的经典算法被称为子集构造法（Subset Construction / 幂集构造法 Powerset Construction）。

核心哲学：
DFA 中的每一个单一状态，在本质上都是原 NFA 中一组可能同时处于活跃状态的子集集合（Subset of NFA States）！

3.1 步骤一：确定 DFA 的初始状态

DFA 必须有一个唯一的起点，它应该对应 NFA 的什么状态？

• NFA 的起点是状态 $1$，但在没有输入任何字符之前，状态机可以通过 $\epsilon$ 边自由滑行到状态 $2$ 和 $5$。
• 因此，在游戏还没开始前，系统其实同时处于 $1$、$2$、$5$ 三个状态的叠加态中！

DFA 起始状态的形式定义：
DFA 的起始状态，正是 NFA 起始状态的 $\epsilon$-闭包：

$$S_{0}^{DFA} = \epsilon\text{-closure}(S_{0}^{NFA})$$

对于 /a|b/，NFA 的初始态为 $1$，其闭包为 ${1, 2, 5}$。
我们将这个子集打包装箱，命名为一个全新的 DFA 状态：**"1,2,5"**（标记为起始状态 > 1,2,5）。

3.2 步骤二：计算字符转移的“之字形法则”（The Zig-Zag Formula）

假设 DFA 当前处于某个复合状态 $U = {s_1, s_2, \dots, s_k}$，当读入字符 $c$ 时，应该跃迁到哪个新的 DFA 状态？

我们需要分两步完成：

1. 收集字符转移：从子集 $U$ 中的每一个 NFA 状态出发，找出所有在字符 $c$ 下能够到达的目标状态；
2. 吸收后续 $\epsilon$ 转移：对上述所有目标状态求一次 $\epsilon$-闭包，确保把下游所有的空转移全部吸收干净！

DFA 转移计算公式：

$$\delta_{DFA}(U, c) = \epsilon\text{-closure}\left( \bigcup_{s \in U} \delta_{NFA}(s, c) \right)$$

在 NFA 转换表上，这个操作就像一个“之字形折线（Zig-Zag）”：

• 先横向查字符列的目标；
• 再横向拉到最右侧的 $\epsilon^*$ 列取闭包！

1

[当前 DFA 状态中的 NFA 节点] ──(查字符列)──> [目标 NFA 节点] ──(查 ε* 列)──> [最终合并的新状态]

3.3 步骤三：递归探索新状态（广度优先搜索队列）

每当上述计算产生了一个之前从未见过的状态组合（如 "3,4"），我们就必须把它作为一个新的行登记到 DFA 转换表中，并加入待处理队列，重复计算它在所有字符下的转移。直到没有新状态产生为止。

3.4 步骤四：判定 DFA 接受状态

接受状态判定准则：
一个 DFA 复合状态 $U$ 是接受状态，当且仅当它包含原 NFA 的接受状态：

$$U \in F_{DFA} \iff S_{accept}^{NFA} \in U$$

从 NFA（非确定性有限状态机） 转化为 DFA（确定性有限状态机） 的过程，在编译原理中被称为 “子集构造法（Subset Construction / 幂集构造）”。

这套算法的核心思想只有一句话：

既然 NFA 会因为 $\epsilon$ 边和多选一分支产生“分身（叠加态）”，那我们就把所有可能同时处于活跃的“分身们”打包塞进一个大圈里，把这个“大圈”当成一个全新的单一 DFA 状态！

我们以你刚刚写的正则表达式 /a|b/ 为例，用逐帧图文演播的方式，带你走完 DFA 诞生的全过程。

初始蓝图：NFA 原始状态图与转换表

在诞生 DFA 之前，我们手头有这张由 6 个节点构成的 NFA 图：

1
2
3
4
5
6

                  ε              'a'              ε
           ┌───────────> ( 2 ) ───────> ( 3 ) ───────────┐
           │                                             ▼
  > ( 1 ) ─┤                                           * (( 4 ))
[起点]     │      ε              'b'              ε     [终点]
           └───────────> ( 5 ) ───────> ( 6 ) ───────────┘

对应查表字典（nfaTable）：

• 1 的 $\epsilon$ 闭包 $\rightarrow$ [1, 2, 5]
• 2 吃了 'a' 变 **3**（3 的 $\epsilon$ 闭包是 **[3, 4]**）
• 5 吃了 'b' 变 **6**（6 的 $\epsilon$ 闭包是 **[6, 4]**）
• 4 是接受态。

1
2
3
4
5
6
7
8

Map(6) {
  '1' => Map(1) { 'ε' => [ '1', '2', '5' ] },
  '2' => Map(2) { 'a' => [ '3' ], 'ε' => [ '2' ] },
  '3' => Map(1) { 'ε' => [ '3', '4' ] },
  '4' => Map(1) { 'ε' => [ '4' ] },
  '5' => Map(2) { 'b' => [ '6' ], 'ε' => [ '5' ] },
  '6' => Map(1) { 'ε' => [ '6', '4' ] }
}

第一帧：第 1 个 DFA 超级节点的诞生（游戏开局）

• 提问：比赛还没开始，字符一个都没输入，系统可能停在哪些节点？
• 追踪：
  从起点 1 出发，因为有无需消耗字符的 $\epsilon$ 滑行绿道，系统在第 0 秒就已经同时存在于 1、2、5 三个节点上了！
• 操作：
  我们拿一个大麻袋，把 {1, 2, 5} 打包成一个全新的超级节点，命名为 状态 A（即 "1,2,5"）。它就是 DFA 的起始状态！

1
2
3
4
5
6
7

┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐
   DFA 起始节点 A: "1,2,5"
│                         │
    ( 1 ) ──ε──> ( 2 )
│     │                   │
      └──ε──> ( 5 )
└ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘

第二帧：超级节点 A 探索字符 'a'（之字形跳跃）

现在，假设外界喂给超级节点 A 一个字符 **'a'**：

1. 麻袋里的每个人各自响应：
   • 节点 1：“我没有 'a' 的路”；
   • 节点 5：“我只有 'b'，不吃 'a'”；
   • 节点 2 站出来：“我有 'a'！吃了 'a'，我跳到了 节点 3！”
2. 吸收目的地后续的 $\epsilon$ 边（闭包展开）：
   • 刚落到节点 3，发现节点 3 连着一条 $\epsilon$ 边通往节点 4！
   • 于是瞬间滑翔到了节点 4。
   • 吃完 'a' 后的最终落点：**[3, 4]**！
3. 诞生新超级节点 B：
   • 我们拿第二个麻袋，把 {3, 4} 打包成 状态 B（即 "3,4"）；
   • 并拉出一条确定的实线转移边：**A ──['a']──> B**！

1
2
3
4
5
6
7
8

┌ ─ ─ ─ ─ ─ ─ ─ ┐                       ┌ ─ ─ ─ ─ ─ ─ ─ ┐
  超级节点 A                              超级节点 B
│    "1,2,5"    │                       │     "3,4"     │
     ( 2 ) ────────────── ['a'] ──────────────> ( 3 )   │
│               │                       │         │     │
└ ─ ─ ─ ─ ─ ─ ─ ┘                                 ▼ ε
                                        │       (( 4 )) │
                                        └ ─ ─ ─ ─ ─ ─ ─ ┘

第三帧：超级节点 A 探索字符 'b'

现在，假设外界喂给超级节点 A 另一个字符 **'b'**：

1. 麻袋里的每个人各自响应：
   • 节点 1、2 不吃 'b'；
   • 节点 5 站出来：“吃了 'b'，我跳到了 节点 6！”
2. 吸收闭包：
   • 节点 6 顺着 $\epsilon$ 边滑翔到了节点 4；
   • 吃完 'b' 后的最终落点：**[6, 4]**！
3. 诞生新超级节点 C：
   • 我们拿第三个麻袋，把 {6, 4} 打包成 状态 C（即 "6,4"）；
   • 拉出实线边：**A ──['b']──> C**！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

┌ ─ ─ ─ ─ ─ ─ ─ ┐
  超级节点 B
│     "3,4"     │
└ ─ ─ ─ ─ ─ ─ ─ ┘
        ▲
        │ ['a']
        │
┌ ─ ─ ─ ─ ─ ─ ─ ┐
  超级节点 A
│    "1,2,5"    │
└ ─ ─ ─ ─ ─ ─ ─ ┘
        │
        │ ['b']
        ▼
┌ ─ ─ ─ ─ ─ ─ ─ ┐
  超级节点 C
│     "6,4"     │
└ ─ ─ ─ ─ ─ ─ ─ ┘

第四帧：检查新节点 B 和 C 的出路（队列收敛）

现在队列里有刚发现的 节点 B ("3,4") 和 **节点 C ("6,4")**：

• 问节点 B：“你里面的 3 和 4，还能吃 'a' 或 'b' 吗？”
  • 查表：节点 3 和 4 都是终点段，没有任何字符出边。
  • $\rightarrow$ 节点 B 没有任何出边，填空。
• 问节点 C：“你里面的 6 和 4，还能吃 'a' 或 'b' 吗？”
  • 查表：节点 6 和 4 同样没有任何字符出边。
  • $\rightarrow$ 节点 C 没有任何出边，填空。

没有产生任何新的超级节点，待处理队列变空，主循环结束！

第五帧：插上终点红旗（确定接受态）

现在整张图骨架已经成型，谁是接受状态（终点）？

• 规则：原 NFA 的最终接受态是 4 号节点；
• 检查每一个超级节点的麻袋：
  • **节点 A ("1,2,5")**：没有 4 $\rightarrow$ 普通起点；
  • 节点 B ("3,4")：里面包含 4！ $\rightarrow$ 插上红旗，成为接受态！
  • 节点 C ("6,4")：里面包含 4！ $\rightarrow$ 插上红旗，成为接受态！

终极对比：NFA 与 DFA 的蜕变

蜕变前：NFA（6 个节点，充斥着混乱的虚线 $\epsilon$ 边）

1
2
3
4
5
6

                ε              'a'              ε
         ┌───────────> ( 2 ) ───────> ( 3 ) ───────────┐
         │                                             ▼
> ( 1 ) ─┤                                           * (( 4 ))
         │      ε              'b'              ε     
         └───────────> ( 5 ) ───────> ( 6 ) ───────────┘

蜕变后：DFA（只有 3 个确定节点，0 条 $\epsilon$ 边，单线直达）

1
2
3
4
5

          ┌─────── 'a' ───────> * (( 3,4 ))
          │
> ( 1,2,5 )
          │
          └─────── 'b' ───────> * (( 6,4 ))

这就是 DFA 产生的完整闭环！它通过“闭包打包、单步吃字、吸收滑行、确定连线”，把原本充满不确定性、需要到处回溯试探的图，重构为了一个没有任何歧义的高速公路网！

最终生成的 DFA 转换表

5. 代码工程实现 (TypeScript)

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

class DFA {
    nfaTable: Map<string, Map<string, string[]>>;

    constructor(public nfa: NFA) {
        this.nfa = nfa;
        this.nfaTable = nfa.getTransitionTable();
    }

    startId = '1'

    getAlphabet(nfaTable: Map<string, Map<string, string[]>>): string[] {
        const alphabet = new Set<string>();
        for (const row of nfaTable.values()) {
            for (const symbol of row.keys()) {
                if (symbol !== 'ε') {
                    alphabet.add(symbol);
                }
            }
        }
        return Array.from(alphabet).sort();
    }

    /**
     * 将 NFA 状态 ID 集合规范化为唯一的 DFA 状态标识字符串（如 ['2', '1', '5'] -> '1,2,5'）
     */
    private formatStateKey(ids: Iterable<string>): string {
        return Array.from(ids).sort((a, b) => Number(a) - Number(b)).join(',');
    }

    getTransitionTable(): Map<string, Map<string, string>> {
        const startClosure = this.nfaTable.get(this.startId)!.get('ε')!;
        const startStateKey = this.formatStateKey(startClosure);

        // 使用队列做 BFS 搜索，同时用 visited 集合在入队前剪枝
        const queue: string[][] = [startClosure];
        const visited = new Set<string>([startStateKey]);
        const dfaTable: Map<string, Map<string, string>> = new Map();

        while (queue.length > 0) {
            const currentIds = queue.shift()!;
            const currentStateKey = this.formatStateKey(currentIds);

            // 记录当前复合状态接收各字符后转移到的 NFA 状态集合
            const symbolTransitions = new Map<string, Set<string>>();

            for (const nfaId of currentIds) {
                const nfaRow = this.nfaTable.get(nfaId);
                if (!nfaRow) continue;

                for (const [symbol, nextIds] of nfaRow.entries()) {
                    if (symbol === 'ε') continue;

                    let targetSet = symbolTransitions.get(symbol);
                    if (!targetSet) {
                        targetSet = new Set<string>();
                        symbolTransitions.set(symbol, targetSet);
                    }

                    for (const nextId of nextIds) {
                        const closure = this.nfaTable.get(nextId)?.get('ε');
                        if (closure) {
                            for (const cid of closure) {
                                targetSet.add(cid);
                            }
                        }
                    }
                }
            }

            // 单次遍历完成：1. 填充 DFA 转移表  2. 发现新状态入队
            const row: Map<string, string> = new Map();

            for (const [symbol, targetSet] of symbolTransitions.entries()) {
                const targetKey = this.formatStateKey(targetSet);
                row.set(symbol, targetKey);

                // 入队前剪枝：仅当该 DFA 复合状态尚未发现过时才推入队列，避免重复排队与出队
                if (!visited.has(targetKey)) {
                    visited.add(targetKey);
                    queue.push(Array.from(targetSet));
                }
            }

            dfaTable.set(currentStateKey, row);
        }

        return dfaTable;
    }
}

NFA 接收器与图遍历匹配算法 (NFA Acceptor: Graph Traversal Engine)

1. 架构总览：从“静态电路图”到“动态求值引擎”

上一章节，我们实现了五大基础 NFA 构建块（单字符、空串、连接、并集、闭包）以及针对字符集的工程优化。这些工厂函数的核心任务是“画图纸 / 搭电路”——它们在内存中建立起由 State 对象与转移边构成的静态有向图。

本讲开启了第三模块的核心篇章：如何驱动这台机器去执行真正的字符串匹配校验？

1
2
3
4
5
6
7
8
9
10

┌──────────────────────────────────────────────────────────────┐
│                    静态构建阶段 (Builder)                    │
│   char('a'), concatenation(nfa1, nfa2), or(nfa1, nfa2)...    │
└──────────────────────────────┬───────────────────────────────┘
                               │ 生成静态 NFA 图
                               ▼
┌──────────────────────────────────────────────────────────────┐
│                    动态求值阶段 (Acceptor)                   │
│          nfa.test("abc") ──> 判定该字符串是否被该机器接受        │
└──────────────────────────────────────────────────────────────┘

2. 委托模式：NFA 与 State 的职责划分

在面向对象架构中，NFA 类对外暴露统一的 test(string) 接口，但它自身并不直接执行深度图搜索，而是薄薄地封装了一层委托（Delegation），将匹配工作完全交给它的起始节点 inState：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class NFA {
  constructor(
    public inState: State,
    public outState: State
  ) {}

  /**
   * 判定输入字符串是否被当前 NFA 接受
   * 核心工作委托给唯一入口 inState 的 test 方法
   */
  test(string: string): boolean {
    return this.inState.test(string);
  }
}

为什么可以从 inState 线性委托？

这正是得益于我们贯穿始终的核心架构不变量（Architectural Invariant）：

• 任何合法的 NFA 片段都有且仅有一个明确的入口（inState）；
• 任何合法的 NFA 片段都有且仅有一个全局出口（outState，且标记为 accepting: true）。

因此，匹配逻辑总是且必须从 inState 出发，沿着有向边一路探索。

3. 图遍历匹配算法详解 (DFS / Backtracking)

State.prototype.test(string) 的本质是一个基于深度优先搜索（DFS）与回溯（Backtracking）的有向图可达性判定器。

在每一步递归中，状态机面临两类转移：

1. 符号转移（Symbol Transition）：必须消耗输入流中的当前字符；
2. 空串转移（$\epsilon$-Transition）：不消耗任何输入字符，瞬间自由跳转。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

             ┌───────────────────────────┐
             │   State.prototype.test    │
             │   (string, visited)       │
             └─────────────┬─────────────┘
                           │
            字符串是否为空 (string === "")?
                    /              \
                 [是]              [否]
                  /                  \
        当前是否为接受态?         1. 尝试匹配当前字符 string[0]:
         /          \               有字符边 -> 消耗字符, 递归 test(rest)
      [是]          [否]          2. 尝试走 ε 边 (不消耗字符):
      /                \            有 ε 边 -> 保持原串, 递归 test(string)
返回 true         顺着 ε 边搜索:
                 能否抵达接受态?

3.1 终止条件判定（Base Cases）

情况 A：输入字符串已完全消耗完毕（string.length === 0）

1. 成功终态：如果当前状态恰好是接受状态（this.accepting === true），说明输入字符串完整且精确地导向了终点，**直接返回 true**。
2. 潜伏路径（绝不能轻言放弃！）：如果当前状态还不是接受状态，不能立刻判定失败！
   • 因为当前状态后面可能连接着若干条 $\epsilon$ 边；
   • 这些 $\epsilon$ 边允许状态机在不吃任何字符的情况下继续向前“瞬移”，最终抵达接受状态！
   • 因此，仍需沿着所有 $\epsilon$ 出边继续递归探测。如果其中任意一条路径能抵达接受状态，返回 true；否则返回 false。

情况 B：输入字符串尚未结束（string.length > 0）

当前状态需要分别尝试两条路：

1. 分支一：字符边匹配（消耗字符）
   • 取出首字符 char = string[0]；
   • 查询当前状态是否存在标记为 char 的出边：this.getTransitionsForSymbol(char)；
   • 若存在，则字符被成功消耗，递归调用下一跳状态的 test(string.slice(1))；
   • 只要有任意一个分支递归成功返回 true，整体即刻判定成功（短路返回 true）。
2. 分支二：$\epsilon$ 边瞬移（不消耗字符）
   • 即使当前字符没有匹配的字符边，或者字符边匹配失败，状态机依然可以尝试走 $\epsilon$ 边；
   • 走 $\epsilon$ 边时，输入字符串保持原样（string 不缩短），递归调用下一跳状态的 test(string)；
   • 同样，若有分支返回 true，整体判定成功。

4. 核心陷阱：$\epsilon$-环路与死循环防范

4.1 死循环危机

考虑闭包模式或复合模式（如 /(a*)* / 或存在回环边的结构）：

1
2
3

   ┌────────── ε ──────────┐
   ▼                       │
( S1 ) ──────── ε ───────> ( S2 )

如果图结构中存在由 $\epsilon$ 边构成的环路，且当前处于 string === "" 或走 $\epsilon$ 路径，递归函数将在状态之间无限来回横跳，最终导致调用栈溢出（Maximum call stack size exceeded）！

4.2 访问集防线 (visited: Set<State>)

为了彻底消除死循环，算法引入了一个只针对 $\epsilon$ 转移的访问记录集（Visited Set）：

• 当沿着一条 $\epsilon$ 边前进时，将目标状态登记入 visited 集合；
• 如果在未消耗任何字符的前提下再次回到了 visited 中的某个状态，说明陷入了无意义的 $\epsilon$ 死循环，**直接剪枝返回 false**；
• 关键重置时机：一旦状态机沿着真实的字符边前进并成功消耗了一个字符，输入纸带已经推进一步，这一轮的 visited 集合必须清空重置（因为不同字符位置重新访问同一状态是完全合法且必要的重复！）。

5. 完整代码工程实现

在 State 类与 NFA 类中补充完整的 test 逻辑：

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

export const EPSILON = 'ε';

export class State {
  accepting: boolean;
  transitions: Map<string, State[]>;

  constructor({ accepting = false } = {}) {
    this.accepting = accepting;
    this.transitions = new Map();
  }

  addTransitionForSymbol(symbol: string, state: State): void {
    const list = this.transitions.get(symbol);
    if (list) {
      list.push(state);
    } else {
      this.transitions.set(symbol, [state]);
    }
  }

  getTransitionsForSymbol(symbol: string): State[] {
    return this.transitions.get(symbol) || [];
  }

  /**
   * 图遍历执行器：递归深度优先搜索 + 回溯
   * @param string 当前待匹配的剩余字符串
   * @param visited 仅用于 ε 转移的环路检测集合
   */
  test(string: string, visited: Set<State> = new Set()): boolean {
    // 1. ε 环路死循环检测：若在空跳转下重复踩中已访问状态，直接剪枝
    if (visited.has(this)) {
      return false;
    }
    visited.add(this);

    // 2. 基准情况：字符串已被消耗殆尽
    if (string.length === 0) {
      // 成功终点：停留在接受状态
      if (this.accepting) {
        return true;
      }
      // 虽未在接受态，但尝试通过剩余的 ε 边能否滑向接受态
      for (const nextState of this.getTransitionsForSymbol(EPSILON)) {
        if (nextState.test('', visited)) {
          return true;
        }
      }
      return false;
    }

    // 3. 递归情况：字符串非空
    const symbol = string[0];
    const rest = string.slice(1);

    // 路径 A：匹配当前字符边（消耗 1 个字符）
    // 注意：一旦消耗了字符，新的递归分支使用全新独立的 visited 集！
    const symbolTransitions = this.getTransitionsForSymbol(symbol);
    for (const nextState of symbolTransitions) {
      if (nextState.test(rest, new Set())) {
        return true;
      }
    }

    // 路径 B：尝试 ε 空转移（不消耗字符）
    // 继承当前的 visited 集合，持续监控 ε 环路
    const epsilonTransitions = this.getTransitionsForSymbol(EPSILON);
    for (const nextState of epsilonTransitions) {
      if (nextState.test(string, visited)) {
        return true;
      }
    }

    // 所有可能路径均无法抵达接受态
    return false;
  }
}

6. 双游标执行轨迹演练 (Trace Walkthrough)

案例：以连接机器 /ab/ 匹配 "ab" 为例

机器结构拓扑：

1

(S1) ──['a']──> (S2) ──[ε]──> (S3) ──['b']──> ((S4: accepting))

NFA 转换表与 ε-闭包计算 (NFA Transition Table & ε-Closure)

1. 为什么需要转换表？(From Graph to Matrix)

在上一讲中，我们通过直接在 NFA 状态图上进行递归回溯遍历，实现了一个功能完备的 test 接收器。

然而，在编译器工业实现中，直接在指针图上游走存在重大性能瓶颈：

1. 内存碎片与指针跳转（Pointer Chasing）：图遍历充斥着散乱的堆内存寻址与缓存未命中；
2. 非确定性（Nondeterminism）与 $\epsilon$ 边：导致程序执行流分叉、需要反复维护 visited 集合以防环路死循环；
3. 向 DFA 进化的必经之路：为了将正则引擎彻底加速为确定性的 $O(1)$ 单步跳转，第一步必须将散乱的图模型结构化为统一的转换矩阵（Transition Table）。

2. NFA 转换表的结构剖析 (Anatomy of the NFA Table)

NFA 转换表将状态机的所有拓扑信息浓缩为一张二维网格：

1
2
3
4
5
6
7
8
9
10

       ┌────────── 字母表字符列 (Alphabet Σ) ──────────┐    ┌── 核心闭包列 ──┐
       │                                               │    │                │
状态行  │               'a'             'b'             │    │       ε*       │
───────┼───────────────────────────────────────────────┼────┼────────────────┤
  > 1  │               -                -              │    │   { 1, 2, 5 }  │
    2  │              {3}               -              │    │      { 2 }     │
    3  │               -                -              │    │    { 3, 4 }    │
  * 4  │               -                -              │    │      { 4 }     │
    5  │               -               {6}             │    │      { 5 }     │
    6  │               -                -              │    │    { 6, 4 }    │

表格要素说明：

1. 行表头（Rows - 状态标签）：
   • 包含 NFA 图中的所有状态节点。
   • 每个状态分配一个唯一标签（如数字 1, 2, 3... 或字母）。
   • 特殊标记：
     • > 或 ->：标记机器的初始状态（Start State）（如 > 1）；
     • * 或双圈：标记机器的接受状态（Accepting State）（如 * 4）。
2. 字符列（Columns - 字母表 $\Sigma$）：
   • 包含该正则模式中出现的所有真实字符（例如 /a|b/ 的字符集为 {'a', 'b'}）。
   • 单元格内记录从当前状态读入该字符后所转移到的目标状态集合（因非确定性，可能是 0 个、1 个或多个状态）。
3. 核心扩展列：$\epsilon^$ 列（Epsilon-Closure / 空转移闭包）*：
   • 这是 NFA 转换表中最核心、最重要的列，也是后续消除所有 $\epsilon$ 边并转化为 DFA 的绝对基石。

3. 核心概念：$\epsilon$-闭包（Epsilon Closure, $\epsilon^*$）

3.1 语义与数学定义

类比于克莱恩星号闭包（Kleene Closure, $A^*$ 表示重复 0 次或多次），**$\epsilon$-闭包（记作 $\epsilon^*(S)$）** 表示：

从状态 $S$ 出发，沿着 0 条或多条 $\epsilon$ 转移边所能抵达的所有状态的集合。

$$\epsilon\text{-closure}(S) = { q \in Q \mid S \xrightarrow{\epsilon^*} q }$$

3.2 自反性铁律：必须包含状态本身！

[!IMPORTANT]
任何状态的 $\epsilon$-闭包，第一项永远是它自身！

即：$$S \in \epsilon\text{-closure}(S)$$

原因：消耗“0 个 $\epsilon$ 转移”意味着原地不动。不消耗任何字符留在当前状态，在物理语义上完全等价于存在一条指向自己的隐式 $\epsilon$ 转移。

3.3 闭包计算演示

以状态 $1$ 为例（图见下节）：

1. 首先加入自身：{ 1 }；
2. 状态 $1$ 有两条显式 $\epsilon$ 出边：分别通往状态 $2$ 和状态 $5$；
3. 检查状态 $2$ 和 $5$，它们均没有更深层的 $\epsilon$ 出边；
4. 搜索结束，状态 $1$ 的 $\epsilon$-闭包为：{ 1, 2, 5 }。

4. 经典全流程实战：构建 /a|b/ 的 NFA 转换表

我们以标准的并集模式 /a|b/ 为例，完整走一遍手工与算法建表流程。

4.1 NFA 拓扑图与状态编号

根据 Thompson 构造法，/a|b/ 包含 6 个状态节点：

1
2
3
4
5
6

                  ε              'a'              ε
           ┌───────────> ( 2 ) ───────> ( 3 ) ───────────┐
           │                                             ▼
  > ( 1 ) ─┤                                           * (( 4 ))
[Start]    │      ε              'b'              ε     [Accept]
           └───────────> ( 5 ) ───────> ( 6 ) ───────────┘

4.2 逐行计算状态转移与闭包

状态 1（初始入口 > 1）：

• **读入 'a'**：无任何直接字符边 $\rightarrow$ 填空（或 $\emptyset$）；
• **读入 'b'**：无任何直接字符边 $\rightarrow$ 填空；
• $\epsilon^$ 闭包*：包含自身 $1$，顺着 $\epsilon$ 边可达 $2$ 和 $5$ $\rightarrow$ **{ 1, 2, 5 }**。

状态 2：

• **读入 'a'**：有一条边连向状态 $3$ $\rightarrow$ **{ 3 }**；
• **读入 'b'**：无出边 $\rightarrow$ 填空；
• $\epsilon^$ 闭包*：无 $\epsilon$ 出边，仅含自身 $\rightarrow$ **{ 2 }**。

状态 3：

• **读入 'a' / 'b'**：均无字符出边 $\rightarrow$ 填空；
• $\epsilon^$ 闭包*：自身 $3$，加上顺着 $\epsilon$ 边直达的 $4$ $\rightarrow$ **{ 3, 4 }**。

状态 4（最终接受态 * 4）：

• **读入 'a' / 'b'**：全局出口，无任何字符出边 $\rightarrow$ 填空；
• $\epsilon^$ 闭包*：自身 $4$ $\rightarrow$ **{ 4 }**。

状态 5：

• **读入 'a'**：无出边 $\rightarrow$ 填空；
• **读入 'b'**：有一条边连向状态 $6$ $\rightarrow$ **{ 6 }**；
• $\epsilon^$ 闭包*：自身 $5$ $\rightarrow$ **{ 5 }**。

状态 6：

• **读入 'a' / 'b'**：无字符出边 $\rightarrow$ 填空；
• $\epsilon^$ 闭包*：自身 $6$，加上顺着 $\epsilon$ 边直达的 $4$ $\rightarrow$ **{ 6, 4 }**。

4.3 最终生成的完整 NFA 转换表

5. 代码工程实现 (TypeScript)

5.1 数据结构定义

1
2
3
4
5
6
7
8
9
10
11

export type StateId = number | string;

export interface NFATableRow {
  state: StateId;
  isStart: boolean;
  isAccepting: boolean;
  transitions: Record<string, StateId[]>; // 字符 -> 目标状态数组
  epsilonClosure: StateId[];              // ε* 闭包集合
}

export type NFATable = NFATableRow[];

5.2 计算单个状态的 $\epsilon$-闭包算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

export function getEpsilonClosure(startState: State): Set<State> {
  // 铁律：闭包必定包含状态自身
  const closure = new Set<State>([startState]);
  const stack = [startState];

  while (stack.length > 0) {
    const currentState = stack.pop()!;
    const epsTransitions = currentState.getTransitionsForSymbol(EPSILON);

    // 空过渡节点还可能指向下一个空过渡节点，所以需要递归处理
    for (const targetState of epsTransitions) {
      if (!closure.has(targetState)) {
        closure.add(targetState);
        stack.push(targetState); // 递归深入追踪链式 ε
      }
    }
  }

  return closure;
}

5.3 遍历图生成 NFA 转换表

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

getTransitionTable(): Map<string, Map<string, string[]>> {
    const stateToId: Map<State, number> = new Map();
    const states: State[] = []
    const nfaTable: Map<string, Map<string, string[]>> = new Map();

    // 给每一个state的对象生成独立的ID,通过map映射I和state
    const mark = (state: State) => {

        if (stateToId.has(state)) return;
        stateToId.set(state, states.length + 1);
        states.push(state);
        for (let transitions of state.transitions.values()) {
            for (let nextState of transitions) {
                mark(nextState)
            }
        }
    }

    mark(this);
    
    // 第一层循环遍历所有独立的state对象
    for (let state of states) {
        const id = stateToId.get(state);
        const row = new Map();

        // 遍历每一个state对象的字符集，如果是空字符就跳过
        // 如果是一个合法的正则文法字符，就获取这个字符可以跳转到所有状态
        // 根据这些状态反查ID，建立字符到某一个状态对应的ID映射
        for (let [char, nextStates] of state.transitions.entries()) {
            if (char === EPSILON) continue;

            const targetIds = nextStates.map(state => String(stateToId.get(state)))
            row.set(char, targetIds)
        }

        // 当前状态可以通过空节点所能达到的所有状态
        const closureStates = state.getEpsilonClosure();
        const closureIds = closureStates.map(state => String(stateToId.get(state)))
        row.set(EPSILON, closureIds)
        nfaTable.set(String(id), row)
    }
    return nfaTable;
}


// 最终生成的结构

// Map(6) {
//   '1' => Map(1) { 'ε' => [ '1', '2', '5' ] },
//   '2' => Map(2) { 'a' => [ '3' ], 'ε' => [ '2' ] },
//   '3' => Map(1) { 'ε' => [ '3', '4' ] },
//   '4' => Map(1) { 'ε' => [ '4' ] },
//   '5' => Map(2) { 'b' => [ '6' ], 'ε' => [ '5' ] },
//   '6' => Map(1) { 'ε' => [ '6', '4' ] }
// }

1. 组合与分解

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

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

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

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

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

1
2
3
4
5
6

+────────────────────────────────────────────────────────+
| 优先级 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'。

1
2
3
4
5
6
7

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

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

1.2.3 代码组装实战

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

// 自底向上组装状态机
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^*$$
• 代码脱糖映射：

  1 2 3

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

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

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

  1 2 3

  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 个状态！

  1 2 3 4

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

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

1
2
3
4
5
6
7
8
9

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 个状态！

  1 2 3 4 5

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

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

1
2
3
4

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

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

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

  1 2 3

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

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

1
2
3
4

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

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

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

  1 2 3 4 5

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

3.5 优化前后的惊人对比

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

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。

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

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

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

1. 有限自动机 (Finite Automata) 的本质

有限自动机（Finite Automata, FA）是正则表达式背后的底层物理引擎与执行机制。在工程界，它通常被称为有限状态机（Finite State Machine, FSM）。

在数据结构与算法视角下，状态机本质上是一个**带权/带标签的有向图 (Directed Graph)**：

• **节点 (Nodes)：代表系统的状态 (States)**。
• **边 (Edges)：代表状态之间的转移 (Transitions)**，每条边上标记了发生该转移所必须消耗的输入符号。

2. 正则文法与有限自动机的一一映射 (One-to-One Mapping)

正则文法的产生式规则与状态机的图结构存在严格的一对一对应关系：

1
2
3
4
5
6
7
8

      正则文法 (BNF 产生式)                       有限自动机 (有向图)
┌────────────────────────────────┐         ┌────────────────────────────────┐
│ 起始符号 S                      │  <===>  │ 起始状态 (带有来自外部的指示箭头)│
│ 产生式左侧非终结符 (当前变量)    │  <===>  │ 当前源状态 (Source State)       │
│ 产生式前缀终结符 (消耗字符)      │  <===>  │ 边上的转移字符 (Transition Label)│
│ 产生式右侧非终结符 (目标变量)    │  <===>  │ 转移目标状态 (Destination State) │
│ 空串推导规则 (A -> ε)           │  <===>  │ 接受状态 (双同心圆标记状态)     │
└────────────────────────────────┘         └────────────────────────────────┘

2.1 状态转移机制

以产生式 $S \to bA$ 为例：

1. 源状态：处于状态 $S$。
2. 字符消耗：当从输入字符串中读取（Consume）字符 'b' 时。
3. 目标状态：系统状态跳转至状态 $A$。

2.2 接受状态 (Accepting / Final States)

• 图形表示：在自动机图纸中，接受状态使用双同心圆（Double-circled）表示。
• 判决准则：当遍历有向图消耗完字符串的所有字符后，如果停留在某个接受状态，则判定该字符串被当前自动机所接受（Accepted）。
• 文法对应：在形式文法中，产生式 $A \to \epsilon$ 对应接受状态。因为 $\epsilon$ 代表空字符串，表示无需再转移，匹配在此圆满终止。

3. 有限自动机的分类谱系

在广义计算理论中，有限自动机划分为两大阵营：

1
2
3
4
5
6
7
8

                  有限自动机 (Finite Automata)
                             │
     ┌───────────────────────┴───────────────────────┐
有输出状态机 (With Output)                      无输出状态机 (Without Output)
(用于硬件控制与序列生成)                        (用于语言识别与正则表达式引擎)
     ├── Moore 机器 (输出取决于状态)                  ├── DFA (确定性有限自动机)
     └── Mealy 机器 (输出取决于状态+输入)             ├── NFA (非确定性有限自动机)
                                                      └── ε-NFA (带空转移的NFA)

在正则表达式引擎的设计与实现中，我们重点研究无输出的三种机器：**$\epsilon$-NFA、NFA** 和 DFA。

4. 三大正则自动机深度剖析：DFA, NFA 与 $\epsilon$-NFA

4.1 NFA (非确定性有限自动机)

• 非确定性（Non-determinism）的核心定义：允许在同一个输入符号下，从当前状态跳转到多个不同的目标状态。
• 执行行为：如果在状态 1 遇到字符 'a'，存在通向状态 2 和状态 3 的两条边，NFA 在概念上会“同时分裂并走入这两条路径”，以并行探索所有可能的接受路径。

4.2 $\epsilon$-NFA (带 $\epsilon$-空转移的非确定性有限自动机)

• 能力扩展：具备 NFA 的一切特性，并额外支持 $\epsilon$-转移（Epsilon-transitions）。
• $\epsilon$-转移的含义：允许系统在不消耗输入字符串中任何字符的情况下，自发地从一个状态跃迁到另一个状态（例如纯粹为了连接两个独立的自动机子模块）。
• 约束程度：限制最少，最适合作为人类构建正则模块的基本积木。

4.3 DFA (确定性有限自动机)

• 确定性（Determinism）的核心约束：
  1. 禁止多分支转移：给定当前状态和特定输入字符，其后继目标状态必须唯一且确定。
  2. 绝对禁止 $\epsilon$-转移：每一次状态转移都必须且只能消耗输入串中的一个确切字符。
• 执行优势：运行毫无歧义，没有分支试探，运行时只需要查表即可线性前进。

5. 核心架构设计：为什么需要三种自动机？

既然 DFA 性能最高且没有二义性，为什么不直接从正则表达式生成 DFA？

5.1 正则引擎编译管道 (Compilation Pipeline)

因为从人类编写的高阶正则表达式直接构造 DFA 极其复杂，工业界通用的标准流水线如下：

1
2
3
4
5
6
7
8
9
10
11
12
13

[正则表达式 (RegExp)]
        │
        ▼ (通过汤普森构造法，直观模块化拼装)
   [ε-NFA]
        │
        ▼ (消除 ε 转移与多分支)
    [NFA]
        │
        ▼ (通过子集构造法 Subset Construction 进行确定化)
    [DFA]
        │
        ▼ (通过 Hopcroft 等算法进行状态最小化)
[高效状态转移表 (Transition Table)]

• 构造期（Construction Time）：利用 $\epsilon$-NFA 的灵活性，能够像搭积木一样为各种正则操作符（拼接、选择、闭包）快速组装子图。
• 运行期（Runtime）：最终将机器转化为 DFA 状态表执行，获得严格的 $O(N)$ 线性时间复杂度保障，消除回溯性能陷阱。

6. 有限自动机（NFA）的形式化数学定义 (5-Tuple)

在理论计算机科学中，一个有限自动机由一个五元组严格定义：
$$M = (Q, \Sigma, \Delta, q_0, F)$$

7. 状态机对象设计

1
2
3
4
5
6
7
8
9
10

                ε                     A                     ε
      ┌───────────────────> ( 状态 1 ) ──────────> ( 状态 2 ) ──────────────────┐
      │                                                                         │
      │                                                                         ▼
( 起始状态 )                                                               (( 接受状态 ))
  (最左侧)                                                                     (双圈终点)
      │                                                                         ▲
      │         ε                     B                     ε                   │
      └───────────────────> ( 状态 3 ) ──────────> ( 状态 4 ) ──────────────────┘

这是汤普森构造法中用来实现正则表达式“或运算”（$A \mid B$）的标准状态机图。

2. 执行链路推导（以匹配字符 'A' 为例）：

1. 起始状态遇到 $\epsilon$（空转移）：
   • $\epsilon$ 代表“免费传送门”：无需消耗输入字符串中的任何字符，机器自发瞬移到了状态 1（同时也会瞬移到状态 3）。
2. 状态 1 遇到字符 'A'：
   • 消耗输入串中的字符 'A'，沿着有向边前进到状态 2。
3. 状态 2 再次遇到 $\epsilon$：
   • 不消耗字符，自动滑入最右侧的接受状态（双圈）。
4. 此时字符串读取完毕，机器停在接受状态，判定：匹配成功！

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

class State {
    accepting: boolean;
    transitions: Map<string, State[]>;
    constructor({ accepting = false }) {
        this.accepting = accepting;
        this.transitions = new Map();
    }
    addTransitionForSymbol(symbol: string, state: State): void {
        const transitionsForSymbol = this.transitions.get(symbol);
        if (transitionsForSymbol) {
            transitionsForSymbol.push(state);
        } else {
            this.transitions.set(symbol, [state]);
        }
    }
    getTransitionForSymbol(symbol: string): State[] {
        return this.transitions.get(symbol) || [];
    }
}

const s1 = new State({ accepting: false })
const s2 = new State({ accepting: true })

s1.addTransitionForSymbol('a', s2)
console.log(s1.getTransitionForSymbol('a'))

正则的历史

斯蒂芬·克莱恩 (Stephen Kleene, 1951年) —— 理论的诞生

• 学术背景：1951年，著名数学家斯蒂芬·克莱恩在理论计算机科学的自动机理论子领域中，为了形式化描述神经元活动与状态变化，首次提出并分类了形式语言。
• 正则集与正则语言：克莱恩发明了一种数学符号体系，称为“正则集”（Regular Sets），用于严格描述“正则语言”（Regular Languages）。
• 有限自动机的等价性定义：在自动机理论中，正则语言被正式且严格地定义为——能够被有限自动机（Finite Automata）所识别的语言。
  • 注：“有限自动机”（Finite Automata）与“状态机”（State Machines）在绝大多数计算语境下是完全等价且可以互换使用的术语。
• **克莱恩定理 (Kleene’s Theorem)**：确立了正则表达式与有限自动机在表达能力上的完全等价性。即：任何正则语言都可以由一个正则表达式表达，且必然存在一个有限自动机能够识别该语言，反之亦然。
• **克莱恩星号 (Kleene-star / Kleene-closure)**：广为人知的星号 * 操作符（代表一个匹配模式重复“零次或多次”），在计算机科学中的标准学术名称正是“克莱恩星”或“克莱恩闭包算子”。

诺姆·乔姆斯基 (Noam Chomsky, 1956年) —— 形式层级与算力边界

• **乔姆斯基层次结构 (Chomsky Hierarchy)**：1956年，被誉为现代语言学之父的诺姆·乔姆斯基建立了著名的形式文法层级分类体系。
• **3型文法 (Type 3 Grammars / Regular Grammars)**：在该层级中，正则语言严格对应由“3型文法”（即正则文法）所生成的语言集合。
• 算力局限与工程铁律：
  • 在乔姆斯基文法体系中，正则文法是表达能力最弱的一种形式文法。
  • 正则文法严格位于“上下文无关文法”（Context-Free Grammars, CFG）之下。而 CFG 才是现代绝大多数编程语言（如 C、Java、Rust、Python 等）语法解析的基石。
  • 关键结论：由于正则文法表达能力的局限性，在一般情况下，仅依靠纯粹的正则表达式是根本不可能或极难完整解析一门现代编程语言的（例如无法单靠纯正则处理具有无限嵌套结构的语法块与括号平衡）。

肯·汤普森 (Ken Thompson, 约1968年) —— 黑客出鞘与工程落地

• 理论走向工程：约12年后（1968年前后），著名的 Unix 之父、图灵奖得主肯·汤普森将正则表达式从纯理论数学体系引入实际工程中，使其成为计算机工业的标准工具。
• 两大经典应用场景：
  1. **模式匹配 (Pattern Matching)**：用于海量文本与字符串的高效模式搜索（Unix 下 grep、sed、awk 等工具的理论基石）。
  2. **词法分析 (Lexical Analysis)**：在现代编译器前端解析编程语言时，用于实现扫描器（Scanner）或分词器（Tokenizer）模块，将源码切分为 Token 流。
• **汤普森构造法 (Thompson Construction)**：汤普森完全基于有限自动机理论实现了正则表达式。他提出了一套经典的、直接从正则表达式语法树构造非确定性有限自动机（$\epsilon$-NFA）的规范算法，后世称为“汤普森构造法”。
• 性能优势与现代影响：
  • 基于状态机实现的正则表达式引擎具备极其优异的运行性能（线性时间复杂度保证，避免指数级回溯爆炸）。
  • 现代编译器解析器生成工具（如 Bison、Flex）在构建底层 Tokenizer 模块时，依然全面沿用此架构。

字母表

从最基本的概念开始，来体会如何演变到状态机的过程。

正则表达式用于匹配字符串，而字符串一定来自于某个字母表。

• 定义：字母表是字符/符号（Characters / Symbols）的有限非空集合。
• 数学表示：在形式语言中，字母表通常用希腊字母大写 $\Sigma$ (Sigma) 表示。
• 示例：
  $$\Sigma = {a, b}$$
  该字母表仅包含两个合法字符：$a$ 与 $b$。

语言 (Language, $L$)

• 定义：语言是特定字母表 $\Sigma$ 上所有满足某种条件的字符串的集合。
• **无限语言 (Unbound / Infinite Language)**：
  • 例如，语言 $L_1$ 定义为字母表 $\Sigma = {a, b}$ 上由这些字符所有可能排列构成的任意长度字符串的集合：
    $$L_1 = {\epsilon, a, b, aa, ab, ba, bb, aaa, \dots}$$
  • 由于字符串长度不受限制，该语言包含无穷多个字符串。
• **有限受限语言 (Restricted / Finite Language)**：
  • 若在生成集合时增加额外约束条件，例如：规定字符串长度必须恰好为 2 个字符，则生成语言 $L_2$：
    $$L_2 = {aa, ab, ba, bb}$$
  • 此时，$L_2$ 是一个只包含 4 个元素的有限集合。

形式文法 (Formal Grammar) 的数学定义

当我们对语言中的字符串结构提出约束规则时，就诞生了文法（Grammar），在计算机科学中称之为形式文法（Formal Grammar）。

一个形式文法 $G$ 在数学上由一个四元组严格定义：
$$G = (N, T, P, S)$$

给定文法：

• $N = {S, X}$
• $T = {a, b}$
• 起始符号：$S$
• 产生式集合 $P$ 包含两条规则：
  1. $S \to aX$ （$S$ 推导出字符 $a$ 跟随变量 $X$）
  2. $X \to b$ （变量 $X$ 替换为终结符 $b$）

推导过程：
$$S \implies aX \implies ab$$
该文法所能接受/生成的唯一合法字符串就是 "ab"。

正则语法

乔姆斯基根据产生式规则的形式约束，将形式文法划分为 4 个层级。文法所处的层级越低，规则受到的限制越多，其表达能力也越弱：

在形式语言理论中，一个文法由四元组 $G = (N, T, P, S)$ 定义。其中，决定一个文法属于哪个层级的，全看产生式规则（$P$ 中的规则 $\alpha \to \beta$）受到的数学限制严苛程度。

乔姆斯基发现：文法规则的受限程度，与执行这套规则所需的“机器模型（自动机）的存储能力”，存在极其优美的严格一对一对应：

理论本质：乔姆斯基通过对“左侧能不能带上下文”以及“右侧非终结符能放几个、放哪里”施加越来越苛刻的限制，逐步把文法从通用图灵机一步步剥离成了只能做简单模式流转的有限自动机。
核心结论：由于正则文法严格处于上下文无关文法（CFG）的下层，因此单纯使用纯正则表达式是无法解析完整的编程语言语法的。

形式文法本质上就是一个“文字擦除与替换的游戏”。

在解释规则前，先认识两个最基础的“零件箱”：

• $N$（Non-terminals，非终结符 / 变量）：你可以把它理解成“半成品”或“待填空的占位符”。通常用大写字母表示（比如 $A, B, S$）。它们最终不能出现在成品文章里，必须被替换掉。
• $T$（Terminals，终结符）：你可以把它理解成“最终零件”或“固定字面量”。比如字母 'a', 'b'，数字 '1', '2'。它们生成了就定死了，不能再替换。

有了这两个箱子，那些奇怪的符号就很容易理解了：

1. **$N \cup T$**：
   • “$\cup$”是集合的“并集”。意思就是把“半成品”和“最终零件”混在一个大盒子里。
2. **$(N \cup T)^+$ 中的那个小加号 $+$**：
   • 正闭包，意思是“至少有 1 个符号”。
   • 大白话：不管里面装的是大写还是小写，至少得有 1 个字符，不能是空（不能是空气）。
3. $(N \cup T)^*$ 中的那个小星号 $*$（克莱恩星）：
   • 闭包，意思是“可以有任意多个符号，也可以是 0 个（即空串）”。
4. $\alpha \to \beta$（阿尔法 变成 贝塔）：
   • 规则的含义极其直白：“你在纸面上只要看到了 $\alpha$ 这一坨东西，就可以把它擦掉，换成 $\beta$ 这一坨东西”。

0型：无限制文法 与 图灵机的“无限纸带”

1. 产生式规则：$\alpha \in (N \cup T)^+, \beta \in (N \cup T)^*$

• **左边 $\alpha$**：只要不是空的，你想写几个字符就写几个字符，可以大写小写混杂（比如 $AbC$、或 $aBa$）。
• **右边 $\beta$**：没有任何限制！可以变得很长，也可以变得很短，甚至可以直接变成“空（消失不见）”。
• 大白话：“无法无天”。你可以定义任意离谱的替换规则，比如：只要看到 猫狗鸡 三个字连在一起，就可以瞬间替换成一个字 神，或者直接把它们全抹掉蒸发。

2. 什么是“图灵机”？为什么说是“无限纸带”？
   在 1936 年，阿兰·图灵设计这个理论模型时，现代电脑还没诞生，内存条更不存在。图灵是怎么想象一台终极计算机的？

想象一台老式打字机，但它有极其恐怖的能力：

1. 纸带（就是内存）：有一条长长的纸带，被划分成一个一个的小格子，每个格子里可以写一个字符。
2. 读写头（就是 CPU 的探针）：机器有一个指针停在某个格子上，它可以读出格子里现在的字，可以擦掉重写一个字，并且可以向左移一格，或者向右移一格。
3. 为什么叫“无限纸带”？
   • 意味着这台机器拥有无限大的草稿纸（无限内存）！
   • 只要计算需要，读写头可以往右走一万亿步，再往左走一万亿步，纸带两头无限延伸，永远不用担心内存爆满（Out of Memory）。

与 0 型文法的关系：
凡是这台“拥有无限内存的图灵机”能够计算出来的任何逻辑，0 型文法随便写写规则就能完全模拟出来。因此它代表了计算机能够计算的最高极限。

1型：上下文相关文法 与 线性有界自动机（LBA）

到了 1 型文法，科学家们开始给它套上枷锁了。它加了两条非常致命的紧箍咒：

1. 限制一：看规则 $\alpha_1 A \alpha_2 \to \alpha_1 \beta \alpha_2$（什么叫上下文？）
   请仔细看箭头两边：

• 左边是：$\alpha_1$ $A$ $\alpha_2$
• 右边是：$\alpha_1$ $\beta$ $\alpha_2$

发现了没有？左右两边的 $\alpha_1$ 和 $\alpha_2$ 根本没有变！ 真正被替换的，仅仅是夹在中间的那个 $A$ 变成了 $\beta$。

• 为什么叫“上下文相关（Context-Sensitive）”？
  • $\alpha_1$ 就是 $A$ 的左邻居，$\alpha_2$ 就是 $A$ 的右邻居。这就是所谓的“上下文”！
  • 生活中的例子：汉字“长”。
    • 如果它的上下文是“校 $\underline{\quad}$ 室”，这个字必须读 $zhǎng$；
    • 如果它的上下文是“细 $\underline{\quad}$ 线”，这个字必须读 $cháng$。
    • 这个字怎么替换、怎么解析，完全取决于它周围的邻居是谁！ 单独看一个 $A$ 你不能动它，只有当它左右两边刚好是 $\alpha_1$ 和 $\alpha_2$ 时，才准许把它展开成 $\beta$。

2. 限制二：长度要求 $|\alpha| \le |\beta|$（什么叫非收缩？）

• $|\alpha|$ 代表左边的字符个数，$|\beta|$ 代表右边的字符个数。
• 左边长度 $\le$ 右边长度，意味着：每一次替换，字符串要么长度不变，要么越变越长，绝对不准缩短！更不准凭空蒸发成空串！

什么是“线性有界自动机 (LBA)”？为什么说纸带受限？

既然 1 型文法的规则规定了“只准变长，不准缩短”，那它对应的机器就发生质变了：

• 依然是刚才图灵机的那台打字机，依然有读写头可以左右走动。
• 但是，无限纸带被没收了！
• 如果你给机器输入了一个长度为 5 的单词（比如 "apple"），这台机器的纸带两头就被打上了物理界限标签（[ 和 ]）。
• 机器的读写头只能在这 5 个格子（或者最多常数倍，比如 $2 \times 5 = 10$ 个格子）的范围内来回移动修改，绝对不允许越界走到外面去申请新的草稿纸！
• “线性有界”的大白话：你这台机器能用的内存空间上限，被你输入的文本长度死死锁定了（两者成严格的线性正比关系）。

与 1 型文法的关系：
因为 1 型文法的产生式是“只变长不缩短”的，如果你想逆向去推导和验证一段代码合不合法，推导过程中的中间字符数量绝不可能超过你最初的代码长度。所以计算机根本不需要无限草稿纸，只要在输入大小的有界空间内，就一定能算完！

在 1 型文法里，我们要改一个占位符，还得看左右邻居的脸色（$\alpha_1 A \alpha_2 \to \alpha_1 \beta \alpha_2$）。

2型： 上下文无关文法 与 下推自动机 (PDA)

文法规则：$A \to \gamma$ —— “六亲不认的单挑”

• 左边：必须且只能是单独 1 个大写字母（单个非终结符 $A$）。绝对不准带任何邻居！
• 右边：任意符号串 $\gamma$（爱写啥写啥，可以长也可以短）。
• 为什么叫“上下文无关”？
  • 因为无论 $A$ 处于什么样的水深火热中，左边站着谁、右边站着谁，只要你看到单独的 $A$，**完全不需要看邻居脸色，直接就能把它换成 $\gamma$**！
  • 这就叫“上下文无关（Context-Free）”。

神奇能力：为什么它能解决“套娃”和“嵌套”？
虽然左边只能是单独一个 $A$，但右边却拥有把符号“夹在中间”的特权！
看看我们上一讲提到的经典规则：
$$S \to (S) \quad \text{或} \quad S \to \epsilon$$
注意：大写的 $S$ 被两边的左右括号死死包在了中间！

• 替换第 1 次：$(S)$
• 替换第 2 次：$((S))$
• 替换第 3 次：$(((S)))$
• 最后把 $S$ 抹掉变空气（$\epsilon$）：$((()))$
  它像俄罗斯套娃一样，两边对称地往外膨胀！这正是解析编程语言中 (1 + (2 * (3 + 4))) 或 { if { while { ... } } } 所必须的核心能力。

什么是下推自动机 (PDA)?

如果用一句话概括下推自动机（Pushdown Automaton，简称 PDA）的本质：

下推自动机 = 一个普通的有限状态机（FA） + 外挂了一个具有后进先出特性的【栈（Stack）】。

它是乔姆斯基 2 型文法（上下文无关文法 CFG）的物理执行模型。计算机世界里所有编译器的语法分析器（Parser），骨子里全都是一台下推自动机！

为什么叫“下推”（Pushdown）这么奇怪的名字？

这个名字来自 20 世纪 50 年代食堂里的一个生活装置——弹簧餐盘架（或者枪械的弹夹）：

1
2
3
4
5
6
7
8
9
10
11

放入餐盘 (Push 压入)
      │
      ▼
┌───────────┐
│  [餐盘 3]  │ ◄── 栈顶（只有最上面的盘子看得到、拿得到）
├───────────┤
│  [餐盘 2]  │ ◄── 下面的盘子被压在底下
├───────────┤
│  [餐盘 1]  │
└─────┬─────┘
    [ 弹簧 ]  （放一个盘子，弹簧被往下压一格；拿走一个，弹簧往上顶一格）

• 当你往架子上叠新盘子时，弹簧被往下推（Push down）；
• 当你拿走最上面的盘子时（Pop 弹出），下面的盘子才会露出来；
• 你永远只能操作最顶上的这一个盘子，看不到更深处的盘子。

科学家们把这个只有一端能进出的存储结构做进自动机里，就把它命名为了“下推自动机”。

它长什么样？（硬件解剖图）

下推自动机的内部只有三大核心构件：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

              输入纸带（从左往右只读一次，绝不回头）
        ┌───┬───┬───┬───┬───┬───┬───┐
输入 ──>│ a │ a │ a │ b │ b │ b │ $ │
        └───┴───┴───┴───┴───┴───┴───┘
                  ▲
                  │ 读头（只能向右移动）
        ┌─────────┴─────────┐
        │   有限状态控制器   │ (内部只有几个灯泡/状态开关)
        └─────────┬─────────┘
                  │
                  ▼ 读写栈顶（压栈 / 弹栈）
               ┌─────┐
               │  A  │ ◄── 栈顶（当前看到的符号）
               ├─────┤
               │  A  │
               ├─────┤
               │  Z0 │ ◄── 栈底标记
               └─────┘
              【下推栈】

1. 输入带：待检查的代码或字符串，单向流水线，读过就扔。
2. 有限状态控制器：和普通状态机一样，负责记录“当前所处的状态”（比如：正在读左括号状态、还是正在读右括号状态）。
3. 下推栈（关键外挂）：理论上可以无限往上叠放符号的栈。它赋予了机器“记忆嵌套深度”的超能力！

确定性 PDA vs. 非确定性 PDA（编译器的命门）

下推自动机也分两类，这个区分在编译器工业界是生死攸关的：

1. **非确定性下推自动机 (NPDA)**：

   • 允许在同一时刻有多条分支，或者允许在不读字符的情况下自发瞎猜压栈。
   • 数学地位：它完美等价于全部上下文无关文法（CFG）。
   • 缺点：因为有“瞎猜/分支”，计算机直接执行它需要大量的试探或回溯，解析速度不稳定。

2. **确定性下推自动机 (DPDA)**：

   • 每一步该压栈、该弹栈、还是该切状态，唯一确定，绝不犹豫，毫无二义性！
   • 工业地位：它的解析时间是严格的 $O(n)$ 线性时间。
   • 现代编程语言的铁律：我们在设计 C++、Rust、Python、Java 语法时，语法设计专家会故意限制语法规则，确保这门语言能够被 确定性下推自动机（DPDA） 解析（比如大家常听说的 LR(1)、LALR 文法）。这样编译器在编译几百万行代码时，才能瞬间完成，绝不卡死！

现实生活中你在哪里天天用到它？

只要你在写代码，下推自动机就无时无刻不在你身边运转：

1. 你的 IDE 代码编辑器：
   你在 VS Code 里打了一个 {，编辑器能立刻高亮出它对应的 } 在哪一行，哪怕中间嵌套了 20 层循环。背后就是一个迷你 PDA 在用栈帮你匹配。
2. 算术表达式求值：
   你在计算器里输入 1 + 2 * (3 + (4 - 5))，经典的“双栈求值算法（一个操作数栈、一个运算符栈）”，本质上就是手动用代码实现了一台确定性下推自动机。
3. 编译器前端语法分析器（Parser）：
   任何一门语言的编译器，不管是 Clang、GCC 还是 Python 解释器，在词法分析把源码切成 Token 之后，拿着这些 Token 一层层组装成语法树（AST）的核心引擎，其数学理论模型就是一台下推自动机！

3型：正则文法 (Regular) 与 有限自动机 (FA)

到了 3 型文法，科学家们觉得：“给你一个能无限堆盘子的桶，你的能力还是太强了（解析起来不够快）”。

文法规则：$A \to aB$ 或 $A \to a$ —— “排队报数，禁止套娃”
在 2 型里，虽然左边单挑，但右边允许写 $(S)$ 把变量夹在中间套娃。
到了 3 型，科学家直接立下一条死规矩：右线性（Right-linear）！

• 产生式的右边，**只能先产生一个真正的文字零件（终结符 $a$），后面最多只能跟 1 个占位符 $B$**；
• 而且这个 $B$ 必须老老实实呆在整个队伍的最屁股后面！
• 严禁把占位符夹在中间！ 你绝对不能写 $A \to aBb$（左边产一个 $a$、右边产一个 $b$）。

大白话：你只能像排队报数一样，从左往右一个字一个字往后接龙，彻底剥夺了从两边往中间对称包裹的能力！

配备的装备：有限自动机 (FA) 与“手里的几个灯泡开关”
到了这一层，机器的装备被扒得只剩底裤了：

• 无限草稿纸？没有！
• 装盘子的桶（栈）？彻底没收！
• 你手里只剩下什么？
  你手里只有几个固定的开关按钮（比如 3 个红、黄、绿指示灯，即所谓的“有限状态” States）！

机器运转的方式变成了极其弱智但也极其快速的盲操作：

1. 输入纸条从眼前滑过，一次看一个字符；
2. 如果看到 'a'，根据手册把黄灯关掉，把绿灯打开；
3. 如果看到 'b'，把绿灯关掉，把红灯打开；
4. 致命特征：过目即忘！
   • 机器在任何瞬间，唯一的记忆就是“当前亮着哪盏灯”。
   • 至于之前到底看过了 5 个字符还是 100 个字符？之前发生过什么？它完全失忆，毫无印象！

为什么用这几个灯泡，绝对解不开括号匹配？
假设你手头只有 3 盏灯（3 个状态），现在输入了 4 个左括号 ((((：

1. 读入第 1 个 ( $\to$ 点亮 1 号灯；
2. 读入第 2 个 ( $\to$ 点亮 2 号灯；
3. 读入第 3 个 ( $\to$ 点亮 3 号灯；
4. 读入第 4 个 ( 时，灾难发生了：你没有 4 号灯了！你只能被迫重新点亮刚才已经亮过的 1 号灯或者 2 号灯（也就是在图上兜圈子形成死循环 Loop）。
5. 记忆崩溃：接下来的右括号来了，机器看着那几盏灯，已经彻底不知道前面到底进来了 4 个括号还是 100 个括号！它再也无法验证左右是否匹配了。

这就是有限自动机（正则）的宿命：
因为没有栈，它根本不具备“数数”并“存起来待会儿对账”的能力。它只能识别平铺直叙的流水线字符（比如“以 $a$ 开头，后面跟着若干个 $b$，最后以 $c$ 结尾”）。

为什么编程语言是上下文无关文法?

如果从“一段代码在逻辑上是否合法”的整体视角来看，Python 以及绝大多数现代编程语言确实都是“上下文相关”的。比如：

• 一个变量必须先定义再使用（变量是否存在取决于上下文作用域）。
• 函数调用传参的个数和类型是否匹配（取决于函数定义处的上下文）。
• Python 最具特色的代码缩进（缩进几格取决于外层代码块的上下文）。

那为什么编译原理教材和课程中都一致说“编程语言是用上下文无关文法（CFG）定义的”呢？

这背后其实是现代编译器工程中最重要的设计哲学：关注点分离（Separation of Concerns）与工程妥协。

编译器的分层解耦：句法（Syntax）与语义（Semantics）

编译器并没有试图在一张文法规则里解决所有问题，而是把它拆成了两个阶段：

1
2
3
4
5
6
7
8
9
10

源代码 
  │
  ▼
[阶段一：语法/句法分析 (Parsing)] ──> 使用“上下文无关文法 (CFG)”
  │   只负责检查代码的“骨架结构”是否合法，生成 AST 语法树。
  │   不管变量有没有声明，也不管类型对不对。
  ▼
[阶段二：语义分析 (Semantic Analysis)] ──> 处理真正的“上下文相关 (Context-Sensitive)”
      使用“符号表 (Symbol Table)”和属性检查代码，
      负责查作用域、查类型匹配、查变量是否声明。

在句法分析阶段，编译器只关心形状：

• 它只认：if <条件表达式> : <代码块> 这个结构对不对；
• 至于 <条件表达式> 里的变量在上下文里有没有被声明、是不是全局变量，句法分析器完全不关心，直接当成合法的表达式节点放进 AST 里。
  这一层骨架结构，就是用上下文无关文法（CFG）来表达的。

计算复杂度的硬限制：为什么不用真正的“1型上下文相关文法”？

如果我们在第一阶段就用乔姆斯基 1 型（上下文相关文法 CSG）来描述整个 Python，后果是灾难性的：

• 1型文法解析是 PSPACE 完全问题：通用解析器运行极其缓慢，在最坏情况下时间复杂度呈指数级爆炸。
• 2型上下文无关文法（CFG）极其高效：存在确定性的线性时间算法（如 LL(k)、LR(k)、LALR 以及 Python 3.9+ 正在使用的 PEG 解析器），能做到 $O(n)$ 线性时间内飞速解析数万行代码。

因此，计算机科学家和工程师达成了妥协：用 2型文法（CFG）搭建高速骨架，把上下文相关的逻辑剥离到后续阶段用普通程序逻辑去检查。

Python 的特殊疑问：缩进（Indentation）难道不是上下文相关吗？

Python 强依赖缩进，很多初学者会疑惑：“下一行属于哪个代码块，必须对比上一行的缩进深度，这难道不是赤裸裸的上下文依赖吗？”

Python 的解决方案非常绝妙——下放给词法分析器（Lexer Hack）：

1. 词法分析器在读取字符时，在内存里偷偷维护了一个缩进栈（Indent Stack）。
2. 当发现缩进增加时，它向后扔出一个虚拟的 Token：INDENT。
3. 当发现缩进减少时，它弹栈并扔出一个或多个虚拟 Token：DEDENT。
4. 到了语法分析器（Parser）手里时，缩进已经被抹平成了普通的标记符号，文法规则依然是完美的上下文无关：

   1 2	if_stmt : "if" test ":" suite suite : simple_stmt | NEWLINE INDENT stmt+ DEDENT

   （这和 C/Java 中的 { 对应 INDENT、} 对应 DEDENT 本质没有任何区别。）

正则为什么不能解析语言

核心瓶颈：有限状态机没有“无限计数”的记忆能力

• 3 型文法对应的底层机器是有限自动机（FA）。
• 有限自动机的关键定语是“有限”（Finite）：它只有固定的 $k$ 个内部状态，没有栈、没有额外变量、没有辅助内存。
• 它在任何时刻的全部记忆，仅仅等于它“当前停留在哪一个状态节点上”。

数学反例：括号平衡匹配（$a^n b^n$ 问题）
在任何编程语言中，代码块 { ... }、函数传参 ( ... )、算术表达式 ((1 + 2) * 3) 都允许无限深度的嵌套与对称闭合。
抽象成最简单的数学语言，这就是语言：
$$L = { a^n b^n \mid n \ge 1 } \quad \text{（即 $n$ 个左括号后面必须精确跟随 $n$ 个右括号）}$$

利用计算机科学中的【鸽巢原理（抽屉原理）/ 泵引理 (Pumping Lemma)】推导：

1. 假设存在一个有限自动机能够识别这个合法的括号嵌套语言，设该自动机内部有 $k$ 个状态。
2. 现在我们给它输入一个嵌套深度超过状态总数的串，比如连续输入 $n = k + 1$ 个左括号（即输入串包含 $k+1$ 个 $a$）。
3. 根据鸽巢原理：只有 $k$ 个状态，却读入了 $k+1$ 个字符，自动机在读这串左括号的过程中，必然会重复踏入某一个相同的状态两次（即图上必然出现了闭环 Loop）！
4. 致命推论：一旦在读取左括号时陷入了循环回路，这个自动机就彻底丢失了它到底已经读入了多少个左括号的精确计数！
5. 结果就是：它再也无法保证右边紧跟着的右括号数量是否恰好也是 $n$ 个。它必然会错误地接受像 $a^{n+m}b^n$ 这样括号不匹配的非法串。

因此定理得证：有限自动机（及等价的正则表达式）从理论上绝对不可能表达具有无限嵌套、自平衡特性的语法结构，而现代编程语言的骨架偏偏全都是这种自包含的嵌套结构。

正则一定有回溯么？

门派一：正统自动机派（无栈、无回溯、绝对线性时间）

代表选手：Ken Thompson 的原始算法、Unix 的 grep、Google 开发的 RE2 引擎、Rust 的 regex 库。

你可能会极其好奇：“既然没有栈，遇到分支选择（比如 cat|car），它不回溯怎么知道该走哪条路？”

答案是：它不是“走错了再退回来”，而是“影分身术（并行推进）”！
有限自动机（特别是 NFA）在面对多个分支时，根本不需要用栈去记录回退点。

直观图解：假设匹配 (cat|car)，目标字符串是 "car"：

1
2
3

              ┌── 走 'c' ──> [状态A] ── 走 'a' ──> [状态C] ── 走 't' ──> (接受)
[起始状态] ───┤
              └── 走 'c' ──> [状态B] ── 走 'a' ──> [状态D] ── 走 'r' ──> (接受)

1. 读入第 1 个字符 'c'：
   • 自动机同时踏入状态 A 和 状态 B。此时自动机内部的状态集合是：{A, B}。
2. 读入第 2 个字符 'a'：
   • 状态 A 走向 C，状态 B 走向 D。当前存活的状态集合是：{C, D}。
3. 读入第 3 个字符 'r'：
   • 从状态 C 无法消耗 'r'，这条分支死掉了；
   • 但从状态 D 成功消耗 'r'，顺利走进接受状态！
4. 匹配成功！

整个过程中，输入字符串只被从左往右读了一遍，机器一次都没有往回倒退，也根本不需要一个“栈”来记账！
它只是每走一步，都在维护一个当前存活状态的“小集合”。这种算法由肯·汤普森在 1968 年发明，速度快得不可思议！

门派二：回溯派（带栈、有回溯、可能导致指数级卡死）

代表选手：Perl、Python (re 模块)、Java、JavaScript (RegExp)、PCRE、.NET。

既然自动机派速度又快又不需要栈，为什么 Python、Java 他们不用呢？

1. 为什么回溯派要引入“栈”？
   因为人类在实际编程中，给正则表达式贪婪地加了太多理论之外的超纲功能：

• **捕获组与反向引用 (Backreferences)**：比如 ([a-z]+)\1，要求后面匹配的单词必须和前面捕获的一模一样。
• **零宽断言 / 环视 (Lookahead / Lookbehind)**：比如 (?<=foo)bar。

致命的真相：根据乔姆斯基层级，“反向引用”根本不是 3 型正则语言，它甚至超越了 2 型，属于 1 型（上下文相关）！
纯有限自动机是绝对做不到反向引用的。为了支持这些功能，Perl、Python 引擎的开发者不得不放弃纯自动机，引入了调用栈，采用“贪婪试探 + 碰壁回溯（Backtracking）”的算法。

2. 回溯派的噩梦：灾难性回溯 (Catastrophic Backtracking)
   一旦引入了栈和回溯，灾难就可能发生。
   比如这条简单的正则：

   1

   (a+)+$

   如果拿它去匹配一串长文本：aaaaaaaaaaaaaaaaaaaaaaaaX（后面带一个不匹配的 X）：
3. 引擎一头扎进去，贪婪地穷举第一层 a+ 到底切几个，第二层 a+ 切几个；
4. 读到最后发现没有 $，匹配失败！
5. 于是从栈里弹栈回退，尝试换一种切分方式；
6. 这种穷举组合呈指数级增长（$2^n$）！如果输入有 30 个 a，回溯次数高达 $2^{30} \approx 10$ 亿次！
7. 结果：Python 进程直接 CPU 飙到 100%，卡死几十分钟甚至几天！这就是黑客极其喜欢的 ReDoS（正则表达式拒绝服务攻击）。

计算机泰斗的愤怒与回归：Russ Cox 与 RE2

在 2007 年，Go 语言核心设计者、Google 架构师 Russ Cox 写了一篇震动整个计算机界的经典论文：

《Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python…)》
（正则表达式匹配本可以简单又飞快，但在 Java、Python 里面却慢得像蜗牛……）

Russ Cox 在文章中指出：

• 现代很多语言的正则引擎走偏了，搞出了极其低效的带栈回溯机制；
• 而 Thompson 在 1968 年写的基于纯状态机的正则引擎，即便面对恶意输入，也永远在几微秒内给出结果，绝不卡死。

后来，Google 索性自己写了一个彻底摒弃回溯的正则库——RE2（现在也被 Go、Rust 官方库吸收）。RE2 故意不支持反向引用等超纲特性，严格遵循有限自动机理论，保证绝对不回溯、绝对不爆栈、严格线性时间！

巴科斯范式 (BNF) 与正则表达式的本质等价性

本质揭秘：正则表达式只是正则文法的“语法糖”

• 形式文法的产生式通常书写为巴科斯范式（BNF, Backus-Naur Form）。
• 关键洞察：我们日常使用的正则表达式，在本质上只是对应正则文法在工程实现上的一种更简洁、更方便在代码中书写的语法符号（Syntactic Notation）。两者在理论上完全等价。

等价性推导案例
考察以下 BNF 正则文法产生式：

1. $S \to aS$
2. $S \to bA$
3. $A \to cA$
4. $A \to \epsilon$

其中符号 $\epsilon$（Epsilon）代表空字符串（Empty String），意味着可以直接消除该非终结符并结束推导。

若要匹配字符串 "abc"，推导路径如下：
$$S \xrightarrow{(1)} aS \xrightarrow{(2)} abA \xrightarrow{(3)} abcA \xrightarrow{(4)} abc\epsilon = abc$$

该 BNF 规则与正则表达式 a*bc*（或者以 a 开头、紧随 b、后接可选 c 的模式）在逻辑语义上完全等价。在代码中编写 BNF 极其冗长，而正则表达式提供了极致简练的等价记号。

场景分析

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
41
42
43
44
45
46

+---------------------------------------------------------------------------------------------------+
|                                      PVE 存储服务端 (Linux 底层)                                     |
|                                                                                                   |
|   +-----------------------+              (异步下刷 Flush)              +----------------------+   |
|   | NVMe SSD 写入缓存层    | -----------------------------------------> | 底层 HDD 机械存储池   |   |
|   | (dm-writecache 水位)  |                                            +----------------------+   |
|   +-----------+-----------+                                                                       |
|               |                                                                                   |
|               v                                                                                   |
|   +-----------+-----------+                                                                       |
|   | iSCSI Target 服务端   | <=================== 3260 端口 (iSCSI 块存储流量) ====================+   |
|   +-----------------------+                                                                       |
+---------------+-----------------------------------------------------------------------------------+
                ^
                |
          (SSH: 22 端口)
    定时查询 dmsetup status
                |
                v
+---------------+-----------------------------------------------------------------------------------+
|                                          Windows 客户端                                           |
|                                                                                                   |
|   +-------------------------------------------------------------------------------------------+   |
|   |                               Node.js 监控守护进程 (后台常驻)                                 |   |
|   |                                                                                           |   |
|   |   1. 每 3 秒执行一次 SSH 命令查询 PVE 端脏页比例                                           |   |
|   |   2. 计算当前水位: Dirty Blocks / Total Blocks                                            |   |
|   |   3. 匹配控速策略:                                                                        |   |
|   |      * 水位 > 85%  -->  强制降速至 10 MB/s (防止 SSD 缓存被打爆假死)                      |   |
|   |      * 水位 70%~85% --> 限制至 30 MB/s                                                    |   |
|   |      * 水位 50%~70% --> 限制至 60 MB/s                                                    |   |
|   |      * 水位 < 50%  -->  解除限速 (0 / 恢复满速)                                           |   |
|   +---------------------------------------------+---------------------------------------------+   |
|                                                 |                                                 |
|                            (WebSocket / CDP 通信: 8080 端口)                                      |
|                       发送 SteamClient.Downloads.SetDownloadThrottle                              |
|                                                 |                                                 |
|                                                 v                                                 |
|   +---------------------------------------------+---------------------------------------------+   |
|   |                       Steam 客户端 (-cef-enable-debugging 启动)                           |   |
|   |                                                                                           |   |
|   |   [CEF 调试接口] ------------> [下载管理器引擎] ----------------> [写入挂载的 iSCSI 盘]   |   |
|   |   (实时注入速率)               (动态调整拉取速度)                  (NTFS 格式 / 映射自 PVE) |   |
|   +-----------------------------------------------------------------------------+-------------+   |
+---------------------------------------------------------------------------------|-----------------+

项目地址

🚀 Steam Auto Throttle

实现流程

Steam 开启 CEF

Steam CEF（Chromium Embedded Framework） 是 Valve 为 Steam 客户端构建全新 UI（基于 React / TypeScript）所内嵌的 开源 Chromium 网页渲染引擎。

现代 Steam 客户端除了最底层的 C++ 游戏启动与网络通讯核心外，整个商店、库、好友列表、下载管理界面本质上都是运行在这个内置 Chromium 浏览器中的 Web 页面。

参数 -cef-enable-debugging 的底层作用
给 Steam 启动项添加 -cef-enable-debugging，本质上是向其内部的 Chromium 内核传递了 –remote-debugging-port 指令：

暴露 CDP 调试端口：默认在本地 127.0.0.1:8080（或系统动态端口）启动一个 HTTP / WebSocket 服务。

开放 Chrome DevTools Protocol (CDP)：允许外部程序（浏览器开发者工具、Node.js、Python 等）通过标准的 CDP 协议，直接连接到 Steam 的前端渲染进程。

打通 SteamClient 原生桥接对象：Steam 前端暴露了一个特权的全局 JS 对象 window.SteamClient，该对象封装了与 Steam C++ 底层通信的各种 IPC 接口。开启调试后，外部脚本可以通过 CDP 的 Runtime.evaluate 自由调用这些接口。

找到 Steam 快捷图标的位置，修改启动参数命令

1

"C:\Program Files (x86)\Steam\Steam.exe" -cef-enable-debugging

在浏览器访问 http://localhost:8080/json 来验证是否启用成功。

功能设计

• 静默拉起

通过 pkg 编译为 .exe 文件，修改默认的 steam 快捷方式,右键点击捷方式 -> 属性（Properties）。

1
2
3
4
5

# 将 Target（目标） 清空并替换为以下单行命令：
mshta vbscript:CreateObject("WScript.Shell").Run("""C:\ProgramData\Microsoft\Windows\Start Menu\Programs\Steam\steam-throttle.exe""",0,false)(window.close)

# 将 Start in（起始位置） 填入
C:\ProgramData\Microsoft\Windows\Start Menu\Programs\Steam

• 动态限速

缓存使用超出 90% 开启限速，直到缓存回落到 80% 以下

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
41
42
43
44
45
46
47

let lastSpeed = 0;
let startTimeStemp = Date.now();
let low = 80;
let high = 90
let isThrottle = false;
export function calculateTargetThrottle({ dirtyRatio }, avgMBps) {
    if (Date.now() - startTimeStemp < 60 * 1000) {
        return {
            needUpdate: false,
            speed: 0
        };
    }

    startTimeStemp = Date.now();

    if (dirtyRatio <= low && isThrottle) {
        isThrottle = false;
        return {
            needUpdate: true,
            speed: 150 * 8 * 1024
        };
    }
    else if ((dirtyRatio > low && isThrottle)) {
        if (Math.abs(lastSpeed - avgMBps) > 5) {
            lastSpeed = avgMBps;
            return {
                needUpdate: true,
                // 客户端内部对于 download_throttle_rate 这个字段的基本计量单位是 Kilobits per second (Kbps，千比特每秒)，而不是 Kilobytes per second (KB/s，千字节每秒)。
                speed: +(avgMBps - 5).toFixed(0) * 1024 * 8
            }
        }
    } else if (dirtyRatio > high) {
        if (Math.abs(lastSpeed - avgMBps) > 5) {
            lastSpeed = avgMBps;
            isThrottle = true;
            return {
                needUpdate: true,
                // 客户端内部对于 download_throttle_rate 这个字段的基本计量单位是 Kilobits per second (Kbps，千比特每秒)，而不是 Kilobytes per second (KB/s，千字节每秒)。
                speed: +(avgMBps - 5).toFixed(0) * 1024 * 8
            }
        }
    }
    return {
        needUpdate: false,
        speed: 0
    };
}

下载固件

OpenWrt 官方版本，所有的第三方版本都是基于官方的自定义编译，
immortalwrt 是针对国内用户编译的第三方版本，推荐优先使用。[GitHub]

点击 All Downloads

选择适配的 x86 版本

SquashFS 和 Ext4 是两种不同的文件系统，各自有不同的特点和应用场景：

• SquashFS 只读的文件系统，经过压缩后可以节省存储空间。默认情况下不支持直接写入，因此需要将可写数据放在单独的 Overlay 文件系统上。
• Ext4 一种常用的可读写文件系统，支持动态修改。

由于 OpenWrt 并不会将所有硬盘剩余空间作为根路径，因此不同的文件格式对应不同的磁盘组成，在安装后需要对根分区扩容。

• Ext4: /boot + /根分区(读写) + 剩余未分区磁盘
• SquashFS： /boot + /rom(只读) + /根分区(读写) + 剩余未分区磁盘 (优先选择此版本，方便迁移和系统恢复)

安装

参考官方安装文档，采用写入镜像文件方式，由于 OpenWrt 没有提供安装引导，所以需要用 微 PE 或 老毛桃[https://www.laomaotao.net/] 等工具制作一个 WinPE 启动盘, 将用到的固件，和固件写入工具保存到启动盘中，当进入 WinPE 系统后是用写入工具写入镜像。

Windows Preinstallation Environment（Windows PE），Windows 预安装环境，是带有有限服务的最小 Win32 子系统，基于以完整 Windows 环境或者保护模式运行的 Windows 3.x 及以上内核。这类系统一般很小。它包括了运行 Windows 安装程序及脚本、连接网络共享、自动化基本过程以及执行硬件验证所需的最小功能。

另外需要下载一个镜像写入工具 Win32 Disk Imager 或 balenaEtcher

将镜像写入工具, 解压出的 OpenWrt 镜像(.iso)文件, 复制到制作好的 WinPE 启动 U 盘中。

将 U 盘插入到软路由中(软路由需要接上鼠标，键盘，显示器)，开机时入到软路由的 BIOS，将默认的固态硬盘启动改为 U 盘启动。

保存重启后，进入 WinPE 系统，首先使用 WinPE 自带的 DiskGenius 工具，删除软路由硬盘的所有分区并保存。打开写入工具，选择磁盘和镜像并写入。

写入成功后，重启系统再次进入 BIOS,将 U 盘启动修改回硬盘启动，保存并再次重启。

启动成功后，会看见有命令行信息，如果卡住不动，尝试按一下回车键，这样会进入 OpenWrt 系统。

首次登录提示修改密码，执行 passwd 命令，修改 root 账户密码，此密码也是网页登录的密码。

修改网络配置信息，执行命令 vi /etc/config/network,

将 config device 的 list_ports 修改为 eth1
将 interface lan 的 option ipaddr 修改为内网不会冲突的 IP 地址例如 192.168.100.1 或 10.10.0.1
将 interface wan 和 interface wan6 的 option device 修改为 eth0

wan 口表示外网，也就是网络运营商的网线，通常更习惯将第一个网口作为插入外网网线，后面插入的都是内网设备，这样更有条理性

保存后重启设备,访问前需要重新连接一下设备：

• 软路由插入电源并开机
• 运营商光猫的网线，链接到软路由的 eth0 网口。
• wifi 路由器需要在管理后台，设置为 AP 有线中继模式，用一个网线将软路由的 eth1 网口，链接到路由器的第一个网口。
• 其他内网设备可以通过网线连接软路由或路由器，也可以直接通过 wifi 网络链接.

这是虽然不能上网，单已经可以通过内网中其他设备访问 /etc/config/network 中设置的 lan 口的 ipaddr 访问到 OpenWrt 的 UI 界面。

pve 虚拟机安装

上传镜像文件到 pve， 创建虚拟机， 删除虚拟机的默认磁盘

1
2
3

qm importdisk [虚拟机ID] [镜像路径] [磁盘]

qm importdisk 4444 /var/lib/vz/template/iso/immortalwrt-24.10.3-x86-64-generic-squashfs-combined-efi__1_.img storage

虚拟机 => 硬件 添加未启用的磁盘
虚拟机 => 选线 修改刚刚添加的磁盘为第一启动项

wan 口配置

最先的配置一定是软路由可以上网，输入账号密码进入到软路由的 UI 界面，点击菜单 网络 => 接口 点击 wan 口的编辑按钮，协议切换为 PPPoE ，输入账号密码，即可上网。

此方式是通过 PPPoE 拨号上网，需要致电运营商，将网络改为桥接模式，并提供账号密码。

lan 口配置

网络 => 接口 => 设备 选择 br_lan, 在网桥端口中将其他的端口都添加到 br_lan 这个网桥中，方便让局域网中的设备互相访问

磁盘扩容

在菜单 状态 => 概览 中可以看到，磁盘空间只有几百 M, 这是因为 OpenWrt 默认不会将剩余空间作为根节点。

官方 openwrt 参考 官方的扩容操作

immortalwrt 在安装前可以使用以下命令修改镜像的分区大小

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

# 将镜像文件扩容
dd if=/dev/zero bs=1M count=98304 >> immortalwrt-24.10.3-x86-64-generic-squashfs-combined-efi__1_.img

# 使用parted扩容文件系统

parted immortalwrt-24.10.3-x86-64-generic-squashfs-combined-efi__1_.img
GNU Parted 3.5
Using /var/lib/vz/template/iso/immortalwrt-24.10.3-x86-64-generic-squashfs-combined-efi__1_.img
Welcome to GNU Parted! Type 'help' to view a list of commands.
(parted) p
Error: The backup GPT table is corrupt, but the primary appears OK, so that will be used.
OK/Cancel? OK
Warning: Not all of the space available to
/var/lib/vz/template/iso/immortalwrt-24.10.3-x86-64-generic-squashfs-combined-efi__1_.img appears to be used, you can fix the GPT
to use all of the space (an extra 30 blocks) or continue with the current setting?
Fix/Ignore? Fix
Model:  (file)
Disk /var/lib/vz/template/iso/immortalwrt-24.10.3-x86-64-generic-squashfs-combined-efi__1_.img: 348MB
Sector size (logical/physical): 512B/512B
Partition Table: gpt
Disk Flags:

Number  Start   End     Size    File system  Name  Flags
128     17.4kB  262kB   245kB                      bios_grub
 1      262kB   33.8MB  33.6MB  fat16              legacy_boot
 2      33.8MB  348MB   315MB

(parted) resizepart 2 100%
(parted) q

immortalwrt 也可以安装后扩容

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
41
42
43
44

opkg update

opkg install fdisk lsblk losetup f2fs-toolsopkg install lsblk fdisk resize2fs losetup blkid f2fs-tools tree

# 查看磁盘信息
# df -h
# fdisk -l

# 替换为自己的磁盘
fdisk /dev/sda

# 查看磁盘
Command (m for help): p

Device         Boot  Start    End Sectors  Size Id Type
/dev/sda1            65536  98303   32768   16M 83 Linux
/dev/sda2            131072 745471  614400  300M 83 Linux

# 删除
Command (m for help): d
Partition number (1,2, default 2): 2

Partition 2 has been deleted.

# 新建磁盘 需要注意 sector 起始位置一定要与原有磁盘信息中 start 大小相同
Command (m for help): n
Partition type
   p   primary (1 primary, 0 extended, 3 free)
   e   extended (container for logical partitions)
Select (default p): p
Partition number (2-4, default 2): 2
First sector (2048-31268863, default 2048): 131072
Last sector, +/-sectors or +/-size{K,M,G,T,P} (131072-31268863, default 31268863):

Created a new partition 2 of type 'Linux' and of size 14.8 GiB.
Partition #2 contains a squashfs signature.


# 一定要选 n ，不要修改标识符
Do you want to remove the signature? [Y]es/[N]o: n

# 保存
Command (m for help): w
The partition table has been altered.