本文實例分析了正規中的回溯定義與用法。分享給大家供大家參考，具體如下：
關於「回溯」我也是第一次接觸，對它也不算很了解。下面就把我所了解的做為一個心德記錄下來，以備查看。
我們所使用的正規表示式的匹配基礎大概分為：優先選擇最左端（最靠開頭）的匹配結果和標準的匹配量詞（*、+、？和{m, n}）是符合優先的。
「優先選擇最左端的匹配」顧名思義就是從字串的起始位置開始匹配直到匹配結束這是基礎；「標準匹配量詞」又分為「非確定型有窮自動機（NFA）」也可以叫做「表達式主導」；另外一種是「確定型有窮自動機（DFA）」也可以叫做「文本主導」。我們目前在JavaScript中所使用的正規表示式為「表達式主導」。表達式主導和文字主導解釋起來有些麻煩，先看來一個例子可能會很清楚。
// 使用正则表达式匹配文本 var reg = /to(nite|knight|night)/; var str = 'doing tonight'; reg.test(str);
在上面的這個例子中，第一個元素[t]，它將會重複嘗試，直到目標字串中找到‘t'為止。之後，就檢查緊接而來的字元是否能由[o]匹配，如果能，就檢查下面的元素（nite|knight|night）。它的真正意義是“nite”或“knight”或“night”。引擎會依序嘗試這3種可能。嘗試[nite]的過程是先嘗試[n]，然後[i]，然後[t]，最後是[e]。如果這種嘗試失敗，引擎會嘗試另一種可能，如此繼續下去，直到匹配成功或是報告失敗。表達式中的控制權在不同的元素之間轉換，所以稱為「表達式主導」。
同樣是上面的例子「文字主導」在掃描字串時，會記錄目前有效的所有匹配可。當引擎移動到t時，它會在當前處理的匹配可能中添加一個潛在的可能：
接下來掃描的每個字符，都會更新當前的可能匹配序列。繼續掃描兩個字元以後的情況是：
有效的可能匹配變為兩個（knight被淘汰出局）。掃描到g時，就只剩下一個可能匹配了。當h和t匹配完成後，引擎發現匹配已經完成，報告成功。 「文字主導」是因為它掃描的字串中的每個字元都對引擎進行了控制。
如果想要弄清楚「表達式主導」是如何運作的，那就要看一下我們今天的主題「回溯（backtracking）」。回溯就像是走岔路口，當遇到岔路的時候就先在每個路口做一個記號。如果走了死路，就可以照原路返回，直到遇見之前所做過的標記，標記著還未嘗試過的道路。如果那條路也走不能，可以繼續返回，找到下一個標記，如此重複，直到找到出路，或直到完成所有沒有嘗試過的路。
在許多情況下，正規引擎必須在兩個（或更多）選項中做出選擇。當遇到/……x?……/時，引擎必須是否嘗試匹配X。對於/……X+……/的情況，毫無疑問，X至少嘗試匹配一次——因為加號要求必須至少匹配一次。第一個X匹配之後，此要求已經滿足，需要決定是否嘗試下一個X。如果決定進行，還要決定是否要配對第三個X，第四個X，如此繼續。每次選擇，其實就是做一個標記，用於提示此處還有另一個可能的選擇，保留起來以備用。在回溯的過程中要考慮兩個要點：哪個分支要先選擇？回溯的時候使用的是哪個（或者是哪些個）之前保存的分支？
第一個問題是按下面這條重要原則來選擇的：
如果需要在“進行嘗試”和“路過嘗試”之間選擇，對於匹配優先量詞，引擎會優先選擇“進行嘗試”，而對於忽略優先量詞，會選擇「路過嘗試」。
第二個問題是按以下這條原則：
距離目前最近儲存的選項就是當本地失敗強制回溯時返回的。使用的原則是LIFO（last in first out，後進先出）。
我們先來看幾個在道路中做標記的例子：
1、未進行回溯的匹配
用[ab?c]來匹配「abc」。 [a]匹配之後，匹配的當前狀態如下：
现在轮到[b?]了，正则引擎需要决定：是需要尝试[b]呢，还是跳过？因为[？]是匹配优先的，它会尝试匹配。但是，为了确保在这个尝试最终失败之后能够恢复，引擎会把：
添加到备用状态序列中。也就是说，稍后引擎可能从下面的位置继续匹配：从正则表达式中的[b?]之后，字符串的c之前（也就是说当前的位置）匹配。这实际上就是跳过[b]的匹配，而问题容许这样做。引擎做好标记后，就会继续向前检查[b]。在示例中，它能够匹配，所以新的当前状态变为：
最终的[c]也能成功匹配，所以整个匹配完成。备用状态不再需要了，所以不再保存它们。
2、进行了回溯的匹配
下面要匹配的文本是“ac”，在尝试[b]之前，一切都与之前的过程相同。显然，这次[b]无法匹配。也就是说，对[……？]进行尝试的路走不通了。因为有一个备用状态，这个“局部匹配失败”产工会导致整体匹配失败。引擎会进行回溯，也就是说，把“当前状态”切换为最近保存的状态。
在[b]尝试之前保存的尚未尝试的选项。这时候，[c]可以匹配c，所以整个匹配宣告完成。
3、不成功的匹配
现在要匹配的文本是“abx”。在尝试[b]以前，因为存在问号，保存了这个备用状态：
[b]能够匹配，但这条路往下却走不通了，因为[c]无法匹配x。于是引擎会回溯到之前的状态，“交还”b给[c]来匹配。显然，这次测试也失败了。如果还有其他保存的状态，回溯会继续进行，但是此时不存在其他状态，在字符串中当前位置开始的整个匹配也就宣告失败。
例子1： 提取字符串 提取 da12bka3434bdca4343bdca234bm 提取包含在字符a和b之间的数字，但是这个a之前的字符不能是c,b后面的字符必须是d才能提取。
例如这里就只有3434这个数字满足要求。那么我们怎么提取呢？
首先我们写出提取这个字符串的表达式： (?
Java代码片段如下：
Pattern p = Pattern.compile( "(?<!c)a(//d+)bd " );
Matcher m = p.matcher( "da12bka3434bdca4343bdca234bm" );
while (m.find()){
System.out.println(m.group( 1 )); //我们只要捕获组1的数字即可。结果 3434
System.out.println(m.group(0)); // 0组是整个表达式，看这里，并没有提炼出(?<!c)的字符 。结果 a3434bd
}例子2： 将一些多位的小数截短到三位小数：\d+\.\d\d[1-9]?\d+
在这种条件下 6.625 能进行匹配，这样做没有必要，因为它本身就是三位小数。最后一个“5”本来是给 [1-9] 匹配的，但是后面还有一个 \d+ 所以，[1-9] 由于是“?”可以不匹配所以只能放弃当前的匹配，将这个“5”送给 \d+ 去匹配，如果改为：
\d+\.\d\d[1-9]?+\d+
的侵占形式，在“5”匹配到 [1-9] 时，由于是侵占式的，所以不会进行回溯，后面的 \d+ 就匹配不到任东西了，所以导致 6.625 匹配失败。
这种情况，在替换时就有效了，比如把数字截短到小数点后三位，如果正好是三位小数的，就可以不用替换了，可以提高效率，侵占量词基本上就是用来提高匹配效率的。
把 \d+\.\d\d[1-9]?+\d+ 改为 \d+\.\d\d(?>[1-9]?)\d+ 这样是一样的。
希望本文所述对大家JavaScript程序设计有所帮助。
更多正規中的回溯定義與用法分析【JS與java實作】相关文章请关注PHP中文网！
