《正規表達式經典執行個體（第2版）》——2.13 選擇最小或最大重複次數

本節書摘來自異步社群《正規表達式經典執行個體（第2版）》一書中的第2章，第2.13節，作者： 【美】jan goyvaerts , steven levithan著，更多章節内容可以通路雲栖社群“異步社群”公衆号檢視

問題描述

比對一對xhtml标簽<code>&lt;p&gt;</code>和<code>&lt;/p&gt;</code>，以及二者之間的所有文本。在标簽之間的文本也可以包含其他xhtml标簽。

解決方案

讨論

在執行個體2.12中讨論的所有量詞都是貪心的（greedy，又稱比對優先），意味着它們會試圖盡量多次重複，隻有當後面的正規表達式不能比對的時候才會回吐（已比對的文本）。

這對于把xhtml（它是xml的一個版本，是以要求每個起始标簽都存在比對的結束标簽）中的标簽進行配對來說，可能會變得困難。看看這個簡單的xhtml片段：

在該斷碼片段中，存在兩個起始<code>&lt;p&gt;</code>标簽和兩個結束<code>&lt;/p&gt;</code>标簽。你想要把第一個<code>&lt;p&gt;</code>與第一個<code>&lt;/p&gt;</code>進行比對，因為它們标記了一個獨立的段落。注意這個段落還嵌套了一個<code>&lt;em&gt;</code>标簽，是以該正規表達式不能在遇到&lt;符号的時候就直接停止。

我們來看一個錯誤的解答。

這個錯誤解答中唯一的不同是它缺少了星号之後額外的問号。這個不正确的答案中使用的星号與執行個體2.12中講解的星号同樣貪心。

在比對了目标文本中的第一個<code>&lt;p&gt;</code>之後，引擎會到達‹.›。其中的點号可以比對任意字元，其中也包括換行符。星号則把它重複0次或更多次。這裡的星号是貪心的，是以‹.›會比對直到目标文本結束的所有内容。我再重申一遍：‹.*›會吃掉你的整個xhtml檔案，從第一段開始。

當‹.*›把肚子吃飽之後，引擎才會試圖去在目标文本的末尾比對‹&lt;›。顯然會失敗。但是這還沒完：正則引擎會進行回溯（backtrack）。

星号更喜歡占有盡可能多的文本，但是它對于不比對任何東西（0次重複）同樣也會感到十分滿足。在超過量詞最小次數之後的每次重複，正規表達式都會儲存一個回溯位置。如果在該量詞之後的正規表達式比對失敗，那麼正則引擎可以回到這些位置。

當‹&lt;›比對失敗之後，引擎會進行回溯，讓‹.›放棄它比對的一個字元。接着‹&lt;›會再次嘗試比對，這次是檔案中的最後一個字元。如果它依然失敗的話，那麼引擎會再一次進行回溯，在檔案的倒數第二個字元處嘗試比對‹&lt;›。這個過程會一直繼續，直到‹&lt;›比對成功為止。如果‹&lt;›一直沒有比對成功，那麼最終‹.›會回退完所有的回溯位置，然後整體比對宣布失敗。

如果在整個回溯的過程中，‹&lt;›的确在某個點上成功比對了，就會接着嘗試比對‹/›。如果‹/›比對失敗的話，那麼引擎會繼續進行回溯。這個過程會一直重複，直到‹<code>&lt;/p&gt;</code>›可以被完整比對為止。

那麼問題在哪裡呢？因為星号是貪心的，是以上面給出的錯誤的正規表達式會比對xhtml檔案中的第一個‹p›到最後一個‹/p›之間的所有内容。但是要想正确地比對一個xhtml段落，我們需要的是比對第一個‹p›與其後的第一個‹/p›。

這個時候，我們就需要使用懶惰（lazy，又稱忽略優先）量詞了。你可以在其後放一個問号來使任何量詞變成懶惰的：‹*?›、‹+?›、‹??›和‹{7,42}?›都是懶惰量詞。

懶惰量詞也會進行回溯，但卻是從不同的方向進行的。一個懶惰量詞會重複盡可能少的次數，然後儲存一個回溯位置，并且允許正規表達式繼續。如果後面的正規表達式比對失敗了，那麼引擎會進行回溯，此時懶惰量詞會再重複一次。如果正規表達式持續回溯，那麼量詞會擴充直到它允許的最大重複次數，或者直到它所重複的正規表達式記号比對失敗。

‹<code>&lt;p&gt;.*?&lt;/p&gt;</code>›使用了一個懶惰量詞來正确地比對一個xhtml段落。當‹<code>&lt;p&gt;</code>›比對成功的時候，‹.?›作為懶惰量詞，最初什麼也不做，隻是稍作停頓。如果‹<code>&lt;/p&gt;</code>›在<code>&lt;p&gt;</code>之後立即出現，就會比對一個空段落。如果不是這樣，那麼引擎會回溯到‹.?›，這次會比對一個字元。如果‹<code>&lt;/p&gt;</code>›還是比對失敗，‹.?›會接着比對下一個字元。這個過程會持續進行下去，直到‹<code>&lt;/p&gt;</code>›比對成功，或者‹.?›擴充失敗。因為點号會比對任意字元，是以直到xhtml檔案結束‹.*?›比對完了所有内容，都不會出現比對失敗。

量詞‹›和‹?›允許所有相同的正規表達式比對。唯一的差別是這些可能的比對嘗試的順序不同。貪心量詞會找到最長可能的比對。懶惰量詞則會找到最短可能的比對。

如果可能，最佳解決方案是確定隻存在一個可能的比對。在執行個體2.12中，如果你把所有量詞都變成懶惰的，用來比對數字的正規表達式還會比對相同的數字。原因是這些正規表達式中擁有量詞的部分和緊跟其後的部分是互斥的。‹d›比對一個數字，而隻有當下一個字元不是數字（或字母）的時候‹b›才會比對‹d›之後的位置。

為了有助于更好地了解貪心和懶惰量詞重複的操作過程，我們可以比較一下‹d+b›和‹d+?b›在幾個不同目标文本之上的表現。貪心和懶惰版本會産生相同的結果，但是卻會按照不同的順序來檢查目标文本。

如果我們使用‹d+b›來比對1234，‹d+›會比對所有的數字。接着‹b›比對，就會找到一個完整比對。如果我們使用‹d+?b›，‹d+?›首先隻會比對1。‹b›在1和2之間比對失敗。‹d+?›會擴充到12，但是‹b›還是會失敗。這将持續下去，直到‹d+?›比對1234，以及‹b›成功比對。

如果我們的目标文本是1234x，第一個正則式‹d+b›依然會讓‹d+›先比對1234。但是接着‹b›會比對失敗。‹d+›回溯到123。‹b›還是會比對失敗。這會繼續下去，直到‹d+›回溯到最小可能的1，‹b›仍然比對失敗。這樣整體比對嘗試就會宣告失敗。

如果我們使用‹d+?b›來比對1234x，‹d+?›首先隻會比對1。‹b›在1和2之間比對失敗。‹d+?›會擴充到12，但是‹b›還是會失敗。這将一直繼續，直到‹d+?›比對1234，‹b›仍然比對失敗。正則引擎會試圖再一次擴充‹d+?›，但是‹d›無法比對x。整體比對嘗試宣告失敗。

如果我們把‹d+›放到單詞邊界之中，那麼它必須比對目标文本中的所有數字，否則就會比對失敗。把量詞變成懶惰的，并不會影響正則比對最終是成功還是失敗。事實上，‹bd+b›更好，因為不用任何回溯。下一個執行個體會解釋如何可以使用一個占有量詞‹bd++b›來達到這個目标，至少在某些流派中，這樣是可行的。