439
技術社區[雲棲]
《正則表達式經典實例（第2版）》——2.14 消除不必要的回溯
本節書摘來自異步社區《正則表達式經典實例（第2版）》一書中的第2章，第2.14節，作者： 【美】Jan Goyvaerts , Steven Levithan著，更多章節內容可以訪問雲棲社區“異步社區”公眾號查看
2.14 消除不必要的回溯
問題描述
上一個實例解釋了貪心和懶惰量詞之間的區別，以及它們是如何進行回溯的。在有些情形下，這種回溯是不必要的。
‹\b\d+\b›使用了一個貪心量詞，而‹\b\d+?\b›使用的是懶惰量詞。它們都會匹配相同的內容：一個整數。如果給它們同樣的目標文本，它們都會找到完全一樣的匹配。在這裏所做的任何回溯都是不必要的。試著改寫這個正則表達式，明確地消除所有回溯，使正則表達式更加高效。
解決方案
\b\d++\b
正則選項：無
正則流派：Java、PCRE、Perl 5.10、Ruby 1.9
最容易的解決方案是使用一個占有量詞。但是隻有最新的幾種正則流派中才支持它。
\b(?>\d+)\b
正則選項：無
正則流派：.NET、Java、PCRE、Perl、Ruby
一個固化分組（atomic group）可以提供完全一樣的功能，但是需要使用稍微難懂點的語法。對固化分組的支持相比占有量詞來說更為廣泛。
JavaScript和Python都不支持占有量詞或固化分組。因此在這兩種正則流派中無法消除不必要的回溯。
討論
占有量詞（possessive quantifier）與貪心量詞是類似的：它也會試圖去重複盡可能多的次數。它們的區別是占有量詞永遠不會回退，即使回退是能夠匹配正則表達式後麵部分的唯一手段時，也不會這樣去做。占有量詞也不會記錄任何可能的回溯位置。
在量詞之後添加加號，來得到對應的占有量詞。例如，‹*+›、‹++›、‹?+›和‹{7,42}+›都是占有量詞。
在Java 4或者更新版本中，也就是從Java中包含了java.util.regex包的第一個發布起，就提供了對占有量詞的支持。本書中介紹的PCRE的所有版本（版本4～7）都支持占有量詞。Perl從5.10版本也開始支持它們。經典的Ruby正則表達式不支持占有量詞，但是Oniguruma引擎，也就是Ruby 1.9中使用的默認引擎是支持占有量詞的。
包含貪心量詞的固化分組與占有量詞會產生完全相同的效果。當正則引擎退出固化分組的時候，量詞會記住所有的回溯位置，並且分組中的其他選擇分支都會被丟棄。所使用的語法是‹(?>⋯)›，其中‹⋯›可以是任意正則表達式。固化分組本質上是非捕獲分組，加上拒絕回溯的功能。這裏的問號不是量詞；而是固化分組的起始括號就是由三個字符‹(?>›組成。
把正則表達式‹\b\d++\b›（占有版本）應用到123abc 456的時候，‹\b›會匹配目標文本的開始，‹\d++›則會匹配123。到目前為止，這和‹\b\d+\b›（貪心版本）所做的並沒有區別。但是接著第二個‹\b›會在3和a之間匹配失敗。
占有量詞不會保存任何回溯位置。既然在這個正則表達式中不存在其他量詞或者選擇分支，因此在第二個單詞邊界匹配失敗的時候，就沒有其他選擇可以嚐試了。正則引擎會立即宣布從1開始的匹配失敗。
正則引擎還會在字符串中的下一個字符位置嚐試匹配該正則表達式，使用占有量詞並不會改變這一點。如果這一正則表達式必須匹配整個目標文本，就需要使用定位符，這在實例2.5中已經講解過。最終，正則引擎會從4開始的位置嚐試匹配該正則表達式，並且找到匹配456。
使用貪心量詞的區別是當在第一次匹配第二個‹\b›的嚐試失敗之後，貪心量詞會開始回溯。正則引擎接著會（沒必要地）在2和3之間，以及1和2之間測試‹\b›。
使用固化分組的匹配過程本質上是一樣的。如果把正則表達式‹\b(?>\d+)\b›（占有版本）應用到123abc 456之上，在目標文本的開始處會匹配單詞邊界。接著正則引擎會進入固化分組，‹\d+›會匹配123。現在引擎退出固化分組。在這一點上，由‹\d+›所記住的回溯位置都被丟棄了。當第二個‹\b›匹配失敗的時候，正則引擎沒有其他選擇，隻能離開，因此會導致這次匹配嚐試立即失敗。與占有量詞的版本一樣，最終456會被找到。
我們描述占有量詞不會去記住回溯位置，而固化分組則會把回溯位置丟棄。這樣會更容易理解匹配過程，但是讀者也不要太在意這裏的區別，因為很可能在你所使用的正則流派中根本不存在這樣的區別。在許多流派中，‹x++›僅僅是‹(?>x+)›語法上的簡寫，而二者的實現則完全是一模一樣的。至於引擎是從來沒有記住回溯位置，還是說它稍後會把這些位置丟棄，對於匹配嚐試的最後結果來說是根本無關緊要的。
占有量詞和固化分組的不同之處是占有量詞隻應用於單個正則表達式記號，而固化分組則可以把一個完整正則表達式包起來。
‹\w++\d++›和‹(?>\w+\d+)›是完全不一樣的。‹\w++\d++›與‹(?>\w+)(?>\d+)›則是一樣的，二者都無法匹配abc123。‹\w++›可以完整匹配abc123。然後，正則引擎會在目標文本的結尾處試圖匹配‹\d++›。因為現在並不存在任何可以匹配的多餘字符，所以‹\d++›會匹配失敗。因為沒有保存任何回溯位置，匹配嚐試失敗。
‹(?>\w+\d+)›在同一個固化分組中擁有兩個貪心量詞。在這個固化分組中，回溯會正常發生。回溯的位置隻有當引擎退出整個分組的時候才會被丟棄。當目標文本是abc123的時候，‹\w+›會匹配abc123。貪心量詞則會記住回溯的位置。當‹\d+›匹配失敗的時候，‹\w+›會主動放棄一個字符。這樣‹\d+›就可以匹配3。現在，引擎會退出這個固化分組，並且丟棄掉為‹\w+›和‹\d+›記住的所有回溯位置。因為此時正則表達式已經到達了結尾，所以沒有其他任務要完成。結果是找到了整體匹配。
如果還沒有到達結尾，如‹(?>\w+\d+)\d+›，我們就會遇到與‹\w++\d++›一樣的情形。在目標文本的結尾處，不存在任何內容可以匹配第二個‹\d+›。因為這時回溯位置已經被丟棄了，所以正則引擎隻能宣布匹配失敗。
占有量詞和固化分組所做的不僅僅是優化正則表達式。它們也會通過排除可以利用回溯完成的匹配，而改變一個正則表達式最終找到的匹配。
本實例展示了如何使用占有量詞和固化分組來進行一些較小的優化，而這些優化在性能測試中甚至可能不會表現出任何區別。下一個實例會講解固化分組如何製造更加顯著的不同。
最後更新：2017-06-02 19:35:49