匹配原理1、有穷自动机2、正则表达式的匹配过程3、回溯4、NFA和DFA1、有穷自动机正则表达式能迅速进行复杂处理的秘密在于它采用了一种特殊的理论模型有穷自动机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、回溯比起DFANFA看起来足够“麻烦”​它的状态是不确定的这有点像走迷宫越走岔路口越多最后不会迷路吗不过NFA的正则引擎自有办法如果有多个可能的状态它们会在选择时记录下这些状态备用然后才选择其中某个状态尝试如果之后遇到死路则退回去选择最近一次记录的且未尝试过的状态如果又遇到死路再选择最近一次记录的且未尝试过的状态……这有点像在分岔路口留下标记—如果我们在遇到的每个分岔路口都留下标记即便前头是死路也可以根据标记返回而不会迷路。为了说明NFA的匹配过程来看在之前举过的双引号字符串匹配的例子所用的正则表达式是.*而字符串是quoted string匹配的过程如图所示。从上图中可以看出在匹配的过程中.*曾经匹配了quoted string但为了保证表达式中最后一个的匹配.*不得不“交还”最后的这种“尝试失败-重新选择”的过程就是回溯backtracking​。回溯只属于NFA引擎。从之前的原理图中可以看到NFA匹配时正则引擎并不准确知道当前的状态只能在所有状态不确定的地方将各种状态都保存下来现在已经匹配了哪些字符进行到字符串中的哪个位置正则表达式中的哪个位置​逐一尝试发现此路不通则退回来选择最近保存的其他状态尝试……如此持续进行下去直到达到最终状态这时候报告“在整个正则表达式开始尝试的位置匹配成功”​​或者所有可能状态都尝试完毕仍然不能到达最终状态如果当前位置是字符串的末尾则报告“在当前位置匹配失败”​否则把“整个正则表达式开始尝试的位置”向前推进一个字符再开始新一轮的尝试​。看到这里就不难明白为什么不推荐使用.*了因为.几乎能匹配任何字符串如果明确指定单行模式则确实能匹配任何字符​而*又表示“匹配优先”​所以正则引擎在处理.*后的其他元素之前会先让.*“吞掉”几乎整个字符串。仍然是上面的正则表达式只是字符串变为quotedstring回溯的次数大大增加了如果在结尾的之后还有很长的文本回溯的次数还可能大大增加匹配过程如图所示。为避免这类问题最好的办法是准确表达意图比如规定双引号字符串内部不允许出现双引号字符就要将表达式改为[^]*当然也可以换用忽略优先量词将表达式改为.*?两种办法都可行。​不过总的经验是除非确实必要否则尽量不要使用.*。要注意的不仅仅有.*还有更糟的情况比如(…*)*之类的表达式这时候回溯的次数会呈指数增长却不会对匹配有任何影响所以应该绝对避免。之前文章中匹配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又有传统型NFATraditional NFA和POSIX NFA两种。两者的主要区别在于如果多选分支中的多个分支都能匹配传统型NFA优先选择左侧的分支而POSIX NFA一定要选择最长的分支。比如用表达式(jeff|jeffrey)匹配字符串jeffreyPOSIX NFA的结果是jeffrey传统型NFA的结果则是jeff—如果调换多选分支的顺序写成(jeffrey|jeff)POSIX NFA的结果不变传统型NFA的结果则变为jeffrey。问题看起来很复杂具体使用起来其实比较简单POSIXNFA的应用很少主要用于Linux/UNIX下的工具所以它们中的很多并不支持捕获分组​编程语言基本都采用传统型NFA引擎。保险起见不妨这样记忆一般情况下多选分支优先采用最左侧的分支。这一点务必要熟记使用多选结构进行正则表达式 操作时很可能因为多选结构的顺序问题得到不同的结果。