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

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

我們說正則表達式是語言無關的，是因為驅動正則表達式的引擎是相似的。鑒于正則表達式是一種古老的語法，它的引擎也在歷史長河中衍生出了幾個大的分支。

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

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

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

我們把有限自動機理解為一個機器人，在這個機器人眼里，所有的事物都是由有限節點組成的。機器人按照順序讀取有限節點，并表達成有限狀態，最終機器人輸出接受或者拒絕作為結束。

關注它的兩個特點：

有限狀態集。

只根據當前狀態和當前輸入來決定下一個狀態。它有點一板一眼。

怎么理解第二個特點？我們看一個例子：

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

我們知道*?是非貪婪匹配，按照我們人類靈活的尿性，直接把匹配結果ab甩他臉上。

但有限自動機不會。第一步它用a匹配a非常完美，然后發現對于a是非貪婪模式，于是試著用b匹配下一個a，結果非常沮喪。于是它只能繼續用a匹配，匹配成功后依然沒忘非貪婪特性，繼續試著用b匹配下一個字符b，成功，收官。

其實寫出這段代碼的開發者想要的結果應該是ab，但有限自動機從來不仰望星空，只低頭做事，一板一眼的根據當前狀態和當前輸入來決定下一個狀態。

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

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

總的來說，DFA可以稱為文本主導的正則引擎，NFA可以稱為表達式主導的正則引擎。

怎么講？

我們常常說用正則去匹配文本，這是NFA的思路，DFA本質上其實是用文本去匹配正則。哪個是攻，哪個是受，大家心里應該有個B數了吧。

我們來看一個例子：

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

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

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

大家發現什么問題了嗎？

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

這就是它們之間的本質區別。其他的不同都是這個特性衍生出來的。

首先，正則表達式在計算機看來只是一串符號，正則引擎首先肯定要解析它。NFA引擎只需要編譯就好了；而DFA引擎則比較繁瑣，編譯完還不算，還要遍歷出表達式中所有的可能。因為對DFA引擎來說機會只有一次，它必須得提前知道所有的可能，才能匹配出最優的結果。

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

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

所以，在運行階段，NFA引擎比DFA引擎慢。

最后，因為NFA引擎是表達式占主導地位，所以它的表達能力更強，開發者的控制度更高，也就是說開發者更容易寫出性能好又強大的正則來，當然也更容易造成性能的浪費甚至撐爆CPU。DFA引擎下的表達式，只要可能性是一樣的，任何一種寫法都是沒有差別(可能對編譯有細微的差別)的，因為對DFA引擎來說，表達式其實是死的。而NFA引擎下的表達式，高手寫的正則和新手寫的正則，性能可能相差10倍甚至更多。

也正是因為主導權的不同，正則中的很多概念，比如非貪婪模式、反向引用、零寬斷言等只有NFA引擎才有。

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

當今市面上大多數正則引擎都是NFA引擎，應該就是勝在表達能力上。

現在我們知道正則表達式的驅動引擎分為兩大類：DFA引擎與NFA引擎。

但是因為NFA引擎比較靈活，很多語言在實現上有細微的差別。所以后來大家弄了一個標準，符合這個標準的正則引擎就叫做POSIX NFA引擎，其余的就只能叫做傳統型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]

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

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

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

結論就是：JavaScript的正則引擎是傳統型NFA引擎。

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

正是因為這樣的機制，引申出了NFA引擎的核心特點——回溯。

首先我們要區分備選狀態和回溯。

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

備選狀態是個好東西，它可以實現模糊匹配，是正則表達能力的一方面。

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

我們來看兩個例子：

"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]

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

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

請問，第二個例子發生回溯了嗎？

并沒有。

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

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

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

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

網絡上有很多文章都認為上面第二個例子發生了回溯。至少根據我查閱的資料，第二個例子發生的情況不能被稱為回溯。當然也有可能我是錯的，歡迎討論。

我們再來看一個真正的回溯例子：

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

匹配文本到ab為止，都沒什么問題。然而蒼天饒過誰，后面既匹配不到b，也匹配不到c。引擎只好將文本ab吐出來，從下一個位置開始匹配。因為上一次是從第一個字符a開始匹配，所以下一個位置當然就是從第二個字符b開始咯。

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

這他媽才叫回溯！

還有一個細節。上面例子中的回溯并沒有往回吐呀，吐出來之后不應該往回走嘛，怎么往后走了？

我們再來看一個例子：

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

因為.*是貪婪匹配，所以它把后面的字符都吞進去了。直到發現目標完不成，不得已往回吐，吐到第二個"為止，終于匹配成功。這就好比結了婚還在外面養小三，幾經折騰才發現家庭才是最重要的，自己的行為背離了初衷，于是幡然悔悟。

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

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

`
/g);

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

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

不賣關子。它會導致瀏覽器卡死，是因為分支和范圍太多了。[^-]+是一個范圍，[-][^-]+是一個范圍，[^-]+|[-][^-]+是一個分支，([^-]+|[-][^-]+)*又是一個范圍。另外注意，嵌套的分支和范圍生成的備選狀態是呈指數級增長的。

我們知道這段語句肯定會匹配失敗，因為文本中壓根就沒有-->。那瀏覽器為什么會卡死呢？因為正則引擎的回溯實在過多，導致瀏覽器的CPU進程飆到98%以上。這和你在Chrome開發者工具跑一段巨大運算量的for循環是一個道理。

但是呢，正則永遠不會走入死循環。正則引擎叫有限狀態機，就是因為它的備選狀態是有限的。既然是有限的，那就一定可以遍歷完。10的2次方叫有限，10的200000000次方也叫有限。只不過計算機的硬件水平有限，容不得你進行這么大的運算量。我以前也以為是正則進入了死循環，其實這種說法是不對的，應該叫瀏覽器卡死或者撐爆CPU。

那么，怎么解決？

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

第二就是減少分支和范圍，尤其是嵌套的分支和范圍。因為分支和范圍越多，備選狀態就越多，早早的就匹配成功還好，如果匹配能成功的備選狀態在很后頭或者壓根就無法匹配成功，那你家的CPU就得嗷嗷叫咯。

我們來看一下：

`

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

你看，備選狀態再多，我已經找到了我的白馬王子，你們都歇著去吧。

這個正則我不知道它這樣寫的用意何在，所以也不知道怎么優化。明白備選狀態是回溯的罪魁禍首就好了。

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

"/g);
// null

試的時候悠著點，不同的瀏覽器可能承受能力不一樣，你可以一個個字符往上加，看看極限在哪里。

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

現在我們知道了控制回溯是控制正則表達式性能的關鍵。

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

備選狀態的數量當然是核心，然而如果備選狀態雖然多，卻早早的匹配成功了，早匹配早下班，也就沒那么多糟心事了。

至于面對具體的正則表達式應該如何優化，那就是經驗的問題了。思考和實踐的越多，就越游刃有余。無他，唯手熟爾。

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

[regexper ]是一個能讓正則的備選狀態可視化的工具，也有助于理解復雜的正則語法。

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