正則表達(dá)式具有偉大技術(shù)發(fā)明的一切特點(diǎn)，它簡(jiǎn)單、優(yōu)美、功能強(qiáng)大、妙用無(wú)窮。對(duì)于很多實(shí)際工作來(lái)講，正則表達(dá)式簡(jiǎn)直是靈丹妙藥，能夠成百倍地提高開發(fā)效率和程序質(zhì)量。

1. 正則常見規(guī)則

1.1 字符匹配

字符說(shuō)明\轉(zhuǎn)義符\d[0-9]。表示是一位數(shù)字。\D[^0-9]。表示除數(shù)字外的任意字符。\w[0-9a-zA-Z_]。表示數(shù)字、大小寫字母和下劃線。\W[^0-9a-zA-Z_]。非單詞字符。\s[\t\v\n\r\f]。表示空白符，包括空格、水平制表符、
垂直制表符、換行符、回車符、換頁(yè)符。\S[^\t\v\n\r\f]。非空白符。.[^\n\r]。通配符，表示幾乎任意字符。
換行符、回車符、行分隔符和段分隔符除外。\uxxxx查找以十六進(jìn)制數(shù) xxxx 規(guī)定的 Unicode 字符。\f匹配一個(gè)換頁(yè)符 (U+000C)。\n匹配一個(gè)換行符 (U+000A)。\r匹配一個(gè)回車符 (U+000D)。\t匹配一個(gè)水平制表符 (U+0009)。\v匹配一個(gè)垂直制表符 (U+000B)。\0匹配 NULL（U+0000）字符， 不要在這后面跟其它小數(shù)，因?yàn)?\0是一個(gè)
八進(jìn)制轉(zhuǎn)義序列。[\b]匹配一個(gè)退格(U+0008)。（不要和\b 混淆了。）[abc]any of a, b, or c[^abc]not a, b, or c[a-g]character between a & g

1.2 位置匹配

字符說(shuō)明\b是單詞邊界，具體就是\w 和\W 之間的位置，也包括\w 和 ^ 之間的位置，
也包括\w 和之間的位置。具體說(shuō)來(lái)就是與、與、與，與之間的位置。\B是\b 的反面的意思，非單詞邊界。例如在字符串中所有位置中，扣掉\b，
剩下的都是\B 的。^abc$字符串開始、結(jié)束的位置

1.3 組

字符說(shuō)明(abc)capture group，捕獲組\nbackreference to group #n，分組引用，引用第 n 個(gè)捕獲組匹配的內(nèi)容,
其中 n 是正整數(shù)(?:abc)non-capturing group，非捕獲組

1.4 先行斷言

字符說(shuō)明a(?=b)positive lookahead，先行斷言，a 只有在 b 前面才匹配a(?!b)negative lookahead，先行否定斷言，a 只有不在 b 前面才匹配

1.5 后行斷言

字符說(shuō)明(?<=b)apositive lookbehind，后行斷言，a 只有在 b 后面才匹配(?<!b)anegative lookbehind，后行否定斷言，a 只有不在 b 后面才匹配

1.6 量詞和分支

字符說(shuō)明a*0 or morea+1 or morea?0 or 1a{5}exactly fivea{2,}two or morea{1,3}between one & threea+?
a{2,}?match as few as possible，惰性匹配，就是盡可能少的匹配

以下都是惰性匹配：
{m,n}?
{m,}?
??
+?
*?

1.7 分支

字符說(shuō)明ab|cdmatch ab or cd，匹配'ab'或者'cd'字符子串

1.8 修飾符

字符說(shuō)明i執(zhí)行對(duì)大小寫不敏感的匹配。g執(zhí)行全局匹配（查找所有匹配而非在找到第一個(gè)匹配后停止）。m執(zhí)行多行匹配。u開啟"Unicode 模式"，用來(lái)正確處理大于\uFFFF 的 Unicode 字符。也就是說(shuō)，會(huì)正確處理四個(gè)字節(jié)的 UTF-16 編碼。s允許 . 匹配換行符。yy 修飾符的作用與 g 修飾符類似，也是全局匹配，后一次匹配都從上一次匹配成功的下一個(gè)位置開始。不同之處在于，g 修飾符只要剩余位置中存在匹配就可，而 y 修飾符確保匹配必須從剩余的第一個(gè)位置開始，這也就是"粘連"的涵義

2. 運(yùn)算符優(yōu)先級(jí)

運(yùn)算符描述\轉(zhuǎn)義符(), (?:), (?=), []圓括號(hào)和方括號(hào)*, +, ?, {n}, {n,}, {n,m}限定符^, $, \任何元字符、任何字符定位點(diǎn)和序列（即：位置和順序）|替換，"或"操作
字符具有高于替換運(yùn)算符的優(yōu)先級(jí)，使得"m|food"匹配"m"或"food"。若要匹配"mood"或"food"，請(qǐng)使用括號(hào)創(chuàng)建子表達(dá)式，從而產(chǎn)生"(m|f)ood"。

3. 正則回溯

3.1 什么是回溯算法

以下是來(lái)自摘自維基百科的部分解釋：

回溯法是一種通用的計(jì)算機(jī)算法，用于查找某些計(jì)算問(wèn)題的所有（或某些）解決方案，特別是約束滿足問(wèn)題，逐步構(gòu)建候選解決方案，并在確定候選不可能時(shí)立即放棄候選（"回溯"）完成有效的解決方案。

回溯法通常用最簡(jiǎn)單的遞歸方法來(lái)實(shí)現(xiàn)，在反復(fù)重復(fù)上述的步驟后可能出現(xiàn)兩種情況：

找到一個(gè)可能存在的正確的答案

在嘗試了所有可能的分步方法后宣告該問(wèn)題沒有答案

在最壞的情況下，回溯法會(huì)導(dǎo)致一次復(fù)雜度為指數(shù)時(shí)間的計(jì)算。

3.2 什么是正則回溯

正則引擎主要可以分為兩大類：一種是 DFA(Deterministic finite automaton 確定型有窮自動(dòng)機(jī))，另一種是 NFA（NFA Non-deterministic finite automaton 　非確定型有窮自動(dòng)機(jī)）。NFA 速度較 DFA 更慢，并且實(shí)現(xiàn)復(fù)雜，但是它又有著比 DFA 強(qiáng)大的多的功能，比如支持反向引用等。像 javaScript、java、php、python、c#等語(yǔ)言的正則引擎都是 NFA 型，NFA 正則引擎的實(shí)現(xiàn)過(guò)程中使用了回溯。

3.2.1 沒有回溯的正則

舉一個(gè)網(wǎng)上常見的例子，正則表達(dá)式/ab{1,3}c/g 去匹配文本'abbc'，我們接下來(lái)會(huì)通過(guò) RegexBuddy 分析其中的匹配過(guò)程，后續(xù)的一個(gè)章節(jié)有關(guān)于 RegexBuddy 的使用介紹。

如上圖所示，讓我們一步一步分解匹配過(guò)程：

1. 正則引擎先匹配 a。
2. 正則引擎盡可能多地(貪婪)匹配 b。
3. 正則引擎匹配 c，完成匹配。

在這之中，匹配過(guò)程都很順利，并沒發(fā)生意外(回溯)。

3.2.2 有正則回溯的正則

讓我們把上面的正則修改一下，/ab{1,3}c/g 改成/ab{1,3}bc/g，接下再通過(guò) RegexBuddy 查看分析結(jié)果。

我們?cè)僖徊揭徊椒纸馄ヅ溥^(guò)程：

1. 正則引擎先匹配 a。
2. 正則引擎盡可能多地(貪婪)匹配 b{1,3}中的 b。
3. 正則引擎去匹配 b，發(fā)現(xiàn)沒 b 了，糟糕！趕緊回溯！
4. 返回 b{1,3}這一步，不能這么貪婪，少匹配個(gè) b。
5. 正則引擎去匹配 b。
6. 正則引擎去匹配 c，完成匹配。

以上，就是一個(gè)簡(jiǎn)單的回溯過(guò)程。

3.3 正則回溯的幾種常見形式

從上面發(fā)生正則回溯的例子可以看出來(lái)，正則回溯的過(guò)程就是一個(gè)試錯(cuò)的過(guò)程，這也是回溯算法的精髓所在。回溯會(huì)增加匹配的步驟，勢(shì)必會(huì)影響文本匹配的性能，所以，要想提升正則表達(dá)式的匹配性能，了解回溯出現(xiàn)的場(chǎng)景(形式)是非常關(guān)鍵的。

3.3.1 貪婪量詞

在 NFA 正則引擎中，量詞默認(rèn)都是貪婪的。當(dāng)正則表達(dá)式中使用了下表所示的量詞，正則引擎一開始會(huì)盡可能貪婪的去匹配滿足量詞的文本。當(dāng)遇到匹配不下去的情況，就會(huì)發(fā)生回溯，不斷試錯(cuò)，直至失敗或者成功。

量詞說(shuō)明a*0 or morea+1 or morea?0 or 1a{5}exactly fivea{2,}two or morea{1,3}between one & three

當(dāng)多個(gè)貪婪量詞挨著存在，并相互有沖突時(shí)，秉持的是"先到先得"的原則，如下所示：


let string = "12345"; 
let regex = /(\d{1,3})(\d{1,3})/; 
console.log( string.match(regex) ); 
// => ["12345", "123", "45", index: 0, input: "12345"] 

3.3.2 惰性量詞

貪婪是導(dǎo)致回溯的重要原因，那我們盡量以懶惰匹配的方式去匹配文本，是否就能避免回溯了呢？答案是否定的。

讓我們還是看回最初的例子，/ab{1,3}c/g 去匹配 abbc。接下來(lái)，我們?cè)侔颜齽t修改一下，改成/ab{1,3}?c/g 去匹配 abbc，以懶惰匹配的方式去匹配文本，RegexBuddy 執(zhí)行步驟如下圖所示：

1. 正則引擎先匹配 a。
2. 正則引擎盡可能少地(懶惰)匹配 b{1,3}中的 b。
3. 正則引擎去匹配 c，糟糕！怎么有個(gè) b 擋著，匹配不了 c 啊！趕緊回溯！
4. 返回 b{1,3}這一步，不能這么懶惰，多匹配個(gè) b。
5. 正則引擎再去匹配 c，糟糕！怎么還有 b 擋著，匹配不了 c 啊！趕緊回溯！
6. 返回 b{1,3}這一步，不能這么懶惰，再多匹配個(gè) b。
7. 正則引擎再去匹配 c，匹配成功，棒棒噠！

本來(lái)是好端端不會(huì)發(fā)生回溯的正則，因?yàn)槭褂昧硕栊粤吭~進(jìn)行懶惰匹配后，反而產(chǎn)生了回溯了。所以說(shuō)，惰性量詞也不能瞎用，關(guān)鍵還是要看場(chǎng)景。

3.3.3 分組

分支的匹配規(guī)則是：按照分支的順序逐個(gè)匹配，當(dāng)前面的分支滿足要求了，則舍棄后面的分支。

舉個(gè)簡(jiǎn)單的分支栗子，使用正則表達(dá)式去匹配 /abcde|abc/g 文本 abcd，還是通過(guò) RegexBuddy 查看執(zhí)行步驟：

1. 正則引擎匹配 a。
2. 正則引擎匹配 b。
3. 正則引擎匹配 c。
4. 正則引擎匹配 d。
5. 正則引擎匹配 e，糟糕！下一個(gè)并不是 e，趕緊回溯！
6. 上一個(gè)分支走不通，切換分支，第二個(gè)分支正則引擎匹配 a。
7. 第二個(gè)分支正則引擎匹配 b。
8. 第二個(gè)分支正則引擎匹配 c，匹配成功！

由此，可以看出，分組匹配的過(guò)程，也是個(gè)試錯(cuò)的過(guò)程，中間是可能產(chǎn)生回溯的。

4. 正則的分析與調(diào)試

RegexBuddy 是個(gè)十分強(qiáng)大的正則表達(dá)式學(xué)習(xí)、分析及調(diào)試工具。RegexBuddy 支持 C++、Java、JavaScript、Python 等十幾種主流編程語(yǔ)言。通過(guò) RegexBuddy，能看到正則一步步創(chuàng)建的過(guò)程。結(jié)合測(cè)試文本，你能看到正則一步步執(zhí)行匹配的過(guò)程，這對(duì)于理解正則回溯和對(duì)正則進(jìn)行進(jìn)一步優(yōu)化，都有極大的幫助。

4.1 安裝分析調(diào)試工具

可以在 RegexBuddy 的官方網(wǎng)站下載及獲取 RegexBuddy。

下載完后，一步步點(diǎn)擊安裝即可。

4.2 工具界面介紹

下圖便是 RegexBuddy 界面的各個(gè)面板及相關(guān)功能。

4.3 創(chuàng)建正則

為了方便使用，可以在布局設(shè)置那里將布局設(shè)置成 Side by Side Layout。

在正則輸入?yún)^(qū)輸入你的正則 regex1，查看 Create 面板，就會(huì)發(fā)現(xiàn)面板上顯示了正則的創(chuàng)建過(guò)程(或者說(shuō)是匹配規(guī)則)，在 Test 面板區(qū)域輸入你的測(cè)試文本，滿足 regex1 匹配規(guī)則的部分會(huì)高亮顯示，如下圖所示。

4.4 使用 RegexBuddy 的 Debug 功能

選中測(cè)試文本，點(diǎn)擊 debug 就可以進(jìn)入 RegexBuddy 的 debug 模式，個(gè)人覺得這是 RegexBuddy 最強(qiáng)大地方，因?yàn)樗梢宰屇闱宄刂滥爿斎氲恼齽t對(duì)測(cè)試文本的匹配過(guò)程，執(zhí)行了多少步，哪里發(fā)生了回溯，哪里需要優(yōu)化，你都能一目了然。

4.5 使用 RegexBuddy 的 Library 功能

RegexBuddy 的正則庫(kù)內(nèi)置了很多常用正則，日常編碼過(guò)程中需要的很多正則表達(dá)式都能在該正則庫(kù)中找到。

4.6 更多工具推薦

• 正則可視化-regexper
• 正則可視化-regulex
• 正則在線調(diào)試

5. 正則性能優(yōu)化

正則是個(gè)很好用的利器，如果使用得當(dāng)，如有神助，能省掉大量代碼。當(dāng)如果使用不當(dāng)，則是處處埋坑。所以，本章節(jié)的重點(diǎn)就是總結(jié)如何寫一個(gè)高性能的正則表達(dá)式。

5.1 避免量詞嵌套

舉個(gè)簡(jiǎn)單的例子對(duì)比：

我們使用正則表達(dá)式/a*b/去匹配字符串 aaaaa，看下圖 RegexBuddy 的執(zhí)行過(guò)程：

我們將以上正則修改成/(a*)*b/去匹配字符串 aaaaa，再看看 RegexBuddy 的執(zhí)行結(jié)果過(guò)程：

以上兩個(gè)正則的基本執(zhí)行步驟可以簡(jiǎn)單認(rèn)為是：

1. 貪婪匹配
2. 回溯
3. 直至發(fā)現(xiàn)匹配失敗

但令人驚奇的是，第一個(gè)正則的從開始匹配到匹配失敗這個(gè)過(guò)程只有 14 步。而第二個(gè)正則卻有 128 步之多。可想而知，嵌套量詞會(huì)大大增加正則的執(zhí)行過(guò)程。因?yàn)檫@其中進(jìn)行了兩層回溯，這個(gè)執(zhí)行步驟增加的過(guò)程就如同算法復(fù)雜度從 O(n)上升到 O(n^2)的過(guò)程一般。

所以，面對(duì)量詞嵌套，我們需作出適當(dāng)?shù)霓D(zhuǎn)化消除這些嵌套：


(a*)* <=> (a+)* <=> (a*)+ <=> a* 
(a+)+ <=> a+ 

5.2 使用非捕獲組

NFA 正則引擎中的括號(hào)主要有兩個(gè)作用：

1. 主流功能，提升括號(hào)中內(nèi)容的運(yùn)算優(yōu)先級(jí)
2. 反向引用

反向引用這個(gè)功能很強(qiáng)大，強(qiáng)大的代價(jià)是消耗性能。所以，當(dāng)我們?nèi)绻恍枰玫嚼ㄌ?hào)反向引用的功能時(shí)，我們應(yīng)該盡量使用非捕獲組，也就是:


// 捕獲組與非捕獲組 
() => (?:) 

5.3 分支優(yōu)化

分支也是導(dǎo)致正則回溯的重要原因，所以，針對(duì)正則分支，我們也需要作出必要的優(yōu)化。

5.3.1 減少分支數(shù)量

首先，需要減少分支數(shù)量。比如不少正則在匹配 http 和 https 的時(shí)候喜歡寫成：


/^http|https/ 

其實(shí)上面完全可以優(yōu)化成：


/^https?/ 

這樣就能減少?zèng)]必要的分支回溯

5.3.2 縮小分支內(nèi)的內(nèi)容

縮小分支中的內(nèi)容也是很有必要的，例如我們需要匹配 this 和 that ，我們也許會(huì)寫成：


/this|that/ 

但上面其實(shí)完全可以優(yōu)化成


/th(?:is|at)/ 

有人可能認(rèn)為以上沒啥區(qū)別，實(shí)踐出真知，讓我們用以上兩個(gè)正則表達(dá)式去匹配一下 that。

我們會(huì)發(fā)現(xiàn)第一個(gè)正則的執(zhí)行步驟比第一個(gè)正則多兩步，那是因?yàn)榈谝粋€(gè)正則的回溯路徑比第二個(gè)正則的回溯路徑更長(zhǎng)了，最終導(dǎo)致執(zhí)行步驟變長(zhǎng)。

5.4 錨點(diǎn)優(yōu)化

在能使用錨點(diǎn)的情況下盡量使用錨點(diǎn)。大部分正則引擎會(huì)在編譯階段做些額外分析, 判斷是否存在成功匹配必須的字符或者字符串。類似^、$ 這類錨點(diǎn)匹配能給正則引擎更多的優(yōu)化信息。

例如正則表達(dá)式 hello(hi)?$ 在匹配過(guò)程中只可能從字符串末尾倒數(shù)第 7 個(gè)字符開始, 所以正則引擎能夠分析跳到那個(gè)位置, 略過(guò)目標(biāo)字符串中許多可能的字符, 大大提升匹配速度。

6. 結(jié)語(yǔ)

曾經(jīng)有一次因?yàn)閷懸粋€(gè)性能惡劣的正則表達(dá)式，導(dǎo)致代碼執(zhí)行過(guò)程因?yàn)樾阅軉?wèn)題掛掉。于是下定決心要把正則表達(dá)式搞明白，看了不少文章書籍，做了不少練習(xí)之后，總算摸到了些門道，也真真切切體會(huì)到正則表達(dá)式的優(yōu)美和強(qiáng)大。寫下此文，記錄下一些學(xué)習(xí)心得和總結(jié)，望批評(píng)指正，共同進(jìn)步。

7. 參考

• 正則表達(dá)式中的悲觀回溯
• 小心別落入正則回溯陷阱
• 正則匹配原理解析
• learncodethehardway
• 正則表達(dá)式系列總結(jié)
• wikipedia Backtracking
• 精通正則表達(dá)式