首頁 > 文章 > web前端 > js裡如何正確理解正規表示式的回溯

js裡如何正確理解正規表示式的回溯

php中世界最好的语言原創: 2018-03-30 13:56:481463瀏覽

這次帶給大家js裡如何正確理解正規表示式的回溯，js裡正確使用正規表示式回溯的注意事項有哪些，以下就是實戰案例，一起來看一下。

在正規表示式實作中，回溯是匹配過程的基本組成部分，它是正規表示式如此好用且強大的根源。然而，回溯計算代價很高，如果設計失誤，將導致失控。回溯是影響整體效能的唯一因素，理解它的工作原理，以及如何減少使用頻率，可能是編寫高效正則表達式的關鍵點

當一個正則表達式掃描目標字串時，從左到右逐一掃描正規表示式的組成部分，在每個位置上測試能不能找到一個匹配。對於每一個量詞和分支，都必須決定如何繼續進行。如果是量詞（如*、+?或{2,}），那麼正規表示式必須確定何時嘗試匹配更多的字元；如果遇到分支（透過|運算子），那麼正規表示式必須從這些選項中選擇一個進行嘗試。

當正規表示式做出這樣的決定時，如果有必要，它會記住另一個選項，以便在返回後使用。如果所選方案匹配成功，正規表示式將繼續掃描正規表示式模板，如果其餘部分匹配也成功了，那麼匹配就結束了。但是，如果所選的方案未能發現相應匹配，或者後來的匹配也失敗了，正則表達式將回溯到最後一個決策點，然後在剩餘的選項中選擇一個。繼續這樣，直到找到一個匹配，或者量詞和分支選項的所有可能的排列組合都嘗試失敗後放棄這一過程，然後移動到此過程開始位置的下一個字符上，重複此過程。

例如，下面的程式碼示範了這個過程是如何透過回溯處理分支的。

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

上面一行正規表示式用來符合「hello hippo」或「happy hippo」。測試一開始要找一個h，目標字串的第一個字母剛好就是h，立刻就找到了。接下來，子表達式（ello|appy）提供了兩個處理選項。正規表示式選擇最左邊的選項（分支選擇總是從左到右進行），檢查ello 是否匹配字串的下一個字符，確實匹配，然後正則表達式又匹配了後面的空格。

然而，在接下來的匹配中正則表達式“走進了死胡同”，因為hippo 中的h 不能匹配字串中的下一個字母t。此時正則表達式還不能放棄，因為它還沒有嘗試過所有的選擇，隨後它回溯到最後一個檢查點（在匹配了首字母h 之後的那個位置上）並嘗試匹配第二個分支選項。但由於匹配沒有成功，而且也沒有更多的選項了，正則表達式認為從字串的第一個字元開始匹配是不能成功的，因此它從第二個字元開始重新進行查找。正規表示式沒有找到h，繼續向後找，直到第14 個字母才找到，它符合happy 的那個h。隨後正規表示式再次進入分支過程，這次ello 未能匹配，但在回溯之後的第二次分支中，它匹配了整個字串“happy hippo”，匹配成功了。

再如，下面程式碼示範了重複量詞的回溯。

var str = "<p>Para 1.</p>" +"<img src=&#39;smiley.jpg&#39;>" +"<p>Para 2.</p>" +"<p>p.</p>";
/<p>.*<\/p>/i.test(str);

正規表示式先符合了字串開始的3個字母

，然後是.*。點號表示匹配換行符以外的任意字符，星號這個「貪婪」量詞表示重複零次或多次，匹配盡量多的次數。因為目標字串中沒有換行符，正規表示式將匹配剩餘的全部字串！不過由於正規表示式範本還有更多內容需要匹配，所以正規表示式嘗試匹配<。由於在字串末尾匹配不成功，因此每次回溯一個字符，繼續嘗試匹配<，直到正則表達式回到

標籤的<位置。接下來嘗試配對\/（轉義反斜線），配對成功，然後配對p，配對不成功。正規表示式繼續回溯，重複此過程，直到第二段末尾時終於匹配了

。匹配返回成功需要從第一段頭部一直掃描到最後一個的末尾，這可能不是我們想要的結果。

將正規表示式中的「貪婪」量詞*改為「懶惰」（又稱「非貪婪」）量詞*?，以符合單一段落。「懶惰」量詞的回溯工作以相反方式進行。當正規表示式/

.*?<\/p>/推進到.*?時，首先嘗試全部跳過，然後繼續匹配<\/p>。

这样做是因为*?匹配零次或多次，尽可能少重复，尽可能少意味着可以重复零次。但是，当随后的<在字符串的这一点上匹配失败时，正则表达式回溯并尝试下一个最小的字符数：1个。正则表达式继续像这样向前回溯到第一段的末尾，在那里量词后面的<\/p>得到完全匹配。

如果目标字符串只有一个段落，那么此正则表达式的“贪婪”版本和“懒惰”版本是等价的，但尝试匹配的过程不同。

当一个正则表达式占用浏览器几秒甚至更长时间时，问题原因很可能是回溯失控。为说明此问题，给出下面的正则表达式，它的目标是匹配整个HTML文件。此表达式被拆分成多行是为了适合页面显示。与其他正则表达式不同，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 字符串时工作良好，但当目标字符串缺少一个或多个标签时，就会变得十分糟糕。例如标签缺失，最后一个[\s\S]*?将扩展到字符串的末尾，因为在那里没有发现标签，然后正则表达式将查看此前的[\s\S]*?队列记录的回溯位置，使它们进一步扩大。正则表达式尝试扩展倒数第二个[\s\S]*?—用它匹配标签，就是此前匹配过正则表达式模板<\/body>的那个标签，然后继续查找第二个标签，直到字符串的末尾。当所有这些步骤都失败时，倒数第三个[\s\S]*?将被扩展，直至字符串的末尾，依此类推。

此类问题的解决办法在于尽可能具体地指出分隔符之间的字符匹配形式，如模板“.*?”用于匹配双引号包围的一个字符串。用更具体的[^"\rn]*取代过于宽泛的.*?就去除了回溯时可能发生的几种情况，如尝试用点号匹配引号，或者扩展搜索超出预期范围。

在HTML 的例子中解决办法不是那么简单。不能使用否定字符类型，如用[^<]替代[\s\S]，因为在搜索过程中可能会遇到其他类型的标签。但是，可以通过重复一个非捕获组来达到同样效果，它包含一个回溯（阻塞下一个所需的标签）和[\s\S]（任意字符）元序列。这样可以确保中间位置上查找的每个标签都会失败。然后，更重要的是，[\s\S]模板在回溯过程中阻塞的标签在被发现之前不能被扩展。应用此方法后对正则表达式的最终修改如下：

/<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>/

虽然这样做消除了潜在的回溯失控，并允许正则表达式在匹配不完整HTML字符串失败时的使用时间与文本长度呈线性关系，但是正则表达式的效率并没有提高。像这样为每个匹配字符进行多次前瞻，缺乏效率，而且成功匹配过程也相当慢。匹配较短字符串时使用此方法相当不错，而匹配一个HTML 文件可能需要前瞻并测试上千次。

相信看了本文案例你已经掌握了方法，更多精彩请关注php中文网其它相关文章！

js裡如何正確理解正規表示式的回溯

相關文章