第四章 正則表達式回溯法原理

第四章 正則表達式回溯法原理

學習正則表達式，是需要懂點兒匹配原理的。

而研究匹配原理時，有兩個字出現的頻率比較高：「回溯」。

聽起來挺高大上，確實還有很多人對此不明不白的。

因此，本章就簡單扼要地說清楚回溯到底是什麼東西。

內容包括：

沒有回溯的匹配

有回溯的匹配

常見的回溯形式

1. 沒有回溯的匹配

假設我們的正則是 /ab{1,3}c/，其可視化形式是：

而當目標字符串是"abbbc"時，就沒有所謂的「回溯」。其匹配過程是：

其中子表達式 b{1,3}表示「b」字符連續出現1到3次。

2. 有回溯的匹配

如果目標字符串是"abbc"，中間就有回溯。

圖中第5步有紅顏色，表示匹配不成功。此時 b{1,3}已經匹配到了2個字符「b」，準備嘗試第三個時，結果發現接下來的字符是「c」。那麼就認為 b{1,3}就已經匹配完畢。然後狀態又回到之前的狀態（即第6步，與第4步一樣），最後再用子表達式 c，去匹配字符「c」。當然，此時整個表達式匹配成功了。

圖中的第6步，就是「回溯」。

你可能對此沒有感覺，這裡我們再舉一個例子。正則是：

目標字符串是"abbbc"，匹配過程是：

其中第7步和第10步是回溯。第7步與第4步一樣，此時 b{1,3}匹配了兩個"b"，而第10步與第3步一樣，此時 b{1,3}只匹配了一個"b"，這也是 b{1,3}的最終匹配結果。

這裡再看一個清晰的回溯，正則是：

目標字符串是："acd"ef，匹配過程是：

圖中省略了嘗試匹配雙引號失敗的過程。可以看出 .*是非常影響效率的。

為了減少一些不必要的回溯，可以把正則修改為 /"[^"]*"/。

3. 常見的回溯形式

正則表達式匹配字符串的這種方式，有個學名，叫回溯法。

回溯法也稱試探法，它的基本思想是：從問題的某一種狀態（初始狀態）出發，搜索從這種狀態出發所能達到的所有「狀態」，當一條路走到「盡頭」的時候（不能再前進），再後退一步或若干步，從另一種可能「狀態」出發，繼續搜索，直到所有的「路徑」（狀態）都試探過。這種不斷「前進」、不斷「回溯」尋找解的方法，就稱作「回溯法」。（copy於百度百科）。

本質上就是深度優先搜索算法。其中退到之前的某一步這一過程，我們稱為「回溯」。從上面的描述過程中，可以看出，路走不通時，就會發生「回溯」。即，嘗試匹配失敗時，接下來的一步通常就是回溯。

道理，我們是懂了。那麼JS中正則表達式會產生回溯的地方都有哪些呢？

3.1 貪婪量詞

之前的例子都是貪婪量詞相關的。比如 b{1,3}，因為其是貪婪的，嘗試可能的順序是從多往少的方向去嘗試。首先會嘗試"bbb"，然後再看整個正則是否能匹配。不能匹配時，吐出一個"b"，即在"bb"的基礎上，再繼續嘗試。如果還不行，再吐出一個，再試。如果還不行呢？只能說明匹配失敗了。

雖然局部匹配是貪婪的，但也要滿足整體能正確匹配。否則，皮之不存，毛將焉附？

此時我們不禁會問，如果當多個貪婪量詞挨著存在，並相互有衝突時，此時會是怎樣？

答案是，先下手為強！因為深度優先搜索。測試如下：

var string = "12345";

var regex = /(\d{1,3})(\d{1,3})/;

console.log( string.match(regex) );

// => ["12345", "123", "45", index: 0, input: "12345"]

其中，前面的 \d{1,3}匹配的是"123"，後面的 \d{1,3}匹配的是"45"。

3.2 惰性量詞

惰性量詞就是在貪婪量詞後面加個問號。表示儘可能少的匹配，比如：

var string = "12345";

var regex = /(\d{1,3}?)(\d{1,3})/;

console.log( string.match(regex) );

// => ["1234", "1", "234", index: 0, input: "12345"]

其中 \d{1,3}?只匹配到一個字符"1"，而後面的 \d{1,3}匹配了"234"。

雖然惰性量詞不貪，但也會有回溯的現象。比如正則是：

目標字符串是"12345"，匹配過程是：

知道你不貪、很知足，但是為了整體匹配成，沒辦法，也只能給你多塞點了。因此最後 \d{1,3}?匹配的字符是"12"，是兩個數字，而不是一個。

3.3 分支結構

我們知道分支也是惰性的，比如 /can|candy/，去匹配字符串"candy"，得到的結果是"can"，因為分支會一個一個嘗試，如果前面的滿足了，後面就不會再試驗了。

分支結構，可能前面的子模式會形成了局部匹配，如果接下來表達式整體不匹配時，仍會繼續嘗試剩下的分支。這種嘗試也可以看成一種回溯。

比如正則：

目標字符串是"candy"，匹配過程：

上面第5步，雖然沒有回到之前的狀態，但仍然回到了分支結構，嘗試下一種可能。所以，可以認為它是一種回溯的。

小結

其實回溯法，很容易掌握的。

簡單總結就是，正因為有多種可能，所以要一個一個試。直到，要麼到某一步時，整體匹配成功了；要麼最後都試完後，發現整體匹配不成功。

貪婪量詞「試」的策略是：買衣服砍價。價錢太高了，便宜點，不行，再便宜點。

惰性量詞「試」的策略是：賣東西加價。給少了，再多給點行不，還有點少啊，再給點。

分支結構「試」的策略是：貨比三家。這家不行，換一家吧，還不行，再換。

既然有回溯的過程，那麼匹配效率肯定低一些。相對誰呢？相對那些DFA引擎。

而JS的正則引擎是NFA，NFA是「非確定型有限自動機」的簡寫。

大部分語言中的正則都是NFA，為啥它這麼流行呢？

答：你別看我匹配慢，但是我編譯快啊，而且我還有趣哦。

作者：老姚

原文：https://juejin.im/post/5965943ff265da6c30653879

本文版權歸作者所有，轉載請經得作者授權

第一章 正則表達式字符匹配攻略

第二章 正則表達式位置匹配攻略

第三章 正則表達式括號的作用