正则引擎中的有限自动机 ① 正则历史和语法

正则的历史

斯蒂芬·克莱恩 (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 极其冗长，而正则表达式提供了极致简练的等价记号。