編寫高質(zhì)量的js之正確理解正則表達(dá)式回溯

當(dāng)一個(gè)正則表達(dá)式掃描目標(biāo)字符串時(shí)，從左到右逐個(gè)掃描正則表達(dá)式的組成部分，在每個(gè)位置上測試能不能找到一個(gè)匹配。對于每一個(gè)量詞和分支，都必須確定如何繼續(xù)進(jìn)行。如果是一個(gè)量詞（如*、+?或者{2,}），那么正則表達(dá)式必須確定何時(shí)嘗試匹配更多的字符；如果遇到分支（通過|操作符），那么正則表達(dá)式必須從這些選項(xiàng)中選擇一個(gè)進(jìn)行嘗試。

當(dāng)正則表達(dá)式做出這樣的決定時(shí)，如果有必要，它會(huì)記住另一個(gè)選項(xiàng)，以備返回后使用。如果所選方案匹配成功，正則表達(dá)式將繼續(xù)掃描正則表達(dá)式模板，如果其余部分匹配也成功了，那么匹配就結(jié)束了。但是，如果所選擇的方案未能發(fā)現(xiàn)相應(yīng)匹配，或者后來的匹配也失敗了，正則表達(dá)式將回溯到最后一個(gè)決策點(diǎn)，然后在剩余的選項(xiàng)中選擇一個(gè)。繼續(xù)這樣，直到找到一個(gè)匹配，或者量詞和分支選項(xiàng)的所有可能的排列組合都嘗試失敗后放棄這一過程，然后移動(dòng)到此過程開始位置的下一個(gè)字符上，重復(fù)此過程。

例如，下面的代碼演示了這一過程是如何通過回溯處理分支的。

/h(ello|appy) hippo/.test("hello there, happy hippo");

上面一行正則表達(dá)式用于匹配“hello hippo”或“happy hippo”。測試一開始要查找一個(gè)h，目標(biāo)字符串的第一個(gè)字母恰好就是h，立刻就找到了。接下來，子表達(dá)式（ello|appy）提供了兩個(gè)處理選項(xiàng)。正則表達(dá)式選擇最左邊的選項(xiàng)（分支選擇總是從左到右進(jìn)行），檢查ello 是否匹配字符串的下一個(gè)字符，確實(shí)匹配，然后正則表達(dá)式又匹配了后面的空格。

然而，在接下來的匹配中正則表達(dá)式“走進(jìn)了死胡同”，因?yàn)閔ippo 中的h 不能匹配字符串中的下一個(gè)字母t。此時(shí)正則表達(dá)式還不能放棄，因?yàn)樗€沒有嘗試過所有的選擇，隨后它回溯到最后一個(gè)檢查點(diǎn)（在匹配了首字母h 之后的那個(gè)位置上）并嘗試匹配第二個(gè)分支選項(xiàng)。但由于匹配沒有成功，而且也沒有更多的選項(xiàng)了，正則表達(dá)式認(rèn)為從字符串的第一個(gè)字符開始匹配是不能成功的，因此它從第二個(gè)字符開始重新進(jìn)行查找。正則表達(dá)式?jīng)]有找到h，繼續(xù)向后找，直到第14 個(gè)字母才找到，它匹配happy 的那個(gè)h。隨后正則表達(dá)式再次進(jìn)入分支過程，這次ello 未能匹配，但在回溯之后的第二次分支中，它匹配了整個(gè)字符串“happy hippo”，匹配成功了。

再如，下面代碼演示了帶重復(fù)量詞的回溯。

var str = "p>Para 1./p>" +"img src='smiley.jpg'>" +"p>Para 2./p>" +"div>Div./div>";
/p>.*\/p>/i.test(str);

正則表達(dá)式先匹配了字符串開始的3個(gè)字母p>，然后是.*。點(diǎn)號表示匹配除換行符以外的任意字符，星號這個(gè)“貪婪”量詞表示重復(fù)零次或多次，匹配盡量多的次數(shù)。因?yàn)槟繕?biāo)字符串中沒有換行符，正則表達(dá)式將匹配剩下的全部字符串！不過由于正則表達(dá)式模板中還有更多內(nèi)容需要匹配，所以正則表達(dá)式嘗試匹配。由于在字符串末尾匹配不成功，因此每次回溯一個(gè)字符，繼續(xù)嘗試匹配，直到正則表達(dá)式回到/div>標(biāo)簽的位置。接下來嘗試匹配\/（轉(zhuǎn)義反斜杠），匹配成功，然后匹配p，匹配不成功。正則表達(dá)式繼續(xù)回溯，重復(fù)此過程，直到第二段末尾時(shí)終于匹配了/p>。匹配返回成功需要從第一段頭部一直掃描到最后一個(gè)的末尾，這可能不是我們想要的結(jié)果。

將正則表達(dá)式中的“貪婪”量詞*改為“懶惰”（又名“非貪婪”）量詞*?，以匹配單個(gè)段落。“懶惰”量詞的回溯工作以相反方式進(jìn)行。當(dāng)正則表達(dá)式/p>.*?\/p>/推進(jìn)到.*?時(shí)，首先嘗試全部跳過，然后繼續(xù)匹配\/p>。

這樣做是因?yàn)??匹配零次或多次，盡可能少重復(fù)，盡可能少意味著可以重復(fù)零次。但是，當(dāng)隨后的在字符串的這一點(diǎn)上匹配失敗時(shí)，正則表達(dá)式回溯并嘗試下一個(gè)最小的字符數(shù)：1個(gè)。正則表達(dá)式繼續(xù)像這樣向前回溯到第一段的末尾，在那里量詞后面的\/p>得到完全匹配。

如果目標(biāo)字符串只有一個(gè)段落，那么此正則表達(dá)式的“貪婪”版本和“懶惰”版本是等價(jià)的，但嘗試匹配的過程不同。

當(dāng)一個(gè)正則表達(dá)式占用瀏覽器幾秒甚至更長時(shí)間時(shí)，問題原因很可能是回溯失控。為說明此問題，給出下面的正則表達(dá)式，它的目標(biāo)是匹配整個(gè)HTML文件。此表達(dá)式被拆分成多行是為了適合頁面顯示。與其他正則表達(dá)式不同，JavaScript在沒有選項(xiàng)時(shí)可使點(diǎn)號匹配任意字符，包括換行符，所以此例中以[\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í)工作良好，但當(dāng)目標(biāo)字符串缺少一個(gè)或多個(gè)標(biāo)簽時(shí)，就會(huì)變得十分糟糕。例如/html>標(biāo)簽缺失，最后一個(gè)[\s\S]*?將擴(kuò)展到字符串的末尾，因?yàn)樵谀抢餂]有發(fā)現(xiàn)/html>標(biāo)簽，然后正則表達(dá)式將查看此前的[\s\S]*?隊(duì)列記錄的回溯位置，使它們進(jìn)一步擴(kuò)大。正則表達(dá)式嘗試擴(kuò)展倒數(shù)第二個(gè)[\s\S]*?—用它匹配/body>標(biāo)簽，就是此前匹配過正則表達(dá)式模板\/body>的那個(gè)標(biāo)簽，然后繼續(xù)查找第二個(gè)/body>標(biāo)簽，直到字符串的末尾。當(dāng)所有這些步驟都失敗時(shí)，倒數(shù)第三個(gè)[\s\S]*?將被擴(kuò)展，直至字符串的末尾，依此類推。

此類問題的解決辦法在于盡可能具體地指出分隔符之間的字符匹配形式，如模板“.*?”用于匹配雙引號包圍的一個(gè)字符串。用更具體的[^"\rn]*取代過于寬泛的.*?就去除了回溯時(shí)可能發(fā)生的幾種情況，如嘗試用點(diǎn)號匹配引號，或者擴(kuò)展搜索超出預(yù)期范圍。

在HTML 的例子中解決辦法不是那么簡單。不能使用否定字符類型，如用[^]替代[\s\S]，因?yàn)樵谒阉鬟^程中可能會(huì)遇到其他類型的標(biāo)簽。但是，可以通過重復(fù)一個(gè)非捕獲組來達(dá)到同樣效果，它包含一個(gè)回溯（阻塞下一個(gè)所需的標(biāo)簽）和[\s\S]（任意字符）元序列。這樣可以確保中間位置上查找的每個(gè)標(biāo)簽都會(huì)失敗。然后，更重要的是，[\s\S]模板在回溯過程中阻塞的標(biāo)簽在被發(fā)現(xiàn)之前不能被擴(kuò)展。應(yīng)用此方法后對正則表達(dá)式的最終修改如下：

/html>(?:(?!head>)[\s\S])*head>(?:(?!title>)[\s\S])*title>

(?:(?!\/title>)[\s\S])*\/title>(?:(?!\/head>)[\s\S])*\/head>

(?:(?!body>)[\s\S])*body>(?:(?!\/body>)[\s\S])*\/body>
(?:(?!\/html>)[\s\S])*\/html>/

雖然這樣做消除了潛在的回溯失控，并允許正則表達(dá)式在匹配不完整HTML字符串失敗時(shí)的使用時(shí)間與文本長度呈線性關(guān)系，但是正則表達(dá)式的效率并沒有提高。像這樣為每個(gè)匹配字符進(jìn)行多次前瞻，缺乏效率，而且成功匹配過程也相當(dāng)慢。匹配較短字符串時(shí)使用此方法相當(dāng)不錯(cuò)，而匹配一個(gè)HTML 文件可能需要前瞻并測試上千次。