回溯

Backtracking

NFA 引擎最重要的性質是，它會依次處理各個子表達式或組成元素，遇到需要在兩個可能成功的可能中進行選擇的時候，它會選擇其一，同時記住另一個，以備稍後可能的需要。

需要做出選擇的情形包括量詞（決定是否嘗試另一次匹配）和多選結構（決定選擇哪個多選分支，留下哪個稍後嘗試）。

不論選擇那一種途徑，如果它能匹配成功，而且正則表達式的餘下部分也成功了，匹配即告完成。如果正則表達式中餘下的部分最終匹配失敗，引擎會知道需要回溯到之前做出選擇的地方，選擇其他的備用分支繼續嘗試。這樣，引擎最終會嘗試表達式的所有可能途徑（或者是匹配完成之前需要的所有途徑）。

真實世界中的例子：麵包屑

A Really Crummy Analogy

回溯就像是在道路的每個分岔口留下一小堆麵包屑。如果走了死路，就可以照原路返回，直到遇見麵包屑標示的尚未嘗試過的道路。如果那條路也走不通，你可以繼續返回，找到下一堆麵包屑，如此重複，直到找到出路，或者走完所有沒有嘗試過的路。

在許多情況下，正則引擎必須在兩個（或更多）選項中做出選擇——我們之前看到的分支的情況就是一例。另一個例子是，在遇到「…x？…」時，引擎必須決定是否嘗試匹配「x」。對於「…x+…」的情況，毫無疑問，「x」至少嘗試匹配一次——因為加號要求必須匹配至少一次。第一個「x」匹配之後，此要求已經滿足，需要決定是否嘗試下一個「x」。如果決定進行，還要決定是否匹配第三個「x」，第四個「x」，如此繼續。每次選擇，其實就是灑下一堆「麵包屑」，用於提示此處還有另一個可能的選擇（目前還不能確定它能否匹配），保留起來以備用。

一個簡單的例子

現在來看個完整的例子，用先前的「to（nite|knight|night）」匹配字符串『hot·tonic· tonight！』（看起來有點無聊，但是個好例子）。第一個元素「t」從字符串的最左端開始嘗試，因為無法匹配『h』，所以在這個位置匹配失敗。傳動裝置於是驅動引擎向後移動，從第二個位置開始匹配（同樣也會失敗），然後是第三個。這時候「t」能夠匹配，接下來的「o」無法匹配，因為字符串中對應位置是一個空格。至此，本輪嘗試宣告失敗。

繼續下去，從…☞tonic…開始的嘗試則很有意思。to匹配成功之後，剩下的3 個多選分支都成為可能。引擎選取其中之一進行嘗試，留下其他的備用（也就是灑下一些麵包屑）。在討論中，我們假定引擎首先選擇的是「nite」。這個表達式被分解為「「n」+「i」+「t」+「e」」，在…遭遇失敗。但此時的情況與之前不同，這種失敗並不意味著整個表達式匹配失敗——因為仍然存在沒有嘗試過的多選分支（就好像是，我們仍然可以找到先前留下的麵包屑）。假設引擎然後選擇「knight」，那麼馬上就會遭遇失敗，因為「k」不能匹配『n』。現在只剩下最後的選項「night」，但它不能失敗。因為「night」是最後嘗試的選項，它的失敗也就意味著整個表達式在…☞tonic…的位置匹配失敗，所以傳動機構會驅動引擎繼續前進。

直到引擎開始從…☞tonight！處開始匹配，情況又變得有趣了。這一次，多選分支「night」終於可以匹配字符串的結尾部分了（於是整體匹配成功，現在引擎可以報告匹配成功了）。

回溯的兩個要點

Two Important Points on Backtracking

回溯機制的基本原理並不難理解，還是有些細節對實際應用很重要。它們是，面對眾多選擇時，哪個分支應當首先選擇？回溯進行時，應該選取哪個保存的狀態？第一個問題的答案是下面這條重要原則：

如果需要在「進行嘗試」和「跳過嘗試」之間選擇，對於匹配優先量詞，引擎會優先選擇「進行嘗試」，而對於忽略優先量詞，會選擇「跳過嘗試」。

此原則影響深遠。對於新手來說，它有助於解釋為什麼匹配優先的量詞是「匹配優先」的，但還不完整。要想徹底弄清楚這一點，我們需要瞭解回溯時使用的是哪個（或者是哪些個）之前保存的分支，答案是：

距離當前最近儲存的選項就是當本地失敗強制回溯時返回的。使用的原則是LIFO（last in first out，後進先出）。

用麵包屑比喻就很好理解——如果前面是死路，你只需要沿原路返回，直到找到一堆麵包屑為止。你會遇到的第一堆麵包屑就是最近灑下的。傳統的LIFO比喻也是這樣：就像堆疊盤子一樣，最後疊上去的盤子肯定是最先拿下來的。

備用狀態

Saved States

用NFA正則表達式的術語來說，那些麵包屑相當於「備用狀態（saved state）」。它們用來標記：在需要的時候，匹配可以從這裡重新開始嘗試。它們保存了兩個位置：正則表達式中的位置，和未嘗試的分支在字符串中的位置。因為它是NFA匹配的基礎，我們需要再看一遍某些已經出現過的簡單但詳細的例子，說明這些狀態的意義。如果你覺得現有的內容都不難懂，請繼續閱讀。

未進行回溯的匹配

來看個簡單的例子，用「ab？c」匹配abc。「a」匹配之後，匹配的當前狀態如下：

現在輪到「b？」了，正則引擎需要決定：是需要嘗試「b」呢，還是跳過？因為？是匹配優先的，它會嘗試匹配。但是，為了確保在這個嘗試最終失敗之後能夠恢復，引擎會把：

添加到備用狀態序列中。也就是說，稍後引擎可以從下面的位置繼續匹配：從正則表達式中的「b？」之後，字符串的b之前（也就是當前的位置）匹配。這實際上就是跳過「b」的匹配，而問號容許這樣做。

引擎放下麵包屑之後，就會繼續向前，檢查「b」。在示例文本中，它能夠匹配，所以新的當前狀態變為：

最終的「c」也能成功匹配，所以整個匹配完成。備用狀態不再需要了，所以不再保存它們。

進行了回溯的匹配

如果需要匹配的文本是『ac』，在嘗試「b」之前，一切都與之前的過程相同。顯然，這次「b」無法匹配。也就是說，對「…？」進行嘗試的路走不通。因為有一個備用狀態，這個「局部匹配失敗」並不會導致整體匹配失敗。引擎會進行回溯，也就是說，把「當前狀態」切換為最近保存的狀態。在本例中，情況就是：

在「b」嘗試之前保存的尚未嘗試的選項。這時候，「c」可以匹配c，所以整個匹配宣告完成。

不成功的匹配

現在，我們用同樣的表達式匹配『abX』。在嘗試「b」以前，因為存在問號，保存了這個備用狀態：

「b」能夠匹配，但這條路往下卻走不通了，因為「c」無法匹配X。於是引擎會回溯到之前的狀態，「交還」b給「c」來匹配。顯然，這次測試也失敗了。如果還有其他保存的狀態，回溯會繼續進行，但是此時不存在其他狀態，在字符串中當前位置開始的整個匹配也就宣告失敗。

事情到此結束了嗎？沒有。傳動裝置會繼續「在字符串中前行，再次嘗試正則表達式」，這可能被想像為一個偽回溯（pseudo-backtrack）。匹配重新開始於：

從這裡重新開始整個匹配，如同之前一樣，所有的道路都走不通。接下來的兩次（從到）都告失敗，所以最終會報告匹配失敗。

忽略優先的匹配

現在來看最開始的例子，使用忽略優先匹配量詞，用「ab？？c」來匹配『abc』。「a」匹配之後的狀態如下：

接下來輪到「b？？」，引擎需要進行選擇：嘗試匹配「b」，還是忽略？因為？？是忽略優先的，它會首先嘗試忽略，但是，為了能夠從失敗的分支中恢復，引擎會保存下面的狀態：

到備用狀態列表中。於是，引擎稍後能夠用正則表達式中的「b」來嘗試匹配文本中的 b（我們知道這能夠匹配，但是正則引擎不知道，它甚至都不知道是否會要用到這個備用狀態）。狀態保存之後，它會繼續向前，沿著忽略匹配的路走下去：

「c」無法匹配『b』，所以引擎必須回溯到之前保存的狀態：

顯然，此時匹配可以成功，接下來的「c」匹配『c』。於是我們得到了與使用匹配優先的「ab？c」同樣的結果，雖然兩者所走的路不相同。

回溯與匹配優先

Backtracking and Greediness

如果工具軟件使用的是NFA正則表達式主導的回溯引擎，理解正則表達式的回溯原理就成了高效完成任務的關鍵。我們已經看到「？」的匹配優先和「？？」的忽略優先是如何工作的，現在來看星號和加號。

星號、加號及其回溯

如果認為「x＊」基本等同於「x？x？x？x？x？x？…」（或者更確切地說是「（x（x（x（x…？）？）？）？）？）」） （注 5），那麼情況與之前沒有大的差別。每次測試星號作用的元素之前，引擎都會保存一個狀態，這樣，如果測試失敗（或者測試進行下去遭遇失敗），還能夠從保存的狀態開始匹配。這個過程會不斷重複，直到包含星號的嘗試完全失敗為止。

所以，如果用「[0-9]+」來匹配『a·1234·num』，「[0-9]」遇到4之後的空格無法匹配，而此時加號能夠回溯的位置對應了四個保存的狀態：

也就是說，在每個位置，「[0-9]」的嘗試都代表一種可能。在「[0-9]」遇到空格匹配失敗時，引擎回溯到最近保存的狀態（也就是最下面的位置），選擇正則表達式中的和文本中的』。當然，到此整個正則表達式已經結束，所以我們知道，整個匹配宣告完成。

請注意，』並不在列表中，因為加號限定的元素至少要匹配一次，這是必要條件。那麼，如果正則表達式是，這個狀態會保存嗎？（提示：這個問題得動點腦筋）。要知道答案，ϖ請翻到下一頁。

重新審視更完整的例子

有了更詳細的瞭解之後，我們再來看看第 152 頁的「^.＊（[0-9][0-9]）」的例子。這一次，我們不是只用「匹配優先」來解釋為什麼會得到那樣的匹配結果，我們能夠根據NFA的匹配機制做出精確解釋。

以『CA·95472·USA』為例。在「.＊」成功匹配到字符串的末尾時，星號約束的點號匹配了13個字符，同時保存了許多備用狀態。這些狀態表明稍後的匹配開始的位置：在正則表達式中是，在字符串中則是點號每次匹配時保存的備用狀態。

現在我們已經到了字符串的末尾，並把控制權交給第一個「[0-9]」，顯然這裡的匹配不能成功。沒問題，我們可以選擇一個保存的狀態來進行嘗試（實際上保存了許多的狀態）。現在回溯開始，把當前狀態設置為最近保存的狀態，也就是「.＊」匹配最後的 A 之前的狀態。忽略（或者，如果你願意，可以使用「交還」）這個匹配，於是有機會用「[0-9]」匹配這個A，但這同樣會失敗。

這種「回溯-嘗試」的過程會不斷循環，直到引擎交還2為止，在這裡，第一個「[0-9]」可以匹配。但是第二個「[0-9]」仍然無法匹配，所以必須繼續回溯。現在，之前嘗試中第一個「[0-9]」是否匹配與本次嘗試並無關係了，回溯機制會把當前的狀態中正則表達式內的對應位置設置到第一個「[0-9]」以前。我們看到，當前的回溯同樣會把字符串中的位置設置到7以前，所以第一個「[0-9]」可以匹配，而第二個「[0-9]」也可以（匹配2）。所以，我們得到一個匹配結果』，$1得到72。

需要注意的是：第一，回溯機制不但需要重新計算正則表達式和文本的對應位置，也需要維護括號內的子表達式所匹配文本的狀態。在匹配過程中，每次回溯都把當前狀態中正則表達式的對應位置指向括號之前，也就是「^.＊☞（[0-9][0-9]）」。在這個簡單的例子中，所以它等價於，因此我說「使用第一個[0-9]之前的位置」。然而，回溯對括號的這種處理，不但需要同時維護$1的狀態，也會影響匹配的效率。

最後需要注意的一點也許讀者早就瞭解：由星號（或其他任何匹配優先量詞）限定的部分不受後面元素影響，而只是匹配盡可能多的內容。在我們的例子中，「.＊」在點號匹配失敗之前，完全不知道，到底應該在哪個數字或者是其他什麼地方停下來。在「^.＊（[0-9]+）」的例子中我們看到，「[0-9]+」只能匹配一位數字（☞153）。