| 字符串中的位置 | 正則表達中的位置 |
| ……doing tonight | 可能的匹配位置：/t↑o(nite|knight|nigth)/ |
接下來掃描的每個字符，都會更新當前的可能匹配序列。繼續(xù)掃描兩個字符以后的情況是：
| 字符串中的位置 | 正則表達中的位置 |
| ……doing tonight | 可能的匹配位置：/to(ni↑te|knight|ni↑gth)/ |
有效的可能匹配變?yōu)閮蓚€（knight被淘汰出局）。掃描到g時，就只剩下一個可能匹配了。當h和t匹配完成后，引擎發(fā)現(xiàn)匹配已經(jīng)完成，報告成功。“文本主導(dǎo)”是因為它掃描的字符串中的每個字符都對引擎進行了控制。
如果想要弄明白“表達式主導(dǎo)”是如何工作的，那就要看一下我們今天的主題“回溯（backtracking）”。回溯就像是在走岔路口，當遇到岔路的時候就先在每個路口做一個標記。如果走了死路，就可以照原路返回，直到遇見之前所做過的標記，標記著還未嘗試過的道路。如果那條路也走不能，可以繼續(xù)返回，找到下一個標記，如此重復(fù)，直到找到出路，或者直到完成所有沒有嘗試過的路。
在許多情況下，正則引擎必須在兩個（或更多）選項中做出選擇。當遇到/……x?……/時，引擎必須是否嘗試匹配X。對于/……X+……/的情況，毫無疑問，X至少嘗試匹配一次——因為加號要求必須匹配至少一次。第一個X匹配之后，此要求已經(jīng)滿足，需要決定是否嘗試下一個X。如果決定進行，還要決定是否匹配第三個X，第四個X，如此繼續(xù)。每次選擇，其實就是做一個標記，用于提示此處還有另一個可能的選擇，保留起來以備用。在回溯的過程中要考慮兩個要點：哪個分支應(yīng)當首先選擇？回溯的時候使用的是哪個（或者是哪些個）之前保存的分支？
第一個問題是按下面這條重要原則來選擇的：
如果需要在“進行嘗試”和“路過嘗試”之間選擇，對于匹配優(yōu)先量詞，引擎會優(yōu)先選擇“進行嘗試”，而對于忽略優(yōu)先量詞，會選擇“路過嘗試”。
第二個問題是按以下這條原則：
距離當前最近儲存的選項就是當本地失敗強制回溯時返回的。使用的原則是LIFO（last in first out，后進先出）。
我們先來看幾個在道路中做標記的例子：
1、未進行回溯的匹配
用[ab?c]來匹配“abc”。[a]匹配之后，匹配的當前狀態(tài)如下：
| “a↑bc” | a↑b?c |
現(xiàn)在輪到[b?]了，正則引擎需要決定：是需要嘗試[b]呢，還是跳過？因為[？]是匹配優(yōu)先的，它會嘗試匹配。但是，為了確保在這個嘗試最終失敗之后能夠恢復(fù)，引擎會把：
| “a↑bc” | ab?↑c |
| “ab↑c” | ab?↑c |
最終的[c]也能成功匹配，所以整個匹配完成。備用狀態(tài)不再需要了，所以不再保存它們。
2、進行了回溯的匹配
下面要匹配的文本是“ac”，在嘗試[b]之前，一切都與之前的過程相同。顯然，這次[b]無法匹配。也就是說，對[……？]進行嘗試的路走不通了。因為有一個備用狀態(tài)，這個“局部匹配失敗”產(chǎn)工會導(dǎo)致整體匹配失敗。引擎會進行回溯，也就是說，把“當前狀態(tài)”切換為最近保存的狀態(tài)。
| “a↑c” | ab?↑c |
在[b]嘗試之前保存的尚未嘗試的選項。這時候，[c]可以匹配c，所以整個匹配宣告完成。
3、不成功的匹配
現(xiàn)在要匹配的文本是“abx”。在嘗試[b]以前，因為存在問號，保存了這個備用狀態(tài)：
| “a↑bx” | ab?↑c |
[b]能夠匹配，但這條路往下卻走不通了，因為[c]無法匹配x。于是引擎會回溯到之前的狀態(tài)，“交還”b給[c]來匹配。顯然，這次測試也失敗了。如果還有其他保存的狀態(tài)，回溯會繼續(xù)進行，但是此時不存在其他狀態(tài)，在字符串中當前位置開始的整個匹配也就宣告失敗。
目前對正則表達式的回溯只能理解這么多，以后我再慢慢補充吧！
