373
《正則表達式經典實例（第2版）》——2.13 選擇最小或最大重複次數
本節書摘來自異步社區《正則表達式經典實例（第2版）》一書中的第2章，第2.13節，作者： 【美】Jan Goyvaerts , Steven Levithan著，更多章節內容可以訪問雲棲社區“異步社區”公眾號查看
2.13 選擇最小或最大重複次數
問題描述
匹配一對XHTML標簽<p>和</p>，以及二者之間的所有文本。在標簽之間的文本也可以包含其他XHTML標簽。
解決方案
<p>.*?</p>
正則選項：點號匹配換行符
正則流派：.NET、Java、JavaScript、PCRE、Perl、Python、Ruby
討論
在實例2.12中討論的所有量詞都是貪心的（greedy，又稱匹配優先），意味著它們會試圖盡量多次重複，隻有當後麵的正則表達式不能匹配的時候才會回吐（已匹配的文本）。
這對於把XHTML（它是XML的一個版本，因此要求每個起始標簽都存在匹配的結束標簽）中的標簽進行配對來說，可能會變得困難。看看這個簡單的XHTML片段：
<p>
The very <em>first</em> task is to find the beginning of a paragraph.
</p>
<p>
Then you have to find the end of the paragraph
</p>
在該斷碼片段中，存在兩個起始<p>標簽和兩個結束</p>標簽。你想要把第一個<p>與第一個</p>進行匹配，因為它們標記了一個獨立的段落。注意這個段落還嵌套了一個<em>標簽，因此該正則表達式不能在遇到<符號的時候就直接停止。
我們來看一個錯誤的解答。
<p>.*</p>
正則選項：點號匹配換行符
正則流派：.NET、Java、JavaScript、PCRE、Perl、Python、Ruby
這個錯誤解答中唯一的不同是它缺少了星號之後額外的問號。這個不正確的答案中使用的星號與實例2.12中講解的星號同樣貪心。
在匹配了目標文本中的第一個<p>之後，引擎會到達‹.›。其中的點號可以匹配任意字符，其中也包括換行符。星號則把它重複0次或更多次。這裏的星號是貪心的，因此‹.›會匹配直到目標文本結束的所有內容。我再重申一遍：‹.*›會吃掉你的整個XHTML文件，從第一段開始。
當‹.*›把肚子吃飽之後，引擎才會試圖去在目標文本的末尾匹配‹<›。顯然會失敗。但是這還沒完：正則引擎會進行回溯（backtrack）。
星號更喜歡占有盡可能多的文本，但是它對於不匹配任何東西（0次重複）同樣也會感到十分滿足。在超過量詞最小次數之後的每次重複，正則表達式都會保存一個回溯位置。如果在該量詞之後的正則表達式匹配失敗，那麼正則引擎可以回到這些位置。
當‹<›匹配失敗之後，引擎會進行回溯，讓‹.*›放棄它匹配的一個字符。接著‹<›會再次嚐試匹配，這次是文件中的最後一個字符。如果它依然失敗的話，那麼引擎會再一次進行回溯，在文件的倒數第二個字符處嚐試匹配‹<›。這個過程會一直繼續，直到‹<›匹配成功為止。如果‹<›一直沒有匹配成功，那麼最終‹.*›會回退完所有的回溯位置，然後整體匹配宣布失敗。
如果在整個回溯的過程中，‹<›的確在某個點上成功匹配了，就會接著嚐試匹配‹/›。如果‹/›匹配失敗的話，那麼引擎會繼續進行回溯。這個過程會一直重複，直到‹</p>›可以被完整匹配為止。
那麼問題在哪裏呢？因為星號是貪心的，所以上麵給出的錯誤的正則表達式會匹配XHTML文件中的第一個‹p›到最後一個‹/p›之間的所有內容。但是要想正確地匹配一個XHTML段落，我們需要的是匹配第一個‹p›與其後的第一個‹/p›。
這個時候，我們就需要使用懶惰（lazy，又稱忽略優先）量詞了。你可以在其後放一個問號來使任何量詞變成懶惰的：‹*?›、‹+?›、‹??›和‹{7,42}?›都是懶惰量詞。
懶惰量詞也會進行回溯，但卻是從不同的方向進行的。一個懶惰量詞會重複盡可能少的次數，然後保存一個回溯位置，並且允許正則表達式繼續。如果後麵的正則表達式匹配失敗了，那麼引擎會進行回溯，此時懶惰量詞會再重複一次。如果正則表達式持續回溯，那麼量詞會擴展直到它允許的最大重複次數，或者直到它所重複的正則表達式記號匹配失敗。
‹<p>.*?</p>›使用了一個懶惰量詞來正確地匹配一個XHTML段落。當‹<p>›匹配成功的時候，‹.*?›作為懶惰量詞，最初什麼也不做，隻是稍作停頓。如果‹</p>›在<p>之後立即出現，就會匹配一個空段落。如果不是這樣，那麼引擎會回溯到‹.*?›，這次會匹配一個字符。如果‹</p>›還是匹配失敗，‹.*?›會接著匹配下一個字符。這個過程會持續進行下去，直到‹</p>›匹配成功，或者‹.*?›擴展失敗。因為點號會匹配任意字符，所以直到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+›放到單詞邊界之中，那麼它必須匹配目標文本中的所有數字，否則就會匹配失敗。把量詞變成懶惰的，並不會影響正則匹配最終是成功還是失敗。事實上，‹\b\d+\b›更好，因為不用任何回溯。下一個實例會解釋如何可以使用一個占有量詞‹\b\d++\b›來達到這個目標，至少在某些流派中，這樣是可行的。
最後更新：2017-06-02 19:35:48