前言
編寫(xiě)高性能的正則表達(dá)式，有如下幾條規(guī)則，這幾條規(guī)則是本人總結(jié)出來(lái)的：
1、使用正確的邊界匹配器（^、$、\b、\B等）
2、使用具體的元字符、字符類(lèi)（\d、\w、\s等）
3、使用正確的量詞（+、*、?、{n,m}）
4、使用非捕獲組、原子組
5、注意量詞的嵌套
其實(shí)正則表達(dá)式的很多優(yōu)化技巧都是圍繞著“減少回溯”這樣一個(gè)原則進(jìn)行優(yōu)化的。
至于什么是“回溯”，筆者就不在這里重復(fù)了，以下通過(guò)具體的例子理解這樣的過(guò)程。
示例
一、以下是一則匹配電子郵件地址的正則表達(dá)式：
^\w+([\.-]?\w+)*@\w+([\.-]?\w+)*(\.\w{2,3})+$
先一步步的解析：
1、^\w+：表示必須以字符開(kāi)始， 且是一個(gè)或者多個(gè)；
2、([\.-]?\w+)*中的“[\.-]?”表示匹配“.”或者“-”，零次或者一次；
3、([\.-]?\w+)*中的“\w+”則表示匹配一個(gè)或者多個(gè)的字符；
4、([\.-]?\w+)*整個(gè)則表示匹配.xxx、-xxx或者xxx這樣的字符，且零次或者多次；
5、第1-4步，則匹配sunny或者sunny.yang這樣的字符；
6、“@”則是具體元，匹配具體的@；
7、 \w+：則表示匹配的一個(gè)或者多個(gè)的字符，因?yàn)閑mail不可能這樣嘛：sunny@.gmail.com；
8、 ([\.-]?\w+)*：則跟第2-4步一樣，匹配.163、-lib、.gd這樣的字符，且零次或者多次；
9、 (\.\w{2,3})+$：則匹配.com、.cc這樣結(jié)尾的域名，且因?yàn)閈w{2,3}限定了長(zhǎng)度必須為2-3位，所以不能匹配.c、.n這樣的字符。
乍看這樣一個(gè)解析過(guò)程沒(méi)問(wèn)題，邏輯正確，但其實(shí)暗藏很多問(wèn)題，看看以下的一個(gè)匹配圖，backtrack則表示回溯（使用RegexBuddy可以很清晰的看到這過(guò)程）
整個(gè)成功的匹配過(guò)程經(jīng)歷了55步，我們先分析下整個(gè)匹配過(guò)程：
1、圖中的第1和2步，匹配^\w+，匹配成功，匹配了“admin”;
2、圖中第3步，匹配[\.-]?，當(dāng)然由于不存在“.”和“-”，因此沒(méi)匹配上具體的字符，但又由于“?”的限定，可以匹配零或者一次，因此這個(gè)子表達(dá)式匹配成功，雖然沒(méi)匹配上具體的字符。
3、圖中第4步，匹配\w+，由于“+”限定一個(gè)或者多個(gè)以上字符，但后續(xù)已經(jīng)沒(méi)[a-zA-Z0-9]可以匹配了，因此產(chǎn)生回溯，回溯到上次匹配成功的位置，也就admin；
4、圖中第5步，因?yàn)樯弦徊疆a(chǎn)生了回溯，所以“[\.-]?\w+”匹配了零次，由于([\.-]?\w+)*中限定零次或者多次，因此也匹配成功，也沒(méi)匹配上具體的字符；
以下步驟，匹配該過(guò)程：
^\w+([\.-]?\w+)*@\w+([\.-]?\w+)*(\.\w{2,3})+$
5、圖中第6步，匹配了“@” ，第7步匹配了“\w+”，即匹配了“open”；
6、圖中第8-13步，匹配“([\.-]?\w+)*” ，匹配了“-lib”、“.com”，匹配“.com”可能與我們期望不相符，我們期望這子表達(dá)式匹配的是www.xx.gd.cn中的“.gd”；
7、圖中第7-10步，匹配了open-lib，第7-13步則匹配了open-lib.com；
8、因?yàn)椤?[\.-]?\w+)*”中的量詞是“*”，則繼續(xù)重復(fù)這個(gè)過(guò)程；
9、 圖中第14步，匹配“([\.-]?\w+)*”中的“[\.-]?”，因?yàn)榇藭r(shí)指針已經(jīng)位于@open-lib.com之后了，但由于量詞“?”，因此也匹配成功，但沒(méi)匹配上字符，也沒(méi)字符可匹配；
10、 圖中第15步，匹配“([\.-]?\w+)*”中的“\w+”，此時(shí)指針仍位于字符串末尾，沒(méi)任何字符能匹配，所以匹配失敗，產(chǎn)生回溯，回到上次成功的位置，即圖中的第13步，繼續(xù)下個(gè)表達(dá)式的匹配；
11、 圖中第16步，匹配(\.\w{2,3})+中的“\.”，由于沒(méi)有任何字符能匹配，匹配失敗，進(jìn)行回溯；
12、圖中第17步 ，(\.\w{2,3})+中量詞“+”，表示該表達(dá)式必須匹配一次或者多次，由于上一步匹配失敗了，所以匹配零次，但不符合一次或者多次的限定，因此繼續(xù)回溯；
13、由于上一步匹配失敗，需要進(jìn)行回溯，因此表達(dá)式?jīng)]有更多的分支了，只能將指針回退一個(gè)字符，回溯上次成功的位置，即([\.-]?\w+)*中\(zhòng)w+的位置（這是上次產(chǎn)生分支的位置）；
14、圖中剩下的步驟，就重復(fù)著匹配([\.-]?\w+)*，回退字符，匹配(\.\w{2,3})+這樣的過(guò)程，直到匹配成功。
二、以下看看另外一則同樣匹配郵件地址的正則表達(dá)式：
^\w+([-\.]\w+)*@\w+([-\.]\w+)*\.\w+([-\.]\w+)*$
這個(gè)正則跟上面的看起來(lái)貌似差不多，不過(guò)細(xì)看還是有區(qū)別的，也先一步步來(lái)解析：
1、^\w+：表示必須以字符開(kāi)始， 且是一個(gè)或者多個(gè)（這一步與上面的一樣）；
2、 ([-\.]\w+)*中的“[-\.]”表示匹配“-”或者“.”；
3、 ([-\.]\w+)*中的“\w+”則表示匹配一個(gè)或者多個(gè)的字符；
4、([-\.]\w+)*整個(gè)則表示匹配.xxx、-xxx這樣的字符，且零次或者多次；
5、第1-4步，則匹配sunny或者sunny.yang這樣的字符；
6、“@”則是具體元，匹配具體的“@”；
7、 \w+：則表示匹配的一個(gè)或者多個(gè)的字符，因?yàn)閑mail不可能這樣嘛：sunny@.gmail.com；
8、([-\.]\w+)*：則跟第2-4步一樣，匹配.163、-lib、.gd這樣的字符，且零次或者多次；
9、“\.”則是具體元，匹配“.”；
10、\w+：則匹配一個(gè)或者多個(gè)字符；
11、([-\.]\w+)*：則匹配“.com”、“-lib”、“.c”這樣的字符，且可以零次或者多次；
12、$ ：則表示結(jié)尾
乍看這個(gè)正則的步驟過(guò)程貌似比上一則長(zhǎng)，其實(shí)不然，同時(shí)這個(gè)正則也存在著問(wèn)題，先看看匹配圖，同樣backtrack表示回溯：
對(duì)的，你沒(méi)看錯(cuò)，整個(gè)正確的匹配過(guò)程用了19步，對(duì)比前面的55步，簡(jiǎn)直天與地的差別。，我們繼續(xù)分析下匹配過(guò)程：
1、圖中的第1和2步，匹配^\w+，匹配成功，匹配了“admin”;
2、圖中第3步，匹配[-\.]，當(dāng)然由于不存在“.”和“-”，因此沒(méi)匹配上具體的字符，也沒(méi)具體的量詞允許匹配零次，所以不用繼續(xù)往下匹配了，因此直接產(chǎn)生了回溯；
3、圖中第4步，因?yàn)樯弦徊疆a(chǎn)生了回溯，所以“[-\.]\w+”匹配了零次，由于([-\.]\w+)*中限定零次或者多次，因此也匹配成功，也沒(méi)匹配上具體的字符；
以下步驟，匹配該過(guò)程：
^\w+([-\.]\w+)*@\w+([-\.]\w+)*\.\w+([-\.]\w+)*$
4、圖中第6步\w+，匹配了open；
5、圖中第7-12步匹配([-\.]\w+)*，匹配了“-lib”和“.com”；
6、因?yàn)椤?[-\.]\w+)*”中的量詞是“*”，則繼續(xù)重復(fù)這個(gè)過(guò)程；
7、圖第13步，匹配([-\.]\w+)* ，因?yàn)榇藭r(shí)指針已經(jīng)位于@open-lib.com之后了，也沒(méi)具體的量詞允許匹配零次，因此匹配失敗，回溯到上次成功的位置；
8、圖第14步，匹配 ([-\.]\w+)*$中的“[-\.]”，此時(shí)指針仍位于字符串末尾，沒(méi)任何字符能匹配，所以匹配失敗，產(chǎn)生回溯，回到上次成功且還沒(méi)嘗試過(guò)的位置，即圖中的第9步；
9、經(jīng)過(guò)上面的回溯，指針已經(jīng)位于@open-lib之后的位置了；
10、圖第15步匹配了“.”，第16步\w+則匹配了“com” ；
11、圖第17步匹配([-\.]\w+)*，由于此時(shí)指針又位于字符串末尾，因此[-\.]部分沒(méi)匹配上任何字符，因此產(chǎn)生回溯；
12、圖第18步，由于 ([-\.]\w+)*的量詞是“*”，表示匹配零次或多次，雖然子表達(dá)式[-\.]匹配失敗，所以整個(gè)表達(dá)式匹配了零次，也是匹配成功；
13、最后一步第19步，“$”表示末尾匹配，因?yàn)榇藭r(shí)指針位于字符串末尾，故符合，因此也匹配成功。
分析
整個(gè)匹配過(guò)程關(guān)鍵優(yōu)化地方，還是回溯，兩個(gè)示例表達(dá)式看起來(lái)相近，匹配過(guò)程也部分類(lèi)似，但兩個(gè)例子的效率卻如此大的分別，現(xiàn)在來(lái)分析一下造成回溯的原因。
對(duì)比下兩個(gè)表達(dá)式不同的部分：
^\w+([\.-]?\w+)*@\w+([\.-]?\w+)*(\.\w{2,3})+$
^\w+([\.-]\w+)*@\w+([\.-]\w+)*\.\w+([-\.]\w+)*$
喜歡 
頂
難過(guò)
囧
圍觀(guān)
無(wú)聊
