主頁(yè) > 知識(shí)庫(kù) > 正則表達(dá)式之回溯

正則表達(dá)式之回溯

熱門標(biāo)簽:惠安地圖標(biāo)注 浙江營(yíng)銷外呼系統(tǒng)有哪些 上海銷售電銷機(jī)器人軟件 自己做的電銷機(jī)器人 地圖標(biāo)注店鋪地圖標(biāo)注酒店 遼寧秒客來(lái)電話機(jī)器人 山東外呼系統(tǒng)聯(lián)系方式 淄博市張店區(qū)地圖標(biāo)注 哈爾濱公司外呼系統(tǒng)代理
關(guān)于“回溯”我也是第一次接觸,對(duì)它也不算很了解。下面就把我所了解的做為一個(gè)心德記錄下來(lái),以備查看。

我們所使用的正則表達(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)解釋起來(lái)有些麻煩,先看來(lái)一個(gè)例子可能會(huì)清楚些。

復(fù)制代碼 代碼如下:

// 使用正則表達(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]的過(guò)程是先嘗試[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è)潛在的可能:

字符串中的位置 正則表達(dá)中的位置
……doing tonight 可能的匹配位置:/to(nite|knight|nigth)/

 

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

 

字符串中的位置 正則表達(dá)中的位置
……doing tonight 可能的匹配位置:/to(nite|knight|nigth)/

 

有效的可能匹配變?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)記。如果走了死路,就可以照原路返回,直到遇見之前所做過(guò)的標(biāo)記,標(biāo)記著還未嘗試過(guò)的道路。如果那條路也走不能,可以繼續(xù)返回,找到下一個(gè)標(biāo)記,如此重復(fù),直到找到出路,或者直到完成所有沒有嘗試過(guò)的路。

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

    第一個(gè)問(wèn)題是按下面這條重要原則來(lái)選擇的:

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

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

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

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

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

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

“abc” ab?c

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

“abc” ab?c
            添加到備用狀態(tài)序列中。也就是說(shuō),稍后引擎可能從下面的位置繼續(xù)匹配:從正則表達(dá)式中的[b?]之后,字符串的c之前(也就是說(shuō)當(dāng)前的位置)匹配。這實(shí)際上就是跳過(guò)[b]的匹配,而問(wèn)題容許這樣做。引擎做好標(biāo)記后,就會(huì)繼續(xù)向前檢查[b]。在示例中,它能夠匹配,所以新的當(dāng)前狀態(tài)變?yōu)椋?
“abc” ab?c

            最終的[c]也能成功匹配,所以整個(gè)匹配完成。備用狀態(tài)不再需要了,所以不再保存它們。

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

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

“ac” ab?c

            在[b]嘗試之前保存的尚未嘗試的選項(xiàng)。這時(shí)候,[c]可以匹配c,所以整個(gè)匹配宣告完成。

        3、不成功的匹配

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

“abx” ab?c

            [b]能夠匹配,但這條路往下卻走不通了,因?yàn)閇c]無(wú)法匹配x。于是引擎會(huì)回溯到之前的狀態(tài),“交還”b給[c]來(lái)匹配。顯然,這次測(cè)試也失敗了。如果還有其他保存的狀態(tài),回溯會(huì)繼續(xù)進(jìn)行,但是此時(shí)不存在其他狀態(tài),在字符串中當(dāng)前位置開始的整個(gè)匹配也就宣告失敗。

    目前對(duì)正則表達(dá)式的回溯只能理解這么多,以后我再慢慢補(bǔ)充吧!

您可能感興趣的文章:
  • PHP 正則表達(dá)式效率 貪婪、非貪婪與回溯分析(推薦)
  • 正則中的回溯定義與用法分析【JS與java實(shí)現(xiàn)】
  • 編寫高質(zhì)量的js之正確理解正則表達(dá)式回溯
  • 深度分析正則(pcre)最大回溯/遞歸限制
  • 小議正則表達(dá)式效率 貪婪、非貪婪與回溯
  • PHP正則表達(dá)式的效率 回溯與固化分組
  • AS3 js正則表達(dá)式 反向引用(backreference)
  • 詳解JavaScript正則表達(dá)式之分組匹配及反向引用
  • php正則表達(dá)式的模式修正符和逆向引用使用介紹
  • PHP正則表達(dá)式的逆向引用與子模式分析
  • JavaScript正則表達(dá)式之后向引用實(shí)例代碼
  • VBS教程:正則表達(dá)式簡(jiǎn)介 -后向引用
  • 正則表達(dá)式學(xué)習(xí)教程之回溯引用backreference詳解

標(biāo)簽:無(wú)錫 長(zhǎng)沙 綿陽(yáng) 西安 銅川 宣城 泰州 重慶

巨人網(wǎng)絡(luò)通訊聲明:本文標(biāo)題《正則表達(dá)式之回溯》,本文關(guān)鍵詞  正則,表達(dá)式,之,回溯,正則,;如發(fā)現(xiàn)本文內(nèi)容存在版權(quán)問(wèn)題,煩請(qǐng)?zhí)峁┫嚓P(guān)信息告之我們,我們將及時(shí)溝通與處理。本站內(nèi)容系統(tǒng)采集于網(wǎng)絡(luò),涉及言論、版權(quán)與本站無(wú)關(guān)。
  • 相關(guān)文章
  • 下面列出與本文章《正則表達(dá)式之回溯》相關(guān)的同類信息!
  • 本頁(yè)收集關(guān)于正則表達(dá)式之回溯的相關(guān)信息資訊供網(wǎng)民參考!
  • 推薦文章