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