|
在大多數(shù)現(xiàn)代正則表達(dá)式實(shí)現(xiàn)中（包括JavaScript所需的）,，回溯是匹配過(guò)程的基本組成部分,。它很大程度上也是正則表達(dá)式如此美好和強(qiáng)大的根源,。然而,，回溯計(jì)算代價(jià)昂貴,，如果你不夠小心的話容易失控。雖然回溯是整體性能的唯一因素,，理解它的工作原理，以及如何減少使用頻率,，可能是編寫高效正則表達(dá)式最重要的關(guān)鍵點(diǎn),。因此后面幾節(jié)用較長(zhǎng)篇幅討論這個(gè)話題。
當(dāng)一個(gè)正則表達(dá)式掃描目標(biāo)字符串時(shí),，它從左到右逐個(gè)掃描正則表達(dá)式的組成部分，在每個(gè)位置上測(cè)試能不能找到一個(gè)匹配,。對(duì)于每一個(gè)量詞和分支，都必須決定如何繼續(xù)進(jìn)行,。如果是一個(gè)量詞（諸如*，+?,，或者{2,}），正則表達(dá)式必須決定何時(shí)嘗試匹配更多的字符,；如果遇到分支（通過(guò)|操作符），它必須從這些選項(xiàng)中選擇一個(gè)進(jìn)行嘗試。
每當(dāng)正則表達(dá)式做出這樣的決定,，如果有必要的話，它會(huì)記住另一個(gè)選項(xiàng),，以備將來(lái)返回后使用。如果所選方案匹配成功,，正則表達(dá)式將繼續(xù)掃描正則表達(dá)式模板,，如果其余部分匹配也成功了,，那么匹配就結(jié)束了。但是如果所選擇的方案未能發(fā)現(xiàn)相應(yīng)匹配,，或者后來(lái)的匹配也失敗了,，正則表達(dá)式將回溯到最后一個(gè)決策點(diǎn)，然后在剩余的選項(xiàng)中選擇一個(gè),。它繼續(xù)這樣下去，直到找到一個(gè)匹配,，或者量詞和分支選項(xiàng)的所有可能的排列組合都嘗試失敗了，那么它將放棄這一過(guò)程,，然后移動(dòng)到此過(guò)程開始位置的下一個(gè)字符上，重復(fù)此過(guò)程,。
一,、分支和回溯
下面的例子演示了這一過(guò)程是如何處理分支的,。
/h(ello|appy) hippo/.test("hellothere, happyhippo");
此正則表達(dá)式匹配“hellohippo”或“happyhippo”,。測(cè)試一開始,，它要查找一個(gè)h，目標(biāo)字符串的第一個(gè)字母恰好就是h,，它立刻就被找到了,。接下來(lái)，子表達(dá)式（ello|appy）提供了兩個(gè)處理選項(xiàng),。正則表達(dá)式選擇最左邊的選項(xiàng)（分支選擇總是從左到右進(jìn)行）,，檢查ello是否匹配字符串的下一個(gè)字符。確實(shí)匹配，然后正則表達(dá)式又匹配了后面的空格,。然而在這一點(diǎn)上它走進(jìn)了死胡同,，因?yàn)閔ippo 中的h 不能匹配字符串中的下一個(gè)字母t,。此時(shí)正則表達(dá)式還不能放棄，因?yàn)樗€沒(méi)有嘗試過(guò)所有的選擇,，隨后它回溯到最后一個(gè)檢查點(diǎn)（在它匹配了首字母h 之后的那個(gè)位置上）并嘗試匹配第二個(gè)分支選項(xiàng),。但是沒(méi)有成功,，而且也沒(méi)有更多的選項(xiàng)了,，所以正則表達(dá)式認(rèn)為從字符串的第一個(gè)字符開始匹配是不能成功的,，因此它從第二個(gè)字符開始，重新進(jìn)行查找,。它沒(méi)有找到h，所以就繼續(xù)向后找,，直到第14 個(gè)字母才找到，它匹配happy的那個(gè)h,。然后它再次進(jìn)入分支過(guò)程,。這次ello未能匹配，但是回溯之后第二次分支過(guò)程中,，它匹配了整個(gè)字符串“happyhippo”,。匹配成功了。
二,、重復(fù)與回溯
下一個(gè)例子顯示了帶重復(fù)量詞的回溯,。
var str = "<p>Para 1.</p>" +
"<img src='smiley.jpg'>" +
"<p>Para 2.</p>" +
"<div>Div.</div>";
/<p>.*<\/p>/i.test(str);
正則表達(dá)式一上來(lái)就匹配了字符串開始的三個(gè)字母<p>,。然后是.*,。點(diǎn)號(hào)匹配除換行符以外的任意字符,，星號(hào)這個(gè)貪婪量詞表示重復(fù)零次或多次——匹配盡量多的次數(shù),。因?yàn)槟繕?biāo)字符串中沒(méi)有換行符,，它將吞噬剩下的全部字符串！不過(guò)正則表達(dá)式模板中還有更多內(nèi)容需要匹配,，所以正則表達(dá)式嘗試匹配<。它在字符串末尾匹配不成功,，所以它每次回溯一個(gè)字符,，繼續(xù)嘗試匹配<,，直到它回到</div>標(biāo)簽的<位置。然后它嘗試匹配\/（轉(zhuǎn)義反斜杠），匹配成功,，然后是p，匹配不成功,。正則表達(dá)式繼續(xù)回溯,，重復(fù)此過(guò)程,，直到第二段末尾時(shí)它終于匹配了</p>。匹配返回成功,，它從第一段頭部一直掃描到最后一個(gè)的末尾,，這可能不是你想要的結(jié)果。
你可以將正則表達(dá)式中的貪婪量詞*改為懶惰（又名非貪婪）量詞*?,，以匹配單個(gè)段落,。懶惰量詞的回溯工作以相反方式進(jìn)行。當(dāng)正則表達(dá)式/<p>.*?<\/p>/推進(jìn)到.*?時(shí),，它首先嘗試全部跳過(guò)然后繼續(xù)匹配<\/p>,。它這么做是因?yàn)??匹配零次或多次，但盡可能少重復(fù),，盡可能少的話那么它就可以重復(fù)零次。但是,，當(dāng)隨后的<在字符串的這一點(diǎn)上匹配失敗時(shí)，正則表達(dá)式回溯并嘗試下一個(gè)最小的字符數(shù)：一個(gè),。它繼續(xù)像這樣向前回溯到第一段的末尾,，在那里量詞后面的<\/p>得到完全匹配,。
如果目標(biāo)字符串只有一個(gè)段落，你可以看到此正則表達(dá)式的貪婪版本和懶惰版本是等價(jià)的,，但是他們嘗試匹配的過(guò)程不同,。
三,、回溯失控
當(dāng)一個(gè)正則表達(dá)式占用瀏覽器上秒，上分鐘或者更長(zhǎng)時(shí)間時(shí),，問(wèn)題原因很可能是回溯失控,。為說(shuō)明此問(wèn)題，考慮下面的正則表達(dá)式,，它的目標(biāo)是匹配整個(gè)HTML文件,。此表達(dá)式被拆分成多行是為了適合頁(yè)面顯示,。不像其他大多數(shù)正則表達(dá)式那樣,，JavaScript沒(méi)有選項(xiàng)可使點(diǎn)號(hào)匹配任意字符,，包括換行符，所以此例中以[\s\S]匹配任意字符,。
/<html>[\s\S]*?<head>[\s\S]*?<title>[\s\S]*?<\/title>[\s\S]*?<\/head>
[\s\S]*?<body>[\s\S]*?<\/body>[\s\S]*?<\/html>/
此正則表達(dá)式匹配正常HTML字符串時(shí)工作良好，但是如果目標(biāo)字符串缺少一個(gè)或多個(gè)標(biāo)簽時(shí),，它就會(huì)變得十分糟糕,。例如</html>標(biāo)簽缺失，那么最后一個(gè)[\s\S]*?將擴(kuò)展到字符串的末尾,，因?yàn)樵谀抢餂](méi)有發(fā)現(xiàn)</html>標(biāo)簽,，然后并沒(méi)有放棄，正則表達(dá)式將察看此前的[\s\S]*?隊(duì)列記錄的回溯位置,，使它們進(jìn)一步擴(kuò)大。正則表達(dá)式嘗試擴(kuò)展倒數(shù)第二個(gè)[\s\S]*?——用它匹配</body>標(biāo)簽,，就是此前匹配過(guò)正則表達(dá)式模板<\/body>的那個(gè)標(biāo)簽——然后繼續(xù)查找第二個(gè)</body>標(biāo)簽直到字符串的末尾,。當(dāng)所有這些步驟都失敗了,，倒數(shù)第三個(gè)[\s\S]*?將被擴(kuò)展直至字符串的末尾，依此類推,。
如果您看完本篇文章感覺不錯(cuò)，請(qǐng)點(diǎn)擊一下右下角的 【推薦】來(lái)支持一下博主,，謝謝！ |
