這一篇就重點講解正則表達式的核心——正則引擎。
1、正則引擎
正則引擎主要可以分為基本不同的兩大類：一種是DFA（確定型有窮自動機），另一種是NFA（不確定型有窮自動機）。DFA和NFA都有很長的歷史，不過NFA的歷史更長一些。使用NFA的工具包括.NET、PHP、Ruby、Perl、Python、GNU Emacs、ed、sec、vi、grep的多數(shù)版本，甚至還有某些版本的egrep和awk。而采用DFA的工具主要有egrep、awk、lex和flex。也有一些系統(tǒng)采用了混合引擎，它們會根據(jù)任務的不同選擇合適的引擎（甚至對同一表達式中的不同部分采用不同的引擎，以求得功能與速度之間的平衡）
NFA和DFA都發(fā)展了很多年了，產(chǎn)生了許多不必要的變體，結(jié)果，現(xiàn)在的情況比較復雜。POSIX標準的出臺，就是為了規(guī)范這種現(xiàn)象，POSIX標準清楚地規(guī)定了引擎中應該支持的元字符和特性。除開表面細節(jié)不談，DFA已經(jīng)符合新的標準，但是NFA風格的結(jié)果卻與此不一，所以NFA需要修改才能符合標準。這樣一來，正則引擎可以粗略地分為三類：DFA；傳統(tǒng)型NFA；POSIX NFA。
我們來看使用`to(nite|knight|night)`來匹配文本‘…tonight…’的一種辦法。正則表達式從我們需要檢查的字符串的首位（這里的位置不是指某個字符的位置，而是指兩個相鄰字符的中間位置）開始，每次檢查一部分（由引擎查看表達式的一部分），同時檢查“當前文本”（此位置后面的字符）是否匹配表達式的當前部分。如果是，則繼續(xù)表達式的下一部分，如果不是，那么正則引擎向后移動一個字符的位置，繼續(xù)匹配，如此繼續(xù)，直到表達式的所有部分都能匹配，即整個表達式能夠匹配成功。在此例子中，由于表達式的第一個元素是`t`，正則引擎將會從需要匹配的字符串的首位開始重復嘗試匹配，直到在目標字符中找到‘t’為止。之后就檢查緊隨其后的字符是否能由`o`匹配，如果能，就檢查下面的元素。下面是`nite`或者`knight`或者`night`。引擎會依次嘗試這3種可能。嘗試`nite`的過程與之前一樣：“嘗試匹配`n`，然后是`i`，然后是`t`，最后是`e`”。如果這種嘗試失敗，引擎就會嘗試另一種可能，如此繼續(xù)下去，直到匹配成功或是報告失敗。表達式的控制權(quán)在不同的元素之間轉(zhuǎn)換，所以我們可以稱它為“表達式主導”。
與表達式主導的NFA不同，DFA引擎在掃描字符串時會記錄“當前有效”的所有匹配可能。在此例中引擎會對‘…tonight…’進行掃描，當掃描到t時，引擎會在表達式里面的t上坐上一個標記，記錄當前位置可以匹配，然后繼續(xù)掃描o，同樣可以匹配，繼續(xù)掃描到n，發(fā)現(xiàn)有兩個可以匹配（knight被淘汰），當掃描到g時就只剩下一個可以匹配了，當h和t匹配完成后，引擎發(fā)現(xiàn)匹配已經(jīng)成功，報告成功。我們稱這種方式為“文本主導”，因為它掃描的字符串中的每個字符都對引擎進行了控制。
從它們匹配的邏輯上我們不難發(fā)現(xiàn)：一般情況下，文本主導的DFA引擎要快一些。正則表達式主導的NFA引擎，因為需要對同樣的文本嘗試不同的子表達式匹配，可能會浪費時間。在NFA的匹配過程中，目標文本的某個字符可能會被正則表達式反復檢測很多遍（每一個字符被檢測的次數(shù)不確定，所以NFA叫做不確定型有窮自動機）。相反，DFA引擎在匹配過程中目標文本中的每個字符只會最多檢查一遍（每個字符被檢測的次數(shù)相對確定，所以DFA叫做確定型有窮自動機）。由于DFA取得一個結(jié)果可能有上百種途徑，但是因為DFA能夠同時記錄它們，選擇哪一個表達式并無區(qū)別，也就是說你改變寫法對于效率是沒有影響的。而NFA是表達式主導，改變表達式的編寫方式可能會節(jié)省很多功夫。
所以后面我們講解的知識都是涉及的NFA的。
2、回溯
何為回溯？先來看一個例子，我們使用`a(b|c)d`去嘗試匹配字符串“cabb”，正則引擎首先處于字符'c'的前面，開始查看正則表達式，發(fā)現(xiàn)第一個為a，不能匹配，然后引擎移動到'c'和'a'之間的位置，繼續(xù)查看表達式，發(fā)現(xiàn)a可以匹配，然后查看表達式的后面，發(fā)現(xiàn)有兩條路，引擎會做好標記，選擇其中一條路，加入選擇區(qū)匹配b，發(fā)現(xiàn)字符'a'后面就是'b'，可以匹配，然偶再次查看表達式，需要匹配d，發(fā)現(xiàn)字符串后面是'b'，不符合條件，這條路失敗，引擎會自動回到之前做選擇的地方，這里就稱作一次回溯。那么引擎會嘗試匹配a后面的c，發(fā)現(xiàn)'a'后面是'b'，這條路也走不通，沒有其它的路線了，然后引擎又會移動位置，現(xiàn)在到了'a'和'b'之間，引擎回去嘗試匹配表達式的a，發(fā)現(xiàn)當前位置后面是'b'，無法匹配，引擎又開始向后移動位置，直到移動到最后，發(fā)現(xiàn)沒有一次匹配成功，然后引擎才會報告失敗。而如果中間又一次成功完整匹配了，引擎會自動停止（傳統(tǒng)型NFA會停止，而POSIX NFA還會繼續(xù)，把所有可能匹配完，選擇其中一個），報告成功。
現(xiàn)在應該知道回溯其實就是引擎在匹配字符串的過程中出現(xiàn)多選的情況，當其中一種選擇無法匹配時再次選擇另種的過程叫做回溯。其實我們在優(yōu)化正則表達式的時候就是考慮的盡量減少回溯的次數(shù)。
2.1回溯 匹配優(yōu)先和忽略優(yōu)先
《精通正則表達式》這本書里面叫做匹配優(yōu)先和忽略優(yōu)先，網(wǎng)上有很多人叫做貪婪模式和非貪婪模式，反正都一樣，叫法無所謂。
匹配優(yōu)先量詞我們已經(jīng)學習了，就是?、+、*、{}這四個。匹配優(yōu)先量詞在匹配的時候首先會嘗試匹配，如果失敗后回溯才會選擇忽略。比如`ab?`匹配"abb"會得到"abb"。這里當匹配成功'a'后，引擎有兩個選擇，一個是嘗試匹配后面的b，一個是忽略后面的b，而由于是匹配優(yōu)先，所以引擎會嘗試匹配b，發(fā)現(xiàn)可以匹配，得到了"ab"，接著引擎又一次遇到了同樣的問題，還是會選擇先匹配，所以得到了"abb"，接著引擎發(fā)現(xiàn)后面沒有字符了，就上報匹配成功。
忽略優(yōu)先量詞使用的是在?、+、*、{}后面添加?組成的，忽略優(yōu)先在匹配的時候首先會嘗試忽略，如果失敗后回溯才會選擇嘗試。比如`ab??`匹配“abb”會得到‘a(chǎn)’而不是“ab”。當引擎匹配成功a后，由于是忽略優(yōu)先，引擎首先選擇不匹配b，繼續(xù)查看表達式，發(fā)現(xiàn)表達式結(jié)束了，那么引擎就直接上報匹配成功。
例子1：
var reg1=/ab?/;
var reg2=/ab??/;
var result1=reg1.exec("abc");
var result2=reg2.exec("abc");
document.write(result1+" "+result2);結(jié)果：
例子2：
var reg1=/ab+/;
var reg2=/ab+?/;
var result1=reg1.exec("abbbc");
var result2=reg2.exec("abbbc");
document.write(result1+" "+result2);結(jié)果：
例子3：
var reg1=/ab*/;
var reg2=/ab*?/;
var result1=reg1.exec("abbbc");
var result2=reg2.exec("abbbc");
document.write(result1+" "+result2);結(jié)果：
例子4：
var reg1=/ab{2,4}/;
var reg2=/ab{2,4}?/;
var result1=reg1.exec("abbbbbbc");
var result2=reg2.exec("abbbbbbc");
document.write(result1+" "+result2);結(jié)果：
下面我們來看稍微復雜一點的匹配優(yōu)先的情況，使用`c.*d`去匹配字符串“caaadc”，我們發(fā)現(xiàn)當c匹配成功后，`.*`會一直匹配到最后的'c'，然后再去匹配表達式里面的d，發(fā)現(xiàn)后面沒有字符可以匹配，這是就會回溯到`.*`匹配'c'的地方，選擇`.*`忽略'c'，那么c就留給后面了，但是發(fā)現(xiàn)還是不能匹配d，又得回溯到匹配d的位置，`.*`再次選擇忽略匹配，發(fā)現(xiàn)就可以匹配d了，這是停止匹配，上報匹配成功，所以結(jié)果是“caaad”。
再看一個忽略優(yōu)先的情況，使用`a.*?d`去匹配字符串“caaadc”，我們發(fā)現(xiàn)當匹配成功a時，引擎有兩條路，會選擇忽略匹配，直接匹配d，但是字符串“caaadc”的a后面是a，所以失敗，回溯到之前的選擇，懸著匹配，獲得“aa”，然后又一次遇到同樣的問題，引擎選擇忽略匹配，發(fā)現(xiàn)后面又是a，不能匹配d，再次回溯，選擇匹配，得到“aaa”，這一次忽略匹配后發(fā)現(xiàn)后匹配成功了d，那么上報成功，得到“aaad”。
希望這幾個例子能夠大概講解清楚這兩種不同的情況吧！
2.2回溯 環(huán)視
環(huán)視結(jié)構(gòu)不匹配任何字符，只匹配文本中的特定位置，這一點和單詞分界符`\b`、`^`、`$`相似。
`(?=)`稱作肯定順序環(huán)視，如`x(?=y)`是指匹配x，僅當后面緊跟y時，如果符合匹配，則只有x會被記住，y不會被記住。
`(?!)`稱作否定順序環(huán)視，如`x(?!y)`是指匹配x，僅當后面不緊跟y時，如果符合匹配，則只有x會被記住，y不會被記住。
在環(huán)視內(nèi)部的備用狀態(tài)一旦退出環(huán)視范圍后立即清除，外部回溯不能回溯到環(huán)視內(nèi)部的備用狀態(tài)。使用`ab\w+c`和`ab(?=\w+)c`來匹配字符串“abbbbc”，第一個表達式會成功，而第二個表達式會失敗。
例子1：
var reg=/ab(?=c)/;
var result1=reg.exec("abcd");
var result2=reg.exec("abbc");
document.write(result1+" "+result2);結(jié)果：
例子2：
var reg=/ab(?!c)/;
var result1=reg.exec("abdc");
var result2=reg.exec("abcd");
document.write(result1+" "+result2);結(jié)果：
例子3：
var reg1=/ab\w+bc/;
var reg2=/ab(?=\w+)c/;
var result1=reg1.exec("abbbbbcb");
var result2=reg2.exec("abbbbbbc");
document.write(result1+" "+result2);結(jié)果：
明顯自己都覺得環(huán)視沒講解好，還有肯定逆序環(huán)視和否定逆序環(huán)視，以及固化分組這些都是在解決回溯的問題，回溯算是影響表達式的罪魁禍首吧！這幾個內(nèi)容看啥時候有時間在細講吧！寫著寫著才發(fā)現(xiàn)想讓人看懂不是那么容易的！體諒一下哦！
3、打造高效正則表達式
Perl、Java、.NET、Python和PHP，以及我們熟悉的JS使用的都是表達式主導的NFA引擎，細微的改變就可能對匹配的結(jié)果產(chǎn)生重大的影響。DFA中不存在的問題對NFA來說卻很重要。因為NFA引擎允許用戶進行精確控制，所以我們可以用心打造正則表達式。
3.1先邁好使的腿
對于一般的文本來說，字母和數(shù)字比較多，而一些特殊字符很少，一個簡單的改動就是調(diào)換兩個多選分支的順序，也許會達到不錯的效果。如使用`(:|\w)*`和`(\w|:)*`來匹配字符串“ab13_b:bbbb:c34d”，一般說來冒號在文本中出現(xiàn)的次數(shù)少于字母數(shù)字，此例中第一個表達式效率低于第二個。
例子：
var reg1=/(:|\w)*/;
var reg2=/(\w|:)*/;
var result1=reg1.exec("ab13_b:bbbb:c34d");
var result2=reg2.exec("ab13_b:bbbb:c34d");
document.write(result1+" "+result2);3.2無法匹配時
對于無法匹配的文本，可能它在匹配過程中任然會進行許多次工作，我們可以通過某種方式提高報錯的速度。如使用`”.*”!`和`”[^”]*”!`去匹配字符串“The name “McDonald’s” is said “makudonarudo” in Japanese”。我們可以看出第一種回溯的次數(shù)明顯多于第二種。
3.3多選結(jié)構(gòu)代價高
多選結(jié)構(gòu)是回溯的主要原因之一。例如使用`u|v|w|x|y|z`和`[uvwxyz]`去匹配字符串“The name “McDonald’s” is said “makudonarudo” in Japanese”。最終`[uvwxyz]`只需要34次嘗試就能夠成功，而如果使用`u|v|w|x|y|z`則需要在每個位置進行6次回溯，在得到同樣結(jié)果前總共有206次回溯。
少用多選結(jié)構(gòu)。
3.4消除無必要的括號
如果某種實現(xiàn)方式認為`(?:.)*`與`.*`是完全等價的，那么請使用后者替換前者，`.*`實際上更快一些。
3.5消除不需要的字符組
只包含單個字符的字符組有點多余，因為它要按照字符組來處理，而這么做完全沒有必要。所以例如`[.]`可以寫成`\.`。
3.6量詞等價轉(zhuǎn)換
有人習慣用`\d\d\d\d`，也有人習慣使用量詞`\d{4}`。對于NFA來說效率上時有差別的，但工具不同結(jié)果也不同。如果對量詞做了優(yōu)化，則`\d{4}`會更快一些，除非未使用量詞的正則表達式能夠進行更多的優(yōu)化。
3.7使用非捕獲型括號
如果不需要引用括號內(nèi)的文本，請使用非捕獲型括號`(?:)`。這樣不但能夠節(jié)省捕獲的時間，而且會減少回溯使用的狀態(tài)的數(shù)量。由于捕獲需要使用內(nèi)存，所以也減少了內(nèi)存的占用。
3.8提取必須的元素
由于很多正則引擎存在著局部優(yōu)化，主要是依靠正則引擎的能力來識別出匹配成功必須的一些文本，所以我們手動的將這些文本“暴露”出來可以提高引擎識別的可能性。 `xx*`替代`x+`能夠暴露必須的‘x’。`-{2,4}`可以寫作`--{0,2}`。用`th(?:is|at)`代替`(?:this|that)`就能暴露必須的`th`。
3.9忽略優(yōu)先和匹配優(yōu)先
通常，使用忽略優(yōu)先量詞還是匹配優(yōu)先量詞取決于正則表達式的具體需求。例如`^.*:`完全不同于`^.*?:`，因為前者匹配到最后的冒號，而后者匹配到第一個冒號。但是如果目標數(shù)據(jù)中只包含一個冒號，兩個表達式就沒有區(qū)別了。不過并不是任何時候優(yōu)劣都如此分明，大的原則是：如果目標字符串很長，而你認為冒號會比較接近字符串的開頭，就使用忽略優(yōu)先量詞；如果你認為冒號在接近字符串的末尾位置，你就使用匹配優(yōu)先。如果數(shù)據(jù)是隨機的，又不知道冒號在哪頭，就使用匹配優(yōu)先量詞，因為它們的優(yōu)化一般來說都要比其他量詞要好一些。
3.10拆分正則表達式
有時候，應用多個小正則表達式的速度比一個大正則表達式要快得多。比如你希望檢查一個長字符串中是否包含月份的名字，依次檢查`January`、`February`、`March`之類的速度要比`January|..|….`快得多。
還有很多優(yōu)化的方法見《精通正則表達式》，我在這里只是列舉了部分容易理解的方式。其實只要理解正則引擎室如何匹配的，理解回溯的邏輯，你就可以對自己寫的表達式進行相應的優(yōu)化了！
喜歡 
頂
難過
囧
圍觀
無聊
