前言

我们先从一个很经典的正则问题来看：

/^(a*)*$/.test('aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab')

这个看似简单的正则表达式，在目前的任何一台计算机上恐怕都要跑上一年。原因很简单，因为使用了贪婪匹配，导致了不断的回溯。事实上被测试字符串每多出一个a，整体的执行时间就会翻倍。

要深入理解这个问题，需要从正则语言谈起，这个是《形式语言与自动机》的范畴，我们简单了解一下。

语言

所谓语言，指的是建立在一个字母表∑上的符合某个规则的字符串的集合。比如我们设计一个如下语言L，它的字母表是{'a', 'b'}，它必须满足以下条件：

• a 不能出现在b之后
• b出现且仅出现一次

那么L包含的字符串可以枚举为：{'b', 'ab', 'aab', ...}。

我们可以看出，语言是一种可数集。在这个定义基础上，我们可以定义对语言的运算，比如交，*并，补*等集合运算，以及连接，和最重要的：克莱尼闭包。

两个语言的连接定义为：两个语言所有字符串的叉积，并进行字符串连接，得到的新集合。比如：L1定义为{'a', 'b'}，L2定义为{'c', 'd'}，则L1L2定义为{'ac', 'ad', 'bc', 'bd'}。

很容易地我们可以得出语言的结合律：(L1L2)L3 = L1(L2L3)，我们可以简写为L1L2L3。

一个语言的幂定义为：语言与自身连接若干次，例如L^3 = LLL。这里我们需要定义：对任何语言，L^0 = {ε}，其中ε代表空字符串。

克莱尼星号（或者克莱尼闭包）是一个针对语言的单目运算符，一个语言的克莱尼闭包定义为：L* = {ε} ∪ L ∪ LL ∪ LLL ∪ ...，即L的0到正无穷次幂的并集。对于语言L = {'a'}，我们有：L*={ε, 'a', 'aa', 'aaa', ...}。

我们还可以定义加号运算符+：L+ = LL* = L*L，对L = {'a'}，我们有：L+={'a', 'aa', 'aaa', ...}。

正则语言

有了上述的语言及其上面的运算的知识，我们就可以定义正则语言了：所谓正则语言，就是可以由有限个规则描述的语言，或者说，有限的语言，或者由若干个有限语言通过有限次连接，幂，克莱尼星号，加号等运算符得到的语言。例如上述的语言{'b', 'ab', 'aab', ...}，可以描述为语言L1 = {'b'}和L2 = {'a'}的运算：L = (L2*) L1。

由此我们可以得出以下定律：

• 有限语言是正则语言。因为可以通过枚举的方式来描述该语言
• 正则语言有可能不是有限语言。因为存在克莱尼闭包等运算

正则表达式与自动机

正则表达式就是正则语言的表述形式，通过对语言的字符串集合和语言的运算进行描述，来描述正则语言的实现过程。比如L = (L2*) L1，可以描述为a*b。

在实际工程实现中，正则表达式是和自动机相关联的，每一个正则表达式可以根据其代表的正则语言实现的过程构造一个自动机。比如正则表达式Mon|Tue，可以描述为以下的确定有限状态自动机 (DFA)：

1. 开始
2. 如果匹配M，进入3；如果匹配T，进入4；否则匹配失败
3. 如果匹配o，进入5；否则匹配失败
4. 如果匹配u，进入6；否则匹配失败
5. 如果匹配n，匹配成功；否则匹配失败
6. 如果匹配e，匹配成功；否则匹配失败

上面的例子比较简单，因为对于每一个输入符号都有确定的下一个状态。如果我们将正则表达式扩展为Mon|Tue|Wed|Thu，那么我们对于第一个字符为T的输入，有两种处理方式：

1. 进入一个特殊状态，这个状态下根据下一个字符是u还是h选择进入另一个状态
2. 对输入T，给定两个不同的状态，它们都有可能被进入

看起来方案一更好理解，而且实现更容易，因为它的对任何输入的下一个状态是确定的，就是说它是一个DFA。而对于方案二，如果进入某一个状态后发现匹配失败，有可能不是因为输入不对，而是最初进入的状态不对，所以就需要引入回溯：将已处理的字符串吐出来，并回到有分支的状态，尝试另一种可能性。这种带有不确定的状态转移的自动机叫做非确定有限状态自动机 (NFA)。

看起来，DFA比NFA更容易理解和实现，而且理论证明，DFA和NFA的计算能力是等价的，即任何NFA都能转换为DFA，它们都能表达任何正则语言。那么为什么我们还需要NFA呢？

因为NFA到DFA的转换的复杂度是指数增长的。考虑上面的例子，我们看到对字母T我们有两个分支，如果字母T下方继续存在两个分支的话，转换为DFA的状态个数不是加法，而是乘法。所以实际应用中有时候我们的确需要利用回溯来实现正则表达式。

正则表达式与回溯

回溯的引入使得正则表达式运行过程中状态转移变幻莫测，比如(a*)*对‘aaaa’的匹配，可以有以下几种符合条件的分支：

• aaaa
• aaa + a
• aa + aa
• aa + a + a
• a + aaa
• a + aa + a
• a + a + aa
• a + a + a + a

而当输入字符串位数增加时，分支条数急剧增加。所以，嵌套使用克莱尼星号是回溯地狱的常见原因。

当然，不嵌套使用克莱尼星号，问题就解决了么？没有，比如这个正则表达式: (a|aa|aaa|aaaa)*，对上述字符串输入，有同样的效果。所以，多个分支条件嵌套克莱尼星号是回溯地狱的另一个常见原因。

那么怎么化解这种尴尬境况呢？当然就是设法避免这两种类型的回溯。首先根据克莱尼星号的特性，我们很容易得出以下结论：

(L*)* === (L+)* === (L*)+ === L*
(L+)+ === L+

即对于常见的嵌套情况，都可以进行化简。

另一个方面就是减少使用复杂的分支，以及避免复杂的分支和重复操作符的嵌套使用。在可能出现复杂分支和重复的情况中，通过合理规划抽取公共匹配部分（比如因为aaaa是aaa和a的结合，它没有必要出现在表达式中）来减少分支的个数和长度。