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