A Global View of Backtracking
從局部來看，回溯就是倒退至未嘗試的分支。這很容易理解，但是回溯對整個匹配影響並不容易理解。在本節，我們會詳細考察回溯在匹配成功和不成功時的各種細節，嘗試從中發掘出一些東西。
先來仔細看看前一章的幾個例子，在165頁，我們把「〞.＊〞」應用到下面的文本：
The name 〞McDonald\'s〞 is said 〞makudonarudo〞 in Japanese
匹配過程如圖6-3所示。
正則表達式會從字符串的起始位置開始依次嘗試每個字符，但是因為開頭的引號無法匹配，此後的字符也不能匹配，直到嘗試進行到標記位置 A。接著嘗試表達式的其他部分，但是傳動裝置（☞148）知道如果這種嘗試不成功，整個表達式可以從下一個位置開始嘗試。
然後「.＊」匹配直到字符串末尾，此時點號無法匹配，所以星號停止迭代。因為「.＊」匹配成功可以不需要任何字符，所以在此過程中引擎記錄了46個狀態供回溯。現在「.＊」停止了，引擎從最後保存的狀態開始回溯，在
處開始嘗試
。
也就是說，我們在字符串的末尾嘗試匹配表示結束的雙引號。不過，在這裡雙引號同樣無法匹配，所以嘗試仍然失敗。然後引擎繼續回溯、嘗試，結果同樣是無法匹配。
圖6-3：「〞.＊〞」的成功匹配過程
引擎倒過來嘗試（最後保存的狀態排在最先）從A到B保存的狀態，首先是從B到C。在進行了多次嘗試之後到達這個狀態：正則表達式中的
對應字符串中的
·in·Japa…，也就是C所標注的位置。此時匹配成功，於是我們在D位置得到全局匹配。
這就是傳統型NFA的匹配過程，剩下的未使用狀態將被拋棄，報告匹配成功。
POSIX NFA需要更多處理
More Work for a POSIX NFA
我們已經介紹過，POSIX NFA的匹配是「到目前為止最長的匹配」，但是仍然需要嘗試所有保存的狀態，確認是否存在更長的匹配。我們知道，對本例來說，第一次找到的匹配就是最長的，但正則引擎需要確認這一點。
所以，在保存的所有狀態中，除了兩個能夠匹配雙引號的可能之外，其他都會在嘗試後立即被放棄。所以，嘗試過程D-E-F和F-G-H類似B-C-D，只是F和H會被放棄，因為它們匹配的文本比D的要短。
在I位置能進行的回溯是「啟動驅動過程，進行下一輪嘗試（bump-along and retry）」。不過，因為從A位置開始的嘗試能夠找到匹配（實際上是三個），POSIX NFA引擎最終停下來，報告在D位置的匹配。
無法匹配時必須進行的工作
Work Required During a Non-Match
我們還需要分析無法匹配時的情況。我們知道「〞.＊〞！」無法匹配範例文本，但是它在匹配過程中仍然會進行許多工作。我們將會看到，工作量增大了許多。
圖6-4說明了這些。A-I序列類似圖6-3。區別在於，在位置D無法匹配（因為結尾的問號）。另一點區別在於，圖6-4中的整個嘗試序列是傳統型NFA和POSIX NFA都必須經歷的：如果無法匹配，傳統型NFA必須進行的嘗試與POSIX NFA一樣多。
圖6-4：「〞.＊〞！」匹配失敗的經過
因為從開始的A到結束的I的所有嘗試都不存在匹配，傳動裝置必須啟動驅動過程開始新一輪嘗試。從J、Q、V開始的嘗試看來有可能匹配成功，但結果都與從A開始的嘗試一樣。最終到Y，不存在繼續嘗試的途徑，所以整個嘗試宣告失敗。如圖6-4所示，得到這個結果花費了許多工夫。
看清楚一點
Being More Specific
我們把點號換成「[^〞]」來做個比較。前一章已經討論過，這樣的結果更容易理解，因為它能匹配的字符更少，而且這樣一來，正則表達式的效率也提高了。如果使用「〞[^〞]＊〞！」，「[^〞]＊」匹配的內容就不能包括雙引號，減少了匹配和回溯。
圖6-5說明了嘗試失敗的過程（請對比圖6-4）。從圖中可以看到，回溯的次數大大減少了。如果這個結果滿足我們的需要，減少的回溯就是有益的伴隨效應（side effect）。
圖6-5：「〞[^〞]＊〞！」無法匹配
多選結構的代價很高
Alternation Can Be Expensive
多選結構或許是回溯的主要原因。舉個簡單的例子，用makudonarudo來比較「u|v|w|x|y|z」和「[uvwxyz]」的匹配。字符組一般只是進行簡單測試（注3），所以「[uvwxyz]」只需要進行34次嘗試就能匹配。
如果使用「u|v|w|x|y|z」，則需要在每個位置進行6次回溯，在得到同樣結果之前總共有204次回溯。當然，並不是每個多選結構都可以替換為字符組，即使可以，也不見得會這麼簡單。不過，在某些情況下，我們將要學習的技巧能夠大大減少與匹配所須的多選結構相關的回溯。
理解回溯可能是學習NFA效率中最重要的問題，但所有的問題不只於此。正則引擎的優化措施能夠大大提升效率。在本章後面，我們將詳細考察正則引擎要做的工作和優化手段。