本文實(shí)例分析了正則中的回溯定義與用法。分享給大家供大家參考，具體如下：

關(guān)于“回溯”我也是第一次接觸，對(duì)它也不算很了解。下面就把我所了解的做為一個(gè)心德記錄下來，以備查看。

我們所使用的正則表達(dá)式的匹配基礎(chǔ)大概分為：優(yōu)先選擇最左端（最靠開頭）的匹配結(jié)果和標(biāo)準(zhǔn)的匹配量詞（*、+、？和{m, n}）是匹配優(yōu)先的。

“優(yōu)先選擇最左端的匹配”顧名思義就是從字符串的起始位置開始匹配直到匹配結(jié)束這是基礎(chǔ)；“標(biāo)準(zhǔn)匹配量詞”又分為“非確定型有窮自動(dòng)機(jī)（NFA）”也可以叫做“表達(dá)式主導(dǎo)”；另外一種是“確定型有窮自動(dòng)機(jī)（DFA）”也可以叫做“文本主導(dǎo)”。我們目前在JavaScript中所使用的正則表達(dá)式為“表達(dá)式主導(dǎo)”。表達(dá)式主導(dǎo)和文本主導(dǎo)解釋起來有些麻煩，先看來一個(gè)例子可能會(huì)清楚些。

// 使用正則表達(dá)式匹配文本
var reg = /to(nite|knight|night)/;
var str = 'doing tonight';
reg.test(str);

在上面的這個(gè)例子中，第一個(gè)元素[t]，它將會(huì)重復(fù)嘗試，直到目標(biāo)字符串中找到‘t'為止。之后，就檢查緊隨其后的字符是否能由[o]匹配，如果能，就檢查下面的元素（nite|knight|night）。它的真正含義是“nite”或者“knight”或者“night”。引擎會(huì)依次嘗試這3種可能。嘗試[nite]的過程是先嘗試[n]，然后[i]，然后[t]，最后是[e]。如果這種嘗試失敗，引擎會(huì)嘗試另一種可能，如此繼續(xù)下去，直到匹配成功或是報(bào)告失敗。表達(dá)式中的控制權(quán)在不同的元素之間轉(zhuǎn)換，所以稱為“表達(dá)式主導(dǎo)”。

同樣是上面的例子“文本主導(dǎo)”在掃描字符串時(shí)，會(huì)記錄當(dāng)前有效的所有匹配可。當(dāng)引擎移動(dòng)到t時(shí)，它會(huì)在當(dāng)前處理的匹配可能中添加一個(gè)潛在的可能：

接下來掃描的每個(gè)字符，都會(huì)更新當(dāng)前的可能匹配序列。繼續(xù)掃描兩個(gè)字符以后的情況是：

有效的可能匹配變?yōu)閮蓚€(gè)（knight被淘汰出局）。掃描到g時(shí)，就只剩下一個(gè)可能匹配了。當(dāng)h和t匹配完成后，引擎發(fā)現(xiàn)匹配已經(jīng)完成，報(bào)告成功?！拔谋局鲗?dǎo)”是因?yàn)樗鼟呙璧淖址械拿總€(gè)字符都對(duì)引擎進(jìn)行了控制。

如果想要弄明白“表達(dá)式主導(dǎo)”是如何工作的，那就要看一下我們今天的主題“回溯（backtracking）”?；厮菥拖袷窃谧卟砺房冢?dāng)遇到岔路的時(shí)候就先在每個(gè)路口做一個(gè)標(biāo)記。如果走了死路，就可以照原路返回，直到遇見之前所做過的標(biāo)記，標(biāo)記著還未嘗試過的道路。如果那條路也走不能，可以繼續(xù)返回，找到下一個(gè)標(biāo)記，如此重復(fù)，直到找到出路，或者直到完成所有沒有嘗試過的路。

在許多情況下，正則引擎必須在兩個(gè)（或更多）選項(xiàng)中做出選擇。當(dāng)遇到/……x?……/時(shí)，引擎必須是否嘗試匹配X。對(duì)于/……X+……/的情況，毫無疑問，X至少嘗試匹配一次——因?yàn)榧犹?hào)要求必須匹配至少一次。第一個(gè)X匹配之后，此要求已經(jīng)滿足，需要決定是否嘗試下一個(gè)X。如果決定進(jìn)行，還要決定是否匹配第三個(gè)X，第四個(gè)X，如此繼續(xù)。每次選擇，其實(shí)就是做一個(gè)標(biāo)記，用于提示此處還有另一個(gè)可能的選擇，保留起來以備用。在回溯的過程中要考慮兩個(gè)要點(diǎn)：哪個(gè)分支應(yīng)當(dāng)首先選擇？回溯的時(shí)候使用的是哪個(gè)（或者是哪些個(gè)）之前保存的分支？

第一個(gè)問題是按下面這條重要原則來選擇的：

如果需要在“進(jìn)行嘗試”和“路過嘗試”之間選擇，對(duì)于匹配優(yōu)先量詞，引擎會(huì)優(yōu)先選擇“進(jìn)行嘗試”，而對(duì)于忽略優(yōu)先量詞，會(huì)選擇“路過嘗試”。

第二個(gè)問題是按以下這條原則：

距離當(dāng)前最近儲(chǔ)存的選項(xiàng)就是當(dāng)本地失敗強(qiáng)制回溯時(shí)返回的。使用的原則是LIFO（last in first out，后進(jìn)先出）。

我們先來看幾個(gè)在道路中做標(biāo)記的例子：

1、未進(jìn)行回溯的匹配

用[ab?c]來匹配“abc”。[a]匹配之后，匹配的當(dāng)前狀態(tài)如下：

現(xiàn)在輪到[b?]了，正則引擎需要決定：是需要嘗試[b]呢，還是跳過？因?yàn)閇？]是匹配優(yōu)先的，它會(huì)嘗試匹配。但是，為了確保在這個(gè)嘗試最終失敗之后能夠恢復(fù)，引擎會(huì)把：

2、進(jìn)行了回溯的匹配

下面要匹配的文本是“ac”，在嘗試[b]之前，一切都與之前的過程相同。顯然，這次[b]無法匹配。也就是說，對(duì)[……？]進(jìn)行嘗試的路走不通了。因?yàn)橛幸粋€(gè)備用狀態(tài)，這個(gè)“局部匹配失敗”產(chǎn)工會(huì)導(dǎo)致整體匹配失敗。引擎會(huì)進(jìn)行回溯，也就是說，把“當(dāng)前狀態(tài)”切換為最近保存的狀態(tài)。

3、不成功的匹配

現(xiàn)在要匹配的文本是“abx”。在嘗試[b]以前，因?yàn)榇嬖趩柼?hào)，保存了這個(gè)備用狀態(tài)：

例子1： 提取字符串   提取 da12bka3434bdca4343bdca234bm   提取包含在字符a和b之間的數(shù)字，但是這個(gè)a之前的字符不能是c,b后面的字符必須是d才能提取。

例如這里就只有3434這個(gè)數(shù)字滿足要求。那么我們?cè)趺刺崛∧兀?/p>

首先我們寫出提取這個(gè)字符串的表達(dá)式： (?<!c)a(/d+)bd  這里就只有一個(gè)捕獲組(/d+)

Java代碼片段如下：

Pattern p = Pattern.compile( "(?<!c)a(//d+)bd " );
Matcher m = p.matcher( "da12bka3434bdca4343bdca234bm" );
 while (m.find()){
 System.out.println(m.group( 1 )); //我們只要捕獲組1的數(shù)字即可。結(jié)果 3434
 System.out.println(m.group(0)); // 0組是整個(gè)表達(dá)式，看這里，并沒有提煉出(?<!c)的字符 。結(jié)果 a3434bd
}

例子2： 將一些多位的小數(shù)截短到三位小數(shù)：\d+\.\d\d[1-9]?\d+

在這種條件下 6.625 能進(jìn)行匹配，這樣做沒有必要，因?yàn)樗旧砭褪侨恍?shù)。最后一個(gè)“5”本來是給 [1-9] 匹配的，但是后面還有一個(gè) \d+ 所以，[1-9] 由于是“?”可以不匹配所以只能放棄當(dāng)前的匹配，將這個(gè)“5”送給 \d+ 去匹配，如果改為：

\d+\.\d\d[1-9]?+\d+

的侵占形式，在“5”匹配到 [1-9] 時(shí)，由于是侵占式的，所以不會(huì)進(jìn)行回溯，后面的 \d+ 就匹配不到任東西了，所以導(dǎo)致 6.625 匹配失敗。

這種情況，在替換時(shí)就有效了，比如把數(shù)字截短到小數(shù)點(diǎn)后三位，如果正好是三位小數(shù)的，就可以不用替換了，可以提高效率，侵占量詞基本上就是用來提高匹配效率的。

把 \d+\.\d\d[1-9]?+\d+ 改為 \d+\.\d\d(?>[1-9]?)\d+ 這樣是一樣的。

PS：這里再為大家提供2款非常方便的正則表達(dá)式工具供大家參考使用：

JavaScript正則表達(dá)式在線測(cè)試工具：
http://tools.jb51.net/regex/javascript

正則表達(dá)式在線生成工具：
http://tools.jb51.net/regex/create_reg

更多關(guān)于JavaScript相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《JavaScript正則表達(dá)式技巧大全》、《JavaScript替換操作技巧總結(jié)》、《JavaScript查找算法技巧總結(jié)》、《JavaScript數(shù)據(jù)結(jié)構(gòu)與算法技巧總結(jié)》、《JavaScript遍歷算法與技巧總結(jié)》、《JavaScript中json操作技巧總結(jié)》、《JavaScript錯(cuò)誤與調(diào)試技巧總結(jié)》及《JavaScript數(shù)學(xué)運(yùn)算用法總結(jié)》

希望本文所述對(duì)大家JavaScript程序設(shè)計(jì)有所幫助。

最新評(píng)論