摘要：總的來說，可以稱為文本主導(dǎo)的正則引擎，可以稱為表達(dá)式主導(dǎo)的正則引擎。首先，正則表達(dá)式在計(jì)算機(jī)看來只是一串符號，正則引擎首先肯定要解析它。精通正則表達(dá)式書中說引擎不支持非貪婪模式，很明顯不是引擎。正則表達(dá)式中可以商榷的部分就叫做備選狀態(tài)。

本文是『horseshoe·Regex專題』系列文章之一，后續(xù)會有更多專題推出
GitHub地址：https://github.com/veedrin/horseshoe
博客地址(文章排版真的很漂亮)：https://veedrin.com
如果覺得對你有幫助，歡迎來GitHub點(diǎn)Star或者來我的博客親口告訴我

我們說正則表達(dá)式是語言無關(guān)的，是因?yàn)轵?qū)動正則表達(dá)式的引擎是相似的。鑒于正則表達(dá)式是一種古老的語法，它的引擎也在歷史長河中衍生出了幾個(gè)大的分支。

我會關(guān)注到正則表達(dá)式引擎這樣比較底層的實(shí)現(xiàn)，緣起于在一次業(yè)務(wù)實(shí)踐中，追蹤到一個(gè)由正則引起的BUG。業(yè)務(wù)中使用的一個(gè)markdown解析庫Remarkable在解析一段不規(guī)則文本時(shí)引起瀏覽器崩潰，調(diào)試之后發(fā)現(xiàn)是某一個(gè)正則在匹配時(shí)陷入了死循環(huán)，嚴(yán)格的說(后來才知道)是匹配花費(fèi)了過多時(shí)間導(dǎo)致瀏覽器卡死。

我當(dāng)時(shí)很震驚，正則匹配的性能不是很高的么？匹配到就是匹配到，沒匹配到就是沒匹配到，怎么會在里面走不出來了呢？

什么叫有限自動機(jī)(Finite Automate)呢？

我們把有限自動機(jī)理解為一個(gè)機(jī)器人，在這個(gè)機(jī)器人眼里，所有的事物都是由有限節(jié)點(diǎn)組成的。機(jī)器人按照順序讀取有限節(jié)點(diǎn)，并表達(dá)成有限狀態(tài)，最終機(jī)器人輸出接受或者拒絕作為結(jié)束。

關(guān)注它的兩個(gè)特點(diǎn)：

有限狀態(tài)集。

只根據(jù)當(dāng)前狀態(tài)和當(dāng)前輸入來決定下一個(gè)狀態(tài)。它有點(diǎn)一板一眼。

怎么理解第二個(gè)特點(diǎn)？我們看一個(gè)例子：

"aab".match(/a*?b/);
// ["aab", index: 0, input: "aab", groups: undefined]

我們知道*?是非貪婪匹配，按照我們?nèi)祟愳`活的尿性，直接把匹配結(jié)果ab甩他臉上。

但有限自動機(jī)不會。第一步它用a匹配a非常完美，然后發(fā)現(xiàn)對于a是非貪婪模式，于是試著用b匹配下一個(gè)a，結(jié)果非常沮喪。于是它只能繼續(xù)用a匹配，匹配成功后依然沒忘非貪婪特性，繼續(xù)試著用b匹配下一個(gè)字符b，成功，收官。

其實(shí)寫出這段代碼的開發(fā)者想要的結(jié)果應(yīng)該是ab，但有限自動機(jī)從來不仰望星空，只低頭做事，一板一眼的根據(jù)當(dāng)前狀態(tài)和當(dāng)前輸入來決定下一個(gè)狀態(tài)。

有限自動機(jī)大體上又可以分為兩類：DFA是確定性有限自動機(jī)的縮寫，NFA是非確定性有限自動機(jī)的縮寫。

我沒辦法告訴你DFA與NFA在原理上的差別，但咱們可以探討一下它們在處理正則上的表現(xiàn)差異。

總的來說，DFA可以稱為文本主導(dǎo)的正則引擎，NFA可以稱為表達(dá)式主導(dǎo)的正則引擎。

怎么講？

我們常常說用正則去匹配文本，這是NFA的思路，DFA本質(zhì)上其實(shí)是用文本去匹配正則。哪個(gè)是攻，哪個(gè)是受，大家心里應(yīng)該有個(gè)B數(shù)了吧。

我們來看一個(gè)例子：

"tonight".match(/to(nite|knite|night)/);

如果是NFA引擎，表達(dá)式占主導(dǎo)地位。表達(dá)式中的t和o不在話下。然后就面臨三種選擇，它也不嫌累，每一種都去嘗試一下，第一個(gè)分支在t這里停止了，接著第二個(gè)分支在k這里也停止了。終于在第三個(gè)分支柳暗花明，找到了自己的歸宿。

換作是DFA引擎呢，文本占主導(dǎo)地位。同樣文本中的t和o不在話下。文本走到n時(shí)，它發(fā)現(xiàn)正則只有兩個(gè)分支符合要求，經(jīng)過i走到g的時(shí)候，只剩一個(gè)分支符合要求了。當(dāng)然，還要繼續(xù)匹配。果然沒有令它失望，第三個(gè)分支完美符合要求，下班。

大家發(fā)現(xiàn)什么問題了嗎？

只有正則表達(dá)式才有分支和范圍，文本僅僅是一個(gè)字符流。這帶來什么樣的后果？就是NFA引擎在匹配失敗的時(shí)候，如果有其他的分支或者范圍，它會返回，記住，返回，去嘗試其他的分支。而DFA引擎一旦匹配失敗，就結(jié)束了，它沒有退路。

這就是它們之間的本質(zhì)區(qū)別。其他的不同都是這個(gè)特性衍生出來的。

首先，正則表達(dá)式在計(jì)算機(jī)看來只是一串符號，正則引擎首先肯定要解析它。NFA引擎只需要編譯就好了；而DFA引擎則比較繁瑣，編譯完還不算，還要遍歷出表達(dá)式中所有的可能。因?yàn)閷FA引擎來說機(jī)會只有一次，它必須得提前知道所有的可能，才能匹配出最優(yōu)的結(jié)果。

所以，在編譯階段，NFA引擎比DFA引擎快。

其次，DFA引擎在匹配途中一遍過，溜得飛起。相反NFA引擎就比較苦逼了，它得不厭其煩的去嘗試每一種可能性，可能一段文本它得不停返回又匹配，重復(fù)好多次。當(dāng)然運(yùn)氣好的話也是可以一遍過的。

所以，在運(yùn)行階段，NFA引擎比DFA引擎慢。

最后，因?yàn)镹FA引擎是表達(dá)式占主導(dǎo)地位，所以它的表達(dá)能力更強(qiáng)，開發(fā)者的控制度更高，也就是說開發(fā)者更容易寫出性能好又強(qiáng)大的正則來，當(dāng)然也更容易造成性能的浪費(fèi)甚至撐爆CPU。DFA引擎下的表達(dá)式，只要可能性是一樣的，任何一種寫法都是沒有差別(可能對編譯有細(xì)微的差別)的，因?yàn)閷FA引擎來說，表達(dá)式其實(shí)是死的。而NFA引擎下的表達(dá)式，高手寫的正則和新手寫的正則，性能可能相差10倍甚至更多。

也正是因?yàn)橹鲗?dǎo)權(quán)的不同，正則中的很多概念，比如非貪婪模式、反向引用、零寬斷言等只有NFA引擎才有。

所以，在表達(dá)能力上，NFA引擎秒殺DFA引擎。

當(dāng)今市面上大多數(shù)正則引擎都是NFA引擎，應(yīng)該就是勝在表達(dá)能力上。

現(xiàn)在我們知道正則表達(dá)式的驅(qū)動引擎分為兩大類：DFA引擎與NFA引擎。

但是因?yàn)镹FA引擎比較靈活，很多語言在實(shí)現(xiàn)上有細(xì)微的差別。所以后來大家弄了一個(gè)標(biāo)準(zhǔn)，符合這個(gè)標(biāo)準(zhǔn)的正則引擎就叫做POSIX NFA引擎，其余的就只能叫做傳統(tǒng)型NFA引擎咯。

我們來看看JavaScript到底是哪種引擎類型吧。

"123456".match(/d{3,6}/);
// ["123456", index: 0, input: "123456", groups: undefined]
"123456".match(/d{3,6}?/);
// ["123", index: 0, input: "123456", groups: undefined]

《精通正則表達(dá)式》書中說POSIX NFA引擎不支持非貪婪模式，很明顯JavaScript不是POSIX NFA引擎。

TODO: 為什么POSIX NFA引擎不支持也沒有必要支持非貪婪模式？

區(qū)分DFA引擎與傳統(tǒng)型NFA引擎就簡單咯，捕獲組你有么？花式零寬斷言你有么？

結(jié)論就是：JavaScript的正則引擎是傳統(tǒng)型NFA引擎。

現(xiàn)在我們知道，NFA引擎是用表達(dá)式去匹配文本，而表達(dá)式又有若干分支和范圍，一個(gè)分支或者范圍匹配失敗并不意味著最終匹配失敗，正則引擎會去嘗試下一個(gè)分支或者范圍。

正是因?yàn)檫@樣的機(jī)制，引申出了NFA引擎的核心特點(diǎn)——回溯。

首先我們要區(qū)分備選狀態(tài)和回溯。

什么是備選狀態(tài)？就是說這一個(gè)分支不行，那我就換一個(gè)分支，這個(gè)范圍不行，那我就換一個(gè)范圍。正則表達(dá)式中可以商榷的部分就叫做備選狀態(tài)。

備選狀態(tài)是個(gè)好東西，它可以實(shí)現(xiàn)模糊匹配，是正則表達(dá)能力的一方面。

回溯可不是個(gè)好東西。想象一下，面前有兩條路，你選擇了一條，走到盡頭發(fā)現(xiàn)是條死路，你只好原路返回嘗試另一條路。這個(gè)原路返回的過程就叫回溯，它在正則中的含義是吐出已經(jīng)匹配過的文本。

我們來看兩個(gè)例子：

"abbbc".match(/ab{1,3}c/);
// ["abbbc", index: 0, input: "abbbc", groups: undefined]
"abc".match(/ab{1,3}c/);
// ["abc", index: 0, input: "abc", groups: undefined]

第一個(gè)例子，第一次a匹配a成功，接著碰到貪婪匹配，不巧正好是三個(gè)b貪婪得逞，最后用c匹配c成功。

第二個(gè)例子的區(qū)別在于文本只有一個(gè)b。所以表達(dá)式在匹配第一個(gè)b成功后繼續(xù)嘗試匹配b，然而它見到的只有黃臉婆c。不得已將c吐出來，委屈一下，畢竟貪婪匹配也只是盡量匹配更多嘛，還是要臣服于匹配成功這個(gè)目標(biāo)。最后不負(fù)眾望用c匹配c成功。

請問，第二個(gè)例子發(fā)生回溯了嗎？

并沒有。

誒，你這樣就不講道理了。不是把c吐出來了嘛，怎么就不叫回溯了？

回溯是吐出已經(jīng)匹配過的文本。匹配過程中造成的匹配失敗不算回溯。

為了讓大家更好的理解，我舉一個(gè)例子：

你和一個(gè)女孩子(或者男孩子)談戀愛，接觸了半個(gè)月后發(fā)現(xiàn)實(shí)在不合適，于是提出分手。這不叫回溯，僅僅是不合適而已。
你和一個(gè)女孩子(或者男孩子)談戀愛，這段關(guān)系維持了兩年，并且已經(jīng)同居。但由于某些不可描述的原因，疲憊掙扎之后，兩人最終還是和平分手。這才叫回溯。
雖然都是分手，但你們應(yīng)該能理解它們的區(qū)別吧。

網(wǎng)絡(luò)上有很多文章都認(rèn)為上面第二個(gè)例子發(fā)生了回溯。至少根據(jù)我查閱的資料，第二個(gè)例子發(fā)生的情況不能被稱為回溯。當(dāng)然也有可能我是錯的，歡迎討論。

我們再來看一個(gè)真正的回溯例子：

"ababc".match(/ab{1,3}c/);
// ["abc", index: 2, input: "ababc", groups: undefined]

匹配文本到ab為止，都沒什么問題。然而蒼天饒過誰，后面既匹配不到b，也匹配不到c。引擎只好將文本ab吐出來，從下一個(gè)位置開始匹配。因?yàn)樯弦淮问菑牡谝粋€(gè)字符a開始匹配，所以下一個(gè)位置當(dāng)然就是從第二個(gè)字符b開始咯。

一開始引擎是以為會和最早的ab走完余生的，然而命運(yùn)弄人，從此天涯。

這他媽才叫回溯！

還有一個(gè)細(xì)節(jié)。上面例子中的回溯并沒有往回吐呀，吐出來之后不應(yīng)該往回走嘛，怎么往后走了？

我們再來看一個(gè)例子：

""abc"def".match(/".*"/);
// [""abc"", index: 0, input: ""abc"def", groups: undefined]

因?yàn)?b>.*是貪婪匹配，所以它把后面的字符都吞進(jìn)去了。直到發(fā)現(xiàn)目標(biāo)完不成，不得已往回吐，吐到第二個(gè)"為止，終于匹配成功。這就好比結(jié)了婚還在外面養(yǎng)小三，幾經(jīng)折騰才發(fā)現(xiàn)家庭才是最重要的，自己的行為背離了初衷，于是幡然悔悟。

我想說的是，不要被回溯的回字迷惑了。它的本質(zhì)是把已經(jīng)吞進(jìn)去的字符吐出來。至于吐出來之后是往回走還是往后走，是要根據(jù)情況而定的。

現(xiàn)在我邀請讀者回到文章開始提起的正則BUG。

`
/g);

這是測試妹子用于測試XSS攻擊的一段代碼，測試的腦洞你不要去猜。正則是Remarkable用于匹配注釋的，雖然我沒搞清楚到底為什么這樣寫。src我篡改了一下，不影響效果。

不怕事大的可以去Chrome開發(fā)者工具跑上一跑。

不賣關(guān)子。它會導(dǎo)致瀏覽器卡死，是因?yàn)榉种Ш头秶嗔恕?b>[^-]+是一個(gè)范圍，[-][^-]+是一個(gè)范圍，[^-]+|[-][^-]+是一個(gè)分支，([^-]+|[-][^-]+)*又是一個(gè)范圍。另外注意，嵌套的分支和范圍生成的備選狀態(tài)是呈指數(shù)級增長的。

我們知道這段語句肯定會匹配失敗，因?yàn)槲谋局袎焊蜎]有-->。那瀏覽器為什么會卡死呢？因?yàn)檎齽t引擎的回溯實(shí)在過多，導(dǎo)致瀏覽器的CPU進(jìn)程飆到98%以上。這和你在Chrome開發(fā)者工具跑一段巨大運(yùn)算量的for循環(huán)是一個(gè)道理。

但是呢，正則永遠(yuǎn)不會走入死循環(huán)。正則引擎叫有限狀態(tài)機(jī)，就是因?yàn)樗膫溥x狀態(tài)是有限的。既然是有限的，那就一定可以遍歷完。10的2次方叫有限，10的200000000次方也叫有限。只不過計(jì)算機(jī)的硬件水平有限，容不得你進(jìn)行這么大的運(yùn)算量。我以前也以為是正則進(jìn)入了死循環(huán)，其實(shí)這種說法是不對的，應(yīng)該叫瀏覽器卡死或者撐爆CPU。

那么，怎么解決？

最粗暴也最貴的方式當(dāng)然是換一臺計(jì)算機(jī)咯。拉一臺超級計(jì)算機(jī)過來肯定是可以打服它的吧。

第二就是減少分支和范圍，尤其是嵌套的分支和范圍。因?yàn)榉种Ш头秶蕉啵瑐溥x狀態(tài)就越多，早早的就匹配成功還好，如果匹配能成功的備選狀態(tài)在很后頭或者壓根就無法匹配成功，那你家的CPU就得嗷嗷叫咯。

我們來看一下：

`

`.match(//g);
// [""]

你看，備選狀態(tài)再多，我已經(jīng)找到了我的白馬王子，你們都歇著去吧。

這個(gè)正則我不知道它這樣寫的用意何在，所以也不知道怎么優(yōu)化。明白備選狀態(tài)是回溯的罪魁禍?zhǔn)拙秃昧恕?/p>

第三就是縮減文本。會發(fā)生回溯的情況，其實(shí)文本也是一個(gè)變量。你想想，總要往回跑，如果路途能短一點(diǎn)是不是也不那么累呢？

"/g);
// null

試的時(shí)候悠著點(diǎn)，不同的瀏覽器可能承受能力不一樣，你可以一個(gè)個(gè)字符往上加，看看極限在哪里。

當(dāng)然，縮減文本是最不可行的。正則正則，就是不知道文本是什么才用正則呀。

現(xiàn)在我們知道了控制回溯是控制正則表達(dá)式性能的關(guān)鍵。

控制回溯又可以拆分成兩部分：第一是控制備選狀態(tài)的數(shù)量，第二是控制備選狀態(tài)的順序。

備選狀態(tài)的數(shù)量當(dāng)然是核心，然而如果備選狀態(tài)雖然多，卻早早的匹配成功了，早匹配早下班，也就沒那么多糟心事了。

至于面對具體的正則表達(dá)式應(yīng)該如何優(yōu)化，那就是經(jīng)驗(yàn)的問題了。思考和實(shí)踐的越多，就越游刃有余。無他，唯手熟爾。

[regex101 ]是一個(gè)很多人推薦過的工具，可以拆分解釋正則的含義，還可以查看匹配過程，幫助理解正則引擎。如果只能要一個(gè)正則工具，那就是它了。

[regexper ]是一個(gè)能讓正則的備選狀態(tài)可視化的工具，也有助于理解復(fù)雜的正則語法。

本文是『horseshoe·Regex專題』系列文章之一，后續(xù)會有更多專題推出
GitHub地址：https://github.com/veedrin/horseshoe
博客地址(文章排版真的很漂亮)：https://veedrin.com
如果覺得對你有幫助，歡迎來GitHub點(diǎn)Star或者來我的博客親口告訴我