正则表达式-引擎

对正则表达式的表象有了一定了解之后，我们其实对正则表达式的引擎原理是有一定猜测的，不过具体引擎是否是按我们猜想的那样运行，在我们深入了解之前肯定会发现自己有时构造的表达式与引擎执行的结果存在偏差，这就需要我们去挖掘表达式背后的英雄：引擎

引擎的分类

现在基本所有的文字编辑软件都会包含正则表达式的功能，但是不同的编辑器所使用的引擎实现原理是不一样的，现在大家用的有三种引擎：

• DFA (deterministic finite automation)
• NFA (Non-deterministic finite automation)
  • traditional NFA
  • POSIX NFA

预备知识-有限状态自动机

有限状态自动机(Finite state machine)表示有限个状态以及在状态之间转换和动作等行为的模型

有限状态自动机包含初始态，转换态和终态，当字符串匹配到达终态时匹配成功，未达到终态则是匹配失败，每个状态后续都是唯一确定的，我们使用状态转移图来表示：

有限状态机是不满足正则表达式引擎的要求的，因为正则表达式对应有分支，状态可能会存在多个等情况，所以延伸出了以下两种引擎

DFA

DFA是确定性有限自动机，它会先扫描表达式，将表达式编译成内部形式，然后在读入字符后状态可以到达多个，DFA记录所有可能的状态，线性的向后处理。但因为DFA只含有有限多个状态，所以不支持反向引用，不可以捕获表达式，但相对NFA来说，DFA的速度是稳定的，对于一些简单场景来说是足够了。

举例说明：对于正则表达式ac|ad|adc|ea,我们假设匹配adc,首先读入字符a, DFA记录后续可能的状态ac,ab,adc,ea不符合直接抛弃，读入字符d, 状态变换为ad,adc, 此时ad已经到达最终态，是一个可能的匹配，记录下来，然后读入c,只剩下adc,也到达最终态，DFA在默认情况下会匹配最长的串，所以匹配结果会是adc,作为对比，传统型NFA会匹配ad,POSIX NFA匹配结果是adc,后面来看他们的差异原因。

NFA

NFA不会像DFA记录所有的状态，它只会记录中间状态。其实与其将NFA看作有穷自动机，不如将NFA看作一棵树，NFA使用深度优先遍历的方式来向下匹配，匹配到叶子节点就完成一次匹配，匹配不成功就回溯到上一个节点，继续对未访问过的子节点进行匹配。

我们从关键概念入手来了解

传动

引擎会从字符串开始进行匹配，如果匹配不成功，则向后移动一个字符，再进行匹配，这个过程就是传动。

回溯

引擎需要匹配完所有路径才能报告匹配失败，在这个过程中，一条路径匹配不成功需要回溯到上一个节点继续其他为匹配的路径，这个过程叫回溯。

捕获、分组与反向引用

在正则里面，捕获跟分组是两个功能，不过捕获必须会有分组功能，分组可以不捕获。

正常的括号()包含捕获和分组的功能，也就是说可以使用\1 \2的方式来引用括号中匹配到的内容，但是捕获是需要记录状态的，在回溯时还需要更改状态，对效率有一定损失，如果对捕获的内容不再使用的话，可以使用非捕获分组(?:)，这样就可以只使用分组功能。

反向引用与捕获是一对，前面捕获了后面才能使用反向引用，就是一个记录与使用的过程。

譬如我们要查找连续两个字母，我们可以使用(\w)\1

ps: 反向引用1/2/3的计数是按照左括号的计数位置来确定的，((\w)\w)(\d),这个表达式\1引用的是(\w)\w,\2引用的是\w,\3引用的是\d

占有字符和零宽度

看下面这张图：

一个有n个字符的字符串含有n+1个位置，^a正则中，^匹配了开始位置0，a是占有字符

前面我们使用的环视就是一个零宽度的位置匹配，它并不占有实际字符，只是作为一个条件。实际上零宽度是需要窥探后面或前面的字符的，只是他们在使用完之后又交还给引擎，并不占有这些字符。

贪婪匹配

正则引擎默认是使用贪婪的模式来匹配字符的，也就是说ab*b匹配abbbbb时，匹配结果为abbbbb,在遇到b时，会首先由b*来匹配，一直到结尾不能匹配再向后匹配，发现是b,而结尾与b不能匹配，于是回溯到最后一个b,匹配成功。

我们可以在量词后加问号?来提示使用非贪婪匹配，也就是说先匹配后面的，再来匹配自己，上面例子匹配结果就是ab。可以看出来贪婪匹配跟非贪婪匹配对于引擎来说就是一个先走哪个分支的问题，对我们来说匹配的结果差异是很大的。

占有优先与固化分组

在回溯中我们看到，如果后续的字符或模式不能匹配时，需要到回溯到上一个字符处继续匹配，这种情形我们说前面匹配的模式交还了一个字符，也就是说已经吃进去的字符再吐出来，这种情形下在遇到不匹配的模式时会一直重复吃-吐，会造成很大的浪费。

占有优先匹配是固化分组的一个简便表示方式，固化分组可以将已经匹配的字符固定在自己这里，回溯的时候不会往外吐字符，而是会直接匹配失败，这在我们对匹配模式有清晰了解，确定不需要回溯时候使用，可以提高匹配效率，在不符合模式的时候尽快报告失败。

例子：假设我们要匹配email，按照前面写的简单模式[-0-9a-zA-Z_]+@\w+(\.\w+)+,假设要匹配的字符串为This_is_a_unmatch_test,很显然这个不符合我们的email模式，[-0-9a-zA-Z_]+会一直匹配到结尾的t，然后发现结束符不能匹配，交给后续的模式匹配，@也不能匹配，于是[-0-9a-zA-Z_]+模式会把匹配到的t吐出来，@还不能匹配，继续吐(回溯),直到开头，然后引擎传动一个字符，再由h重复上述过程。

可以看到我们浪费了很多尝试的机会，因为在@不能匹配后，[-0-9a-zA-Z_]+里匹配到的字符是怎么也不会有@的，所以这里的回溯是没有价值的，是浪费的。我们可以使用占有优先量词或者固化分组来让[-0-9a-zA-Z_]+匹配的字符据为己有，回溯时不往外吐字符，而是直接报告失败。最后写成[-0-9a-zA-Z_]++@\w+(\.\w+)+，有+变成了++

NFA总结

NFA使用了复杂的技术来匹配我们写的表达式，这就需要我们对引擎的实现有一定了解，上面给出了NFA引擎中重要的概念，理解了他们我们对以后写出来的正则会更有信心

现在一般编程语言中带有的正则表达式包都是NFA的，包括java，Perl，Python等的，因为NFA支持反向引用，捕获等强大的功能，是正则实现完备性不可或缺的。

POSIX NFA

POSIX NFA在NFA的基础上加了一个限制，就是要求返回的匹配结果需要是最长匹配结果，也就是说POSIX NFA引擎会尝试所有分支，返回最长匹配的结果。在大部分情况下，POSIX NFA比NFA的效率要低很多，毕竟要把所有的可能都计算出来，再比较然后返回最长的。