正则表达式引擎的实现

1. 前言

在计算机领域，正则表达式是名副其实的神器，它的诞生可以说直接推动了计算机软件的发展。至今它已被广泛应用于编译器、搜索引擎、文本处理等多个领域，并且在很多未知领域仍不断探索着可能。对于普通用户来说，熟练使用正则表达式可以有效提高我们的工作效率，提升我们的生活质量。然而，面对像天书一样的正则语法，很多人因此望而却步。本文将从正则表达式的原理讲起，让读者对正则表达式的语法有一个直观的印象。随后我们将自己动手构建一个正则引擎，加深对正则表达式的理解。

2. 什么是语言？

我们平时所说的语言是由语句构成的，每个语句是字符的某种组合。对于英语，这些字符取自字母表；对于中文，这些字符取自汉字表。无论是字母表还是汉字表，它们都是有限的字符集合，基于这些字符集合构成了形形色色的语言世界。我们可以进一步地抽象和概括出：语言是在给定字母表上的一个任意可数的字符串集合，其中给定的字母表是一个有限的符号集合，而字符串是字母表中符号的一个有限序列。例如，计算机指令是 {0, 1} 这样的二进制字母表上的有限序列，计算机语言就是这些计算机指令的集合。基于这种抽象，我们可以对语言做一些代数运算。在此之前，我们先来看看字符串的运算。

假设 x 和 y 都是字符串，x 和 y 的连接操作是将 y 附加到 x 上形成的字符串。例如，如果 x = “dog” 且 y = “house”，那么 xy = “doghouse”。假设 $\epsilon$ 是空串，那么对于任何字符串 s，都有 sε = εs = s。如果把两个字符串的连接视为这两个字符串的”乘积”，我们可以定义字符串的”指数”运算如下：定义 s⁰ 为 ε，且对于 i > 0，sⁱ 为 s^i-1s。因为 εs = s，故 s¹ = s，s² = ss，s³ = sss，依此类推。

语言的运算除了常见的集合运算外，还有连接运算和闭包运算。语言连接就是从第一个语言中选出一个串，从第二个语言中选出另一个串，然后将它们连接起来得到的全体串的集合。语言的闭包运算包括 Kleene 闭包和正闭包。语言 L 的 Kleene 闭包记作 L*，表示将 L 连接零次或多次得到的串集。L 的正闭包记作 L+，表示将 L 连接一次或多次得到的串集。下表给出了这些运算的形式化定义。

令 L 表示字母集合 {A, B, …, Z, a, b, c, …, z}，令 D 表示数字集合 {0, 1, …, 9}。利用上述介绍的运算，我们可以构造出新的语言。

• L ∪ D 是长度为 1 的串集，其中每个串要么是一个字母，要么是一个数字。
• LD 是长度为 2 的串集，其中每个串由一个字母后跟一个数字组成。
• L⁴ 是由 4 个字母组成的串集。
• L^* 是由字母组成的串集，包括空串 ε。
• L(L ∪ D)^* 是由字母开头，由字母和数字组成的串集。
• D⁺ 是由一个或多个数字组成的串集。

3. 正则表达式简介

为了更好地描述语言，人们通过使用正则表达式来表达语言，一个正则表达式就代表一类语言。从上面的描述我们知道，可以对语言进行代数运算构造出另一种语言。同理，可以对较小的正则表达式进行代数运算，得到一个更大的正则表达式。例如，假设 r 和 s 都是正则表达式，分别表示语言 L(r) 和 L(s)，通过对它们进行简单的并、连接和闭包运算，我们可以构造出更丰富的正则表达式。

• (r)|(s) 是一个正则表达式，表示语言 L(r) ∪ L(s)。
• (r)(s) 是一个正则表达式，表示语言 L(r)L(s)。
• (r)^* 是一个正则表达式，表示语言 (L(r))^*。
• (r) 是一个正则表达式，表示语言 L(r)。

同理，我们可以为这些运算符设置一些优先级，以便书写时节省一些不必要的括号。完整的符号优先级列表如下，其中红色的为已学过的基本运算符。那些未标红的是一些扩展运算符，它们存在主要是为了增强正则表达式的表达能力，后面我们将学习它们的含义。

依据运算符优先级的约定，我们可以将表达式 (a)|((b)*(c)) 重写为 a|b*c。这两个表达式描述的是同一个串集，但后者看起来要简洁得多。和其他数学运算符一样，正则表达式也遵循一些代数定律。通过了解这些定律我们可以知道不同形式的正则表达式也是可以等价的，因此它们描述的是同一种语言。下表列出了对于任意正则表达式 r、s、t 都成立的代数定律。

4. 正则表达式的扩展

我们可以通过将子表达式进行并、连接和闭包等基本运算来构造出很多有表达能力的正则表达式，但是还远远不能满足一些特殊的需求。于是，很多正则引擎在基本正则表达式的基础上增加了一些扩展运算符，它们用于增强正则表达式描述字符串模式的能力，具体如下：

除以上扩展运算符之外，多数正则实现还提供了一些常用的字符集简写，它们能让正则表达式变得更加简洁。下面是一些常见的简写：

5. 有限自动机

正则表达式是一种高度概括的表达方式，它能用简洁的语法描述出庞大的字符串集合，它的功能就是简化人们的编码工作。在计算机中，有限自动机用于描述形式化语言，它是事件驱动的状态转移图，具有与正则表达式同等的表达能力。有限自动机是一种抽象的数学模型，它能根据外部输入改变自身的状态，从而达到模拟和控制执行流程的目的。一个有限自动机由五部分组成，可以用一个五元组 (S, Σ, s, F, δ) 来表示，其中各部分含义如下：

• S：有限的状态集合。
• Σ：输入符号集合。
• s：初始状态。
• F：接受状态集合。
• δ：状态之间的转移函数集合。

例如，假设需要识别一个英文字符串是否包含”main”子字符串，可以用程序来模拟如下的有限自动机。

上图中是一个非常简单的有限自动机模型，它从初始状态 0 开始，不断读入下一个字符并进行状态转移。如果最终自动机能到达接受状态 4，说明输入的字符串中包含”main”子串，否则表示不包含该子串。这样的一个自动机同样由五部分组成，各部分具体含义如下：

• S：有限状态集 {0, 1, 2, 3, 4}。
• Σ：字母表 {a, b, c, …, z, A, B, C, …, Z}。
• s：初始状态 0。
• F：接受状态集 {4}。
• δ：状态转移函数集 {(0, m) → 1, (1, a) → 2, (2, i) → 3, (3, n) → 4}。

依据状态转移性质的不同，有限自动机（Finite Automata，FA）又分为不确定有限自动机（Nondeterministic Finite Automata，NFA）和确定有限自动机（Deterministic Finite Automata，DFA）。NFA 允许基于空串输入 $\epsilon$ 的状态转移，以及对于同一个输入字符允许转移到多个目标状态。DFA 在这些方面则有限制，不允许基于空串的状态转移，对于同一输入字符只能转移到一个目标状态。NFA 和 DFA 在表达能力上等价，任何 DFA 都是 NFA 的一种特例，任何 NFA 都可以被一个 DFA 所模拟。例如，下面的 NFA 和 DFA 描述的是同一个语言。

（1）能够识别模式 a(b|c)^* 的一个 NFA 如下图所示。

（2）能够识别模式 a(b|c)^* 的一个 DFA 如下图所示。

从上面两图可以看到，NFA 的状态转移是不确定的，而 DFA 的状态转移是确定的。对于机器而言，不确定性将产生大量的回溯，这就导致 NFA 的执行性能不如 DFA。另一方面，基于正则表达式直接构造 NFA 比直接构造 DFA 更简单且耗时更少，所以实际应用中需要结合场景使用 NFA 或 DFA。一般来说，对于需要多次复用的复杂正则表达式，直接将其编译成 DFA 来模拟效果会更好；而对于只使用几次的简单正则表达式，用 NFA 来模拟效果会更好。两者具体差异总结如下表。

6. Thompson 算法

我们上面讨论过复杂的正则表达式可以由简单的正则表达式通过并、连接和闭包等基本运算构造而来。Thompson 算法使用的正是这种归纳的思想，将一个正则表达式转换成一个等价的 NFA。该算法递归地将一个正则表达式划分为它的子表达式，在得到每个子表达式对应的 NFA 之后，根据子表达式之间的运算关系和一系列规则，构造出表达式自身对应的 NFA。下面介绍通过子表达式 NFA 构造自身 NFA 的运算规则。

6.1 最小 NFA 构造

假设 r₁ = ε，r₂ = a，表示 r₁ 的 NFA 如下图左边部分所示，表示 r₂ 的 NFA 如下图右边部分所示。这里空串 ε 和单个字符 ‘a’ 都是最小的正则表达式，所以无需继续递归。使用它们构造 NFA 的规则如下：创建一个新的开始状态 i 和一个接受状态 f，将这两个状态直接连接起来。标签可以是空串 ε，也可以是一个单独的字符。得到的 NFA 只有一个状态转移。

6.2 并运算

假设 r = s|t，r 的 NFA 记为 N(r)，如下图所示构建。其中 i 和 f 是两个新状态，分别表示 N(r) 的开始状态和接受状态。从 i 到 N(s) 和 N(t) 的开始状态各有一条 $\epsilon$ 转移，从 N(s) 和 N(t) 的接受状态到 f 也各有一条 $\epsilon$ 转移。请注意，N(s) 和 N(t) 的接受状态在 N(r) 中不再是接受状态。因为 N(r) 中任何从 i 到 f 的路径要么经过 N(s)，要么经过 N(t)，且进出 i 和 f 的 $\epsilon$ 转移不会改变路径上的标签。因此我们可以断定 N(r) 识别的串集为 L(s) $\cup$ L(t)。

6.3 连接运算

假设 r = st，r 的 NFA 记为 N(r)，如下图所示构建。N(s) 的开始状态变成了 N(r) 的开始状态。N(t) 的接受状态变成了 N(r) 唯一的接受状态。N(s) 的接受状态和 N(t) 的开始状态合并为一个状态，合并后的状态继承了原来进出合并状态的全部转移。一条从 i 到 f 的路径必须首先经过 N(s)，因此路径上的标签以 L(s) 中的某个串开头。然后，该路径继续经过 N(t)，因此路径上的标签以 L(t) 中的某个串结尾。所以，N(r) 识别的串恰好是 L(s)L(t)。

6.4 闭包运算

假设 r = s^*，r 的 NFA 记为 N(r)，如下图所示构建。其中 i 和 f 是两个新状态，分别表示 N(r) 的开始状态和接受状态。要从 i 到达 f，我们可以沿着新引入的标记为 $\epsilon$ 的路径前进，该路径对应 L(s)⁰ 中的一个串。我们也可以到达 N(s) 的开始状态，然后穿过该 NFA，再从其接受状态沿 $\epsilon$ 回到其开始状态，反复零次或多次。这些选项使得 N(r) 能够接受 L(s)¹、L(s)² 等集合中的所有串。因此，N(r) 识别的全部串集就是 L(s)^*。

7. 子集构造法

由于 NFA 的状态转移是不确定的，这主要是因为其支持基于空串的转移，并且一个输入字符可以到达多个目标状态。这会导致计算机在执行时产生大量回溯，严重影响执行性能。但由于从正则表达式构造 NFA 比直接构造 DFA 更简单，因此 NFA 适用于正则表达式简单且仅使用一两次的场景，比如 Linux 中的 grep 命令。而对于希望多次复用同一个正则表达式的场景，还是将其转换为 DFA 更可靠。下面介绍的”子集构造法”就是用于将 NFA 转换成等价 DFA 的算法。

7.1 算法原理

子集构造法的步骤如下：

1. 首先，根据 NFA 的初始状态，找到通过它经过 ε 能变换到的所有状态集合，将该集合标记为 q₀，并加入到集合 Q 中，此时 Q = { q₀ }。

2. 从集合 Q 中取出一个状态集合 q，遍历每个输入字符 c 执行以下操作：

   2.1 计算状态集合 q 中的每个状态在字符 c 下的状态转移，并将迁移后的状态收集为一个新集合。

   2.2 对新集合中的状态执行 ε 变换，生成一个全新的状态集合并加入 Q 中。

3. 持续执行下述操作，直到无法再往集合 Q 中加入新元素为止，然后退出循环操作。

4. 将 Q 中的每个状态集映射为一个 DFA 状态，将包含 NFA 初始状态的那个集合标记为 DFA 的初始状态，将包含 NFA 结束状态的那个集合标记为 DFA 的结束状态，将 Q 中元素的转移关系映射为 DFA 的状态转移关系。

下面用伪代码来表达：

q0 = ε-closure(s0);
Q = {q0};
T = [[]]
while Q is not empty do:
	get q from Q and remove it;
	for each input charcter c:
		t = ε-closure(move(q, c));
		T[q, c] = t;
		if t not in Q then:
			append t to Q;
	end;
end;

上面的代码中涉及的三个操作定义如下：

7.2 算法示例

以正则表达式 (a|b)^*abb 为例，它的 NFA 如下图所示。

第 0 步：由于 NFA 的初始状态是 0，因此初始状态集是 ε-closure(0) = {0, 1, 2, 4, 7}，将该集合标记为 A，并加入到集合 Q 中，此时 Q = {A}。

第 1 步：从 Q 中取出集合 A，分别求输入符号 a 和 b 时的状态集：

ε-closure(move(A, a)) = {1, 2, 3, 4, 6, 7, 8}，将该集合标记为 B 并加入 Q 中，此时 Q = { B }。

ε-closure(move(A, b)) = {1, 2, 4, 5, 6, 7}，将该集合标记为 C 并加入 Q 中，此时 Q = {B, C}。

第 2 步：从 Q 中取出集合 B，分别求输入符号 a 和 b 时的状态集：

ε-closure(move(B, a)) = {1, 2, 3, 4, 6, 7, 8}，该集合为 B，此次不加入 Q 中，所以 Q = { C }。

ε-closure(move(B, b)) = {1, 2, 4, 5, 6, 7, 9}，将该集合标记为 D 并加入 Q 中，此时 Q = {C, D}。

第 3 步：从 Q 中取出集合 C，分别求输入符号 a 和 b 时的状态集：

ε-closure(move(C, a)) = {1, 2, 3, 4, 6, 7, 8}，该集合为 B，此次不加入 Q 中，所以 Q = { D }。

ε-closure(move(C, b)) = {1, 2, 4, 5, 6, 7}，该集合为 C，此次不加入 Q 中，所以 Q = { D }。

第 4 步：从 Q 中取出集合 D，分别求输入符号 a 和 b 时的状态集：

ε-closure(move(D, a)) = {1, 2, 3, 4, 6, 7, 8}，该集合为 B，此次不加入 Q 中，所以 Q = {}。

ε-closure(move(D, b)) = {1, 2, 4, 5, 6, 7, 10}，将该集合标记为 E 并加入 Q 中，此时 Q = { E }。

第 5 步：从 Q 中取出集合 E，分别求输入符号 a 和 b 时的状态集：

ε-closure(move(E, a)) = {1, 2, 3, 4, 6, 7, 8}，该集合为 B，此次不加入 Q 中，所以 Q = {}。

ε-closure(move(E, b)) = {1, 2, 4, 5, 6, 7}，该集合为 C，此次不加入 Q 中，所以 Q = {}。

第 6 步：由于集合中 Q 没有新的状态可加入，因此循环结束，新的状态转移表如下：

第 7 步：依据上面的状态转移表生成的 DFA 如下：

8. Hopcroft 算法

通过子集构造法将 NFA 转换到 DFA 后，通常会有很多冗余的状态，这导致 DFA 不够精简。为提升计算机模拟执行的效率，可以使用 Hopcroft 算法对 DFA 的状态进行最小化。下面将介绍该算法的工作原理。

8.1 算法原理

Hopcroft 算法的主要思想基于等价类的概念，其核心思想是：如果两个状态在接收任何输入字符时表现出相同的行为，那么它们就是等价的，可以合并为一个等价类。以下是算法的整体流程描述：

1. 首先，将状态初始划分为接受状态和非接受状态。

2. 重复细化划分：

   2.1 如果划分 p 中包含这样的状态——它们在符号 s 上转移到不同的后继划分。

   2.2 将 p 拆分为新的子划分，使得每个子划分中的全部状态在 s 上转移到相同的后继划分。

3. 重复细化直到达到不动点（无法再进一步细化）。

4. 最后，通过将属于同一等价类的状态合并为一个状态，创建新的最小化 DFA。

下面用伪代码来表达：

T = {AcceptStates, NonAcceptStates};
P = {};
while (P != T) do:
	P = T;
	T = P;
	for each set S in P do:
		T = T ∪ Split(S);
	end;
end;
	
Split(S):
	for each input charcter c:
		if c splits S into s1 and s2:
			return {s1, s2};
	end;
	return S

8.2 算法示例

以下面的 DFA 为例，左侧是 DFA 状态图，右侧是状态转移表。

第 0 步：首先将状态划分为非接受状态 {A, B, C, D} 和接受状态 {E}，分别记为 S0 和 S1。

第 1 步：由于 S1 只包含一个状态，无法进一步划分。我们继续对集合 S0 进行划分。

第 2 步：根据图示，我们可以观察到状态 A、B、C 在输入 0 和 1 时都转移到 S0，而状态 D 仅在输入 1 时转移到 S1。我们将 {A, B, C, D} 划分为 {A, B, C} 和 {D}，形成等价类集合 P1。

第 3 步：根据图示，状态 A 和 C 在输入 0 和 1 时都转移到 S0，而状态 B 仅在输入 1 时转移到 S1。我们将 {A, B, C} 划分为 {A, C} 和 {B}，得到等价类集合 P2。

第 4 步：通过检查图表，我们发现状态 A 和 C 在输入 0 和 1 时的后继状态完全相同。因此，我们不再对集合 {A, C} 进行划分。此时所有等价类都无法再进一步划分。最终的等价类集合为 P3 = {{A, C}, {B}, {D}, {E}}。

第 5 步：最后，我们将每个等价类中的状态合并，得到对应的最小化 DFA 如图所示。

9. 总结

本文介绍了正则表达式的基本概念，以及如何通过并、连接和闭包等基本运算构造出复杂的正则表达式。我们还详细讲述了使用 Thompson 算法将正则表达式转换为 NFA 形式。然而，由于 NFA 中存在不确定性（如空转移等），可能会导致回溯问题。因此，我们使用子集构造法将 NFA 转换为 DFA，并使用 Hopcroft 算法对 DFA 进行状态最小化，以提高状态机的运行效率。这些算法的应用使我们能够构建一个高效而简洁的正则表达式引擎。通过深入理解正则表达式的基本原理，我们以后在正则表达式的使用上必将更加得心应手。