Javascript 貪婪量詞和惰性量詞

量詞乍一看非常簡單，但實際上它們可能很棘手。

如果我們打算尋找比 /\d+/ 更復雜的東西，就需要理解搜索的工作原理。

以接下來的任務為例。

有一個文本，我們需要用書名號：?...? 來代替所有的引號 "..."。在許多國家，書名號是排版的首選。

例如："Hello, world" 應該變成 ?Hello, world?。還有其他引用，例如 ?Witam, ?wiat!”（波蘭語）或 「你好，世界」（中文），但對于我們的任務，讓我們選擇 ?...? 吧。

首先要做的是定位帶引號的字符串，然后替換它們。

像 /".+"/g（一個引號，然后是一些內容，然后是另一個引號）這樣的正則表達式看起來可能很合適，但事實并非如此！

讓我們試一下：

let regexp = /".+"/g;

let str = 'a "witch" and her "broom" is one';

alert( str.match(regexp) ); // "witch" and her "broom"

……可以看出來它的運行結果與預期不同！

它沒有找到匹配項 "witch" 和 "broom"，而是找到："witch" and her "broom"。

這可被稱為“貪婪是萬惡之源”。

貪婪搜索

為了查找到一個匹配項，正則表達式引擎采用了以下算法：

• 對于字符串中的每一個位置
  • 嘗試匹配該位置的模式。
  • 如果未匹配，則轉到下一個位置。

這樣簡單的描述并不能說清楚這個正則表達式匹配失敗的原因，所以讓我們詳細說明一下模式 ".+" 是如何進行搜索的。

1. 該模式的第一個字符是一個引號 ?"?。

正則表達式引擎嘗試在源字符串 a "witch" and her "broom" is one 的位置 0 找到它，但那里有 a，所以匹配失敗。


然后繼續(xù)前進：移至源字符串中的下一個位置，并嘗試匹配模式中的第一個字符，再次失敗，最終在第三個位置匹配到了引號：





2. 找到引號后，引擎就嘗試去匹配模式中的剩余字符。它嘗試查看剩余的字符串是否符合 .+"。

在我們的用例中，模式中的下一個字符為 .（一個點）。它表示匹配除了換行符之外的任意字符，所以將會匹配下一個字符 'w'：





3. 然后由于量詞 .+，點會重復。正則表達式引擎一個接一個字符地進行匹配。

……什么時候會不匹配？點（.）能夠匹配所有字符，所以只有在移至字符串末尾時才停止匹配：





4. 現(xiàn)在引擎完成了對重復模式 .+ 的搜索，并且試圖尋找模式中的下一個字符。是引號 "。但是有一個問題：對字符串的遍歷已經(jīng)結束，沒有更多字符了！

正則表達式引擎知道它為 .+ 匹配太多項了，所以開始 回溯。


換句話說，它去掉了量詞匹配項的最后一個字符：





現(xiàn)在它假設 .+ 的匹配在字符串的倒數(shù)第一個字符前的位置結束，并嘗試從該位置匹配模式的剩余部分。


如果那里有引號，則搜索將結束，但最后一個字符是 'e'，所以不匹配。


5. ……所以引擎會將 .+ 的重復次數(shù)減少一個字符：




引號 '"' 與 'n' 不匹配。


6. 引擎不斷進行回溯：它減少 '.' 的重復次數(shù)，直到模式的其余部分（在我們的用例中是 '"'）匹配到結果：




7. 匹配完成。
8. 所以，第一次匹配項是 ?"witch" and her "broom"?。如果正則表達式具有修飾符 ?g?，則搜索將從第一個匹配結束的地方繼續(xù)。字符串 ?is one? 的剩余部分不再有引號，因此沒有更多匹配項。

這可能不是我們所期望的，但這就是它的工作方式。

在貪婪模式下（默認情況），量詞都會盡可能多地重復。

正則表達式引擎嘗試用 .+ 去匹配盡可能多的字符，然后在模式的其余部分不匹配時再將其逐一縮短。

對于這個任務，我們想要得是另一種結果。這也就是惰性量詞模式的用途。

惰性模式

惰性模式中的量詞與貪婪模式中的是相反的。它表示：“重復最少的次數(shù)”。

我們可以通過在量詞后面添加一個問號 '?' 來啟用它，這樣匹配模式就變成了 *? 或 +?，甚至將 '?' 變成 ??。

這么說吧：通常問號 ? 本身就是一個量詞（0 或 1），但如果將其放到 另一個量詞（甚至是它自己）后面，就會有不同的含義 —— 它將匹配的模式從貪婪轉為惰性。

正則表達式 /".+?"/g 能夠按預期工作了：它找到了 "witch" 和 "broom"：

let regexp = /".+?"/g;

let str = 'a "witch" and her "broom" is one';

alert( str.match(regexp) ); // "witch", "broom"

為了更清楚地理解這個變化，我們來一步步解析這個搜索過程。

1. 第一步是一樣的：它在第三個字符的位置找到了模式的開頭 '"'：




2. 下一步也是類似的：引擎為 '.' 找到了一個匹配項：




3. 接下來的搜索就有些不同了。因為我們對 +? 啟用了惰性模式，引擎不會去嘗試多匹配一個點的匹配字符，而會停止并立即嘗試對剩余的模式 '"' 進行匹配：




如果這里有一個引號，搜索就會停止，但這里是一個 'i'，所以沒有匹配到引號。


4. 接著，正則表達式引擎增加對點的重復搜索次數(shù)，并且再次嘗試：




又失敗了。然后重復次數(shù)一次又一次的增加……


5. ……直到找到了模式中的剩余部分的匹配項：




6. 接下來的搜索從當前匹配的結尾開始，并產(chǎn)生了下一個匹配項：

在這個例子中，我們看到了惰性模式的 +? 是怎樣工作的。量詞 *? 和 ?? 的工作方式類似 —— 正則表達式引擎僅在模式的其余部分無法在給定位置匹配時增加重復次數(shù)。

惰性模式僅對帶有 ? 的量詞啟用

其它量詞依舊保持貪婪模式。

例如：

alert( "123 456".match(/\d+ \d+?/) ); // 123 4

1. 模式 \d+ 嘗試匹配盡可能多的數(shù)字（貪婪模式），因此在它找到 123 時停止，因為下一個字符為空格 ' '。

2. 然后模式中有一個空格，正好匹配。

3. 然后是 \d+?。此量詞處于惰性模式，所以它匹配一個數(shù)字 4 后開始嘗試去檢查模式的剩余部分是否匹配。

   ……但是在 \d+? 之后沒有其它內容了。

   惰性模式在不必要的情況下不會重復任何東西。模式結束，我們找到了匹配項 123 4。

優(yōu)化

現(xiàn)在正則表達式引擎會通過優(yōu)化內部算法來提升效率。所以它們的工作方式和所描述的算法可能略有不同。

但如果只是為了了解正則表達式的工作原理和如何構建正則表達式我們不需要知道這些。它們僅用于內部算法優(yōu)化。

復雜的正則表達式是很難優(yōu)化的，因此搜索的過程也可以完全按照描述的方式進行。

替代方法

使用正則表達式，通常有不止一種方式可以做相同的事。

在我們的例子中，我們可以在不啟用惰性模式的情況下使用正則表達式 "[^"]+" 找到帶引號的字符串：

let regexp = /"[^"]+"/g;

let str = 'a "witch" and her "broom" is one';

alert( str.match(regexp) ); // "witch", "broom"

正則表達式 "[^"]+" 給出了正確答案，因為它查找一個引號 '"' 后跟一個或更多非引號 [^"] 的字符，然后是結束的引號。

當引擎尋找 [^"]+ 時，它會在匹配到結束的引號時停止重復，這樣就完成了。

請注意，這個邏輯并不能取代惰性量詞！

它們是不同的。我們在不同情況下可能會需要使用到其中的一個或另一個。

讓我們再來看一個使用惰性量詞失敗而使用這種變體能獲得預期結果的例子。

例如，我們想要找到 <a href="..." class="doc"> 形式的帶有任意 href 的鏈接。

該使用哪個正則表達式呢？

首先可能會想到：/<a href=".*" class="doc">/g。

驗證一下：

let str = '...<a href="link" class="doc">...';
let regexp = /<a href=".*" class="doc">/g;

// 有效！
alert( str.match(regexp) ); // <a href="link" class="doc">

……但如果文本中有多個鏈接呢？

let str = '...<a href="link1" class="doc">... <a href="link2" class="doc">...';
let regexp = /<a href=".*" class="doc">/g;

// 蛤！一個匹配項中有兩個鏈接！
alert( str.match(regexp) ); // <a href="link1" class="doc">... <a href="link2" class="doc">

現(xiàn)在這個結果是錯的，原因與我們的 “witches” 示例相同。量詞 .* 占用了太多字符。

匹配結果如下：

<a href="....................................." class="doc">
<a href="link1" class="doc">... <a href="link2" class="doc">

讓我們啟用惰性量詞 .*? 來修改模式：

let str = '...<a href="link1" class="doc">... <a href="link2" class="doc">...';
let regexp = /<a href=".*?" class="doc">/g;

// 正確了！
alert( str.match(regexp) ); // <a href="link1" class="doc">, <a href="link2" class="doc">

現(xiàn)在能成功了，有兩個匹配項：

<a href="....." class="doc">    <a href="....." class="doc">
<a href="link1" class="doc">... <a href="link2" class="doc">

……但是讓我們用另外一個文本來測試看看：

let str = '...<a href="link1" class="wrong">... <p style="" class="doc">...';
let regexp = /<a href=".*?" class="doc">/g;

// 錯誤的匹配！
alert( str.match(regexp) ); // <a href="link1" class="wrong">... <p style="" class="doc">

現(xiàn)在它匹配錯了。匹配項不僅包括了一個鏈接，還包括了它后面的很多文本，包括 <p...>。

為什么？

原因如下：

1. 首先，正則表達式尋找鏈接的開始：<a href="。
2. 然后它尋找 .*?，取一個字符（惰性的?。缓髾z查字符串的剩余部分是否與模式的剩余部分匹配（未匹配）。
3. 然后再取一個字符到 .*? 中，以此類推……直到最終到達 " class="doc">。

但問題是：這已經(jīng)超出了鏈接 <a...>，已經(jīng)在另一個標簽 <p> 中了。這不是我們想要的。

這是與匹配項在文本上對齊的示例：

<a href="..................................." class="doc">
<a href="link1" class="wrong">... <p style="" class="doc">

所以，我們需要模式尋找 <a href="...something..." class="doc">，但貪婪模式和惰性模式都有問題。

正確的變體可以是這樣的：href="[^"]*"。它會獲取 href 特性中的所有字符直到最近的引號，正好符合我們的需求。

舉個例子：

let str1 = '...<a href="link1" class="wrong">... <p style="" class="doc">...';
let str2 = '...<a href="link1" class="doc">... <a href="link2" class="doc">...';
let regexp = /<a href="[^"]*" class="doc">/g;

// 有效！
alert( str1.match(regexp) ); // null，無匹配項，這是對的
alert( str2.match(regexp) ); // <a href="link1" class="doc">, <a href="link2" class="doc">

總結

量詞有兩種工作模式：

貪婪模式

默認情況下，正則表達式引擎會嘗試盡可能多地重復量詞字符。例如，\d+ 會消耗所有可能的字符。當無法消耗更多（在尾端沒有更多的數(shù)字或字符串）時，然后它再匹配模式的剩余部分。如果沒有匹配，則減少重復的次數(shù)（回溯），并再次嘗試。

惰性模式

通過在量詞后添加問號 ? 來啟用。正則表達式引擎嘗試在每次重復量化字符之前匹配模式的其余部分。

正如我們所見，惰性模式并不是貪婪搜索的“靈丹妙藥”。另一種方式是使用排除項“微調”貪婪搜索，如模式 "[^"]+"。

任務

/d+? d+?/ 的匹配項

匹配的結果是什么？

alert( "123 456".match(/\d+? \d+?/g) ); // ?

解決方案

結果是：123 4。

首先，惰性模式 \d+? 嘗試去獲取盡可能少的數(shù)字，但它必須到達空格，因此需要匹配到 123。

然后，第二個 \d+? 就只獲取一個數(shù)字，因為這就已經(jīng)足夠了。

查找 HTML 注釋

找出文本中的所有 HTML 注釋：

let regexp = /你的正則表達式/g;

let str = `... <!-- My -- comment
 test --> ..  <!----> ..
`;

alert( str.match(regexp) ); // '<!-- My -- comment \n test -->', '<!---->'

解決方案

我們需要找到注釋的起始位置 <!--，然后獲取字符直到注釋的末尾 -->。

行得通的表達式可以是 <!--.*?--> —— 惰性量詞使得點在 --> 之前 停止。我們還需要為點添加修飾符 s 以包含換行符。

否則找不到多行注釋：

let regexp = /<!--.*?-->/gs;

let str = `... <!-- My -- comment
 test --> ..  <!----> ..
`;

alert( str.match(regexp) ); // '<!-- My -- comment \n test -->', '<!---->'

尋找 HTML 標簽

創(chuàng)建一個正則表達式來尋找所有（開始和結束）HTML 標簽及其特性。

用例：

let regexp = /你的正則表達式/g;

let str = '<> <a href="/"> <input type="radio" checked> <b>';

alert( str.match(regexp) ); // '<a href="/">', '<input type="radio" checked>', '<b>'

這里我們假設標簽特征中不包含 < 和 >（包括被引號包裹的內容），這樣就簡單多了。

解決方案

答案是 <[^<>]+>。

let regexp = /<[^<>]+>/g;

let str = '<> <a href="/"> <input type="radio" checked> <b>';

alert( str.match(regexp) ); // '<a href="/">', '<input type="radio" checked>', '<b>'