正则指引——匹配原理

1、有穷自动机

正则表达式能迅速进行复杂处理的秘密在于，它采用了一种特殊的理论模型：有穷自动机（Finite Automata，也叫有穷状态自动机，finite-state machine）​。这种机器具备有限个状态，可以根据不同的条件在状态之间转移。

卖饮料的自动售货机就是一种有穷自动机：假设其中的饮料价格都是整数元，而且只接收5块钱的纸币，根据余额的不同，可能状态有6个：5元、4元、3元、2元、1元、0元。你塞进去5块钱，此时的状态就是“5元”​，你点了一罐可乐，花去3元，于是状态切换到“2元”​，这时候你按下“退币”​，就把剩下的2元退给你，并把状态切换到“0元”​，​“0元”这个状态也叫作“最终状态”​。到此，这一轮状态转移结束，如果你再塞5块钱，就开始新一轮的状态转移。

严格说起来，有穷自动机必须满足4个条件：

• 具有有限多个状态；
• 有一套状态转移函数（或者叫“规则”​）​；
• 有一个开始状态；
• 有一个或多个最终状态。

我们说自动售货机是一种有穷自动机，就是因为它满足这4个条件：

• 具有有限多个状态（6个）​；
• 有一套状态转移函数（比如余额还有3元，你买了一罐2元的饮料，则转移到状态“1元”​，如果你选择买4元的饮料，则报告“余额不足”​，状态并不变化）​；
• 有一个开始状态（余额“5元”​）​；
• 有一个最终状态（余额“0元”​）​。

自动售货机对应的有穷自动机模型如图所示，它包含6个状态，对应余额的6种可能，起始状态是“￥5”​，结束状态是“￥0”​，每个箭头代表一个转移函数（每样商品的价格为1元或者2元，所以每个转移函数上的文字或者是-1，或者是-2）​，在￥4、￥3、￥2、￥1状态下，都可以直接退币，所以有一个转移函数直达最终状态。

自动售货机并不关心你买了什么商品，也不关心你的选择顺序，无论你买什么，它总处在这6个状态之一，只需要根据状态转移函数在其中转移即可。

2、正则表达式的匹配过程

正则表达式所使用的理论模型就是有穷自动机，其具体实现称为正则引擎（Regex Engine）​。用正则表达式处理字符串，首先需要生成自动机（你应该还记得，很多语言中使用正则表达式之前都要“编译”正则对象）​；之后，无论输入什么字符串，正则引擎都只需要老老实实地在状态之间游走。

下图显示了正则表达式a(bb)+a对应的自动机。这台自动机的表示与之前看到的稍有不同：在匹配字符串时，输入的都是字符，所以箭头上标注的都是字符。

在这台有穷自动机中，S0、S1、…、S4是各个状态，S0为开始状态，S4为最终状态；转移函数很直观：比如当前状态是S0，输入字符a，则转移到S1；如果当前状态为S0，输入的不是a，那么直接退出。这也很好理解：如果正则表达式是a(bb)+a，它能匹配的字符串只能是以字符a开头的，否则必然不能匹配。

下图说明了这台有穷自动机对字符串abbbba的处理过程。

在经历了一系列的状态转移之后，字符串abbbba处理完毕，自动机停留在最终状态上，也就是说，字符串abbbba可以由正则表达式a(bb)+a匹配。

同一个正则表达式对应有穷自动机不止一台，可以是若干台，这些有穷自动机是等价的。同样是正则表达式a(bb)+a，它对应到下图所示的两台完全等价的有穷自动机。

仔细观察会发现，第二台自动机有些奇怪，在输入ab之后，再输入b，它所处的状态是不确定的：可能在S1，也可能在S3。但是，输入a(bb)+a能匹配的字符串，它确实可以抵达最终状态S4。下图所示的自动机看起来更加奇怪，而且它仍然是与a(bb)+a完全对应的。

在状态S3，即便没有输入任何字符，也不会停留下来，而可能“凭空”转义到S1。也就是说，在某个时刻，自动机到底处在状态S3，还是S1，这是不确定的！但是这种不确定性，并不会影响自动机对于正则表达式a(bb)+a的匹配。也就是说，这台有穷自动机与之前的两台有穷自动机，也是完全等价的！

根据状态的确定与否，一般我们会把有穷自动机（正则引擎）分为两类：

• 一类是确定型有穷自动机（DefiniteFinite Automata，简称DFA）​，在任何时刻，它所处的状态是确定无疑的；
• 另一类是非确定型有穷自动机（Non-definite Finite Automata，简称NFA）​，在某个 时刻，它所处的状态可能是不确定的。

下图把上面的三台自动机做了分类，第一台是DFA，而另两台是NFA。

可以证明，DFA和NFA之间存在等价关系。也就是说，每一台DFA都可以等价转换为一台NFA，反过来也成立。

比较正则表达式a(bb)+a和这三台自动机，会发现NFA构造起来更直观，实际上这是普遍规律：从正则表达式出发，构造NFA的难度要小于DFA。但是正如之前讲过的，DFA在任意时刻必定处于某个确定的状态，而NFA可能处于若干状态之中的任何一个，所以，如果使用NFA，就必须保存所有的可能的状态，并且在某种状态不可行时“回退”到之前保存的状态，这就是正则表达式匹配中的重要概念：回溯。

3、回溯

比起DFA，NFA看起来足够“麻烦”​：它的状态是不确定的，这有点像走迷宫，越走岔路口越多，最后不会迷路吗？

不过，NFA的正则引擎自有办法：如果有多个可能的状态，它们会在选择时记录下这些状态备用，然后才选择其中某个状态尝试；如果之后遇到死路，则退回去，选择最近一次记录的且未尝试过的状态；如果又遇到死路，再选择最近一次记录的且未尝试过的状态……这有点像在分岔路口留下标记—如果我们在遇到的每个分岔路口都留下标记，即便前头是死路，也可以根据标记返回，而不会迷路。

为了说明NFA的匹配过程，来看在之前举过的双引号字符串匹配的例子，所用的正则表达式是".*"，而字符串是"quoted string"，匹配的过程如图所示。

从上图中可以看出，在匹配的过程中，.*曾经匹配了quoted string，但为了保证表达式中最后一个"的匹配，.*不得不“交还”最后的"，这种“尝试失败-重新选择”的过程，就是回溯（backtracking）​。

回溯只属于NFA引擎。从之前的原理图中可以看到，NFA匹配时，正则引擎并不准确知道当前的状态，只能在所有状态不确定的地方将各种状态都保存下来（现在已经匹配了哪些字符，进行到字符串中的哪个位置，正则表达式中的哪个位置）​，逐一尝试，发现此路不通，则退回来，选择最近保存的其他状态尝试……如此持续进行下去，直到达到最终状态（这时候报告“在整个正则表达式开始尝试的位置，匹配成功”​）​；或者所有可能状态都尝试完毕，仍然不能到达最终状态（如果当前位置是字符串的末尾，则报告“在当前位置匹配失败”​；否则，把“整个正则表达式开始尝试的位置”向前推进一个字符，再开始新一轮的尝试）​。

看到这里，就不难明白为什么不推荐使用.*了，因为.几乎能匹配任何字符串（如果明确指定单行模式，则确实能匹配任何字符）​，而*又表示“匹配优先”​，所以正则引擎在处理.*后的其他元素之前，会先让.*“吞掉”几乎整个字符串。仍然是上面的正则表达式，只是字符串变为"quoted"string，回溯的次数大大增加了，如果在结尾的"之后还有很长的文本，回溯的次数还可能大大增加，匹配过程如图所示。

为避免这类问题，最好的办法是准确表达意图，比如规定双引号字符串内部不允许出现双引号字符，就要将表达式改为"[^"]*"；当然也可以换用忽略优先量词，将表达式改为".*?"，两种办法都可行。​不过总的经验是，除非确实必要，否则尽量不要使用.*。

要注意的不仅仅有.*，还有更糟的情况，比如(…*)*之类的表达式，这时候回溯的次数会呈指数增长，却不会对匹配有任何影响，所以应该绝对避免。之前文章中匹配HTMLtag的正则表达式是<('[^']*'|\"[^\"]*\"|[^'\">])+>，其中的多选分支[^'\">]没有添加量词*，就是因为单引号字符串和双引号字符串之外的字符虽然可能有很多，但多选结构最外层还有+限定，从忽略之前两个多选分支来看，([^'\">])+要好过([^'\">]*)+。

在实际应用中，不只要注意自己写的正则表达式，还需要防范外界的恶意程序，它们刻意使用会造成大量回溯的表达式，将计算机的资源消耗殆尽，这种攻击有一个专门的名词，叫作正则表达式拒绝服务攻击（RegularExpression Denial of Service）​。​

4、NFA和DFA

上一节粗略介绍了回溯，它是NFA特有的功能，DFA不需要回溯，也就不需要保存状态，再反复尝试。这样看来，NFA不是要更慢吗？事实也确实如此，但是当前我们所使用的大多数工具中的正则引擎，都选用了NFA，这是为什么呢？

NFA确实更慢，但NFA也有自己的优势：如果正则表达式比较复杂，构建NFA的时间比DFA的时间短（举例来说，如果你的正则表达式使用了多选分支，每个分支其实只是一个简单的字符串，那么完全可以直接对每个多选分支构建简单的NFA，再把它们简单“并列”起来就可以了；相比之下，构建整个表达式对应的DFA就复杂多了）​。

同时，现代NFA也提供了更多的优化措施，比如之前提到的a(bb)+a的匹配，优化过的NFA可以“并行尝试”​，其匹配过程如下图所示，这样的速度就快多了。

更重要的是，NFA的匹配性质决定了它必须在匹配过程中保存可能的状态，需要“停下来四处看看”​，所以也能够“回顾一路走来的历程”​；相比之下，DFA不会两次测试同一个字符，所以不需要保存状态。因此，NFA具有许多DFA无法提供的功能：比如捕获型括号(…)，反向引用\num，环视功能(?!…)、(?=…)，忽略优先量词+?、*?、??……

如果希望用到这些功能，一定不要选择使用DFA引擎的工具。当然一般来说，用户并不需要操心引擎是DFA或者NFA，毕竟它们是位于“幕后”的，需要关注的是，是否提供了希望实现功能所用到的API。

而且，在现代的一些工具中，为兼顾效率和功能，同时包含了DFA和NFA两种引擎，如果发现正则表达式中没有专属于NFA的功能，则使用DFA，否则使用NFA。下表列出了各种常用工具所使用的正则引擎。

细分起来，NFA又有传统型NFA（Traditional NFA）和POSIX NFA两种。两者的主要区别在于，如果多选分支中的多个分支都能匹配，传统型NFA优先选择左侧的分支，而POSIX NFA一定要选择最长的分支。

比如用表达式(jeff|jeffrey)匹配字符串jeffrey，POSIX NFA的结果是jeffrey，传统型NFA的结果则是jeff—如果调换多选分支的顺序，写成(jeffrey|jeff)，POSIX NFA的结果不变，传统型NFA的结果则变为jeffrey。

问题看起来很复杂，具体使用起来其实比较简单：POSIXNFA的应用很少，主要用于Linux/UNIX下的工具（所以它们中的很多并不支持捕获分组）​，编程语言基本都采用传统型NFA引擎。保险起见，不妨这样记忆：一般情况下，多选分支优先采用最左侧的分支。这一点务必要熟记：使用多选结构进行正则表达式 操作时，很可能因为多选结构的顺序问题得到不同的结果。