貪婪和懶惰量詞

量詞乍看之下很簡單，但實際上它們可能會很棘手。

如果我們計畫尋找比 /\d+/ 更複雜的內容，我們應該非常了解搜尋運作的方式。

以下列任務為例。

我們有一段文字，需要將所有引號 "..." 替換為法文引號：«...»。在許多國家，法文引號是印刷體的首選。

例如："Hello, world" 應變更為 «Hello, world»。還有其他引號，例如 „Witaj, świecie!”（波蘭語）或 「你好，世界」（中文），但對於我們的任務，我們選擇 «...»。

首先要找出帶引號的字串，然後我們才能替換它們。

類似 /".+"/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，因此立即沒有比對。

   然後它前進：移至來源字串中的下一個位置，並嘗試在那裡找到樣式的第一個字元，再次失敗，最後在第 3 個位置找到引號

2. 引號已偵測到，然後引擎嘗試找到樣式其餘部分的比對。它嘗試查看主旨字串的其餘部分是否符合 .+"。

   在我們的案例中，下一個樣式字元是 .（一個點）。它表示「任何字元，換行符號除外」，因此下一個字串字母 'w' 符合

3. 然後，由於量詞 .+，點會重複。正規表示式引擎會將一個字元一個字元加入比對。

   …直到何時？所有字元都符合點，因此只有在到達字串結束時才會停止

4. 現在，引擎已完成重複 .+，並嘗試找到樣式的下一個字元。它是引號 "。但有一個問題：字串已結束，沒有更多字元了！

   正規表示式引擎了解它取用了過多的 .+，並開始回溯。

   換句話說，它會將量詞的比對縮短一個字元

   現在，它假設 .+ 在字串結束前一個字元結束，並嘗試從該位置比對樣式的其餘部分。

   如果那裡有引號，則搜尋就會結束，但最後一個字元是 'e'，因此沒有符合。

5. …因此引擎會將 .+ 的重複次數減少一個字元

   引號 '"' 不符合 'n'。

6. 引擎持續回溯：它會減少 '.' 的重複次數，直到模式的其餘部分（在我們的案例中為 '"'）符合為止

7. 符合完成。

8. 因此第一個符合為 "witch" and her "broom"。如果正規表示式有旗標 g，則搜尋會從第一個符合結束的地方繼續。字串 is one 的其餘部分沒有更多引號，因此沒有更多結果。

這可能不是我們預期的，但這就是它的運作方式。

在貪婪模式（預設）中，量化字元會重複盡可能多次。

正規表示式引擎會為 .+ 新增與它可以一樣多的字元到符合中，然後如果模式的其餘部分不符合，就逐一縮短它。

對於我們的任務，我們想要另一種方式。這時惰性模式就能派上用場。

惰性模式

量化詞的惰性模式與貪婪模式相反。它的意思是：「重複最少次數」。

我們可以在量化詞後加上問號 '?' 來啟用它，這樣它就會變成 *? 或 +? 甚至 ?? 表示 '?'。

為了清楚說明：通常問號 ? 本身就是一個量化詞（零或一），但如果在 另一個量化詞（甚至它本身） 之後加上它，它就會有另一個意思 – 它會將符合模式從貪婪切換為惰性。

正規表示式 /".+?"/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. 然後正規表示式引擎會增加點號的重複次數，並再試一次

   再次失敗。然後重複次數會再增加一次，以此類推…

5. …直到找到與模式其餘部分相符的項目

6. 下一次搜尋從目前相符項目的結尾開始，並產生另一個結果

在這個範例中，我們看到 +? 的惰性模式如何運作。量詞 *? 和 ?? 的運作方式類似，正規表示式引擎只會在模式的其餘部分無法在給定的位置相符時，才會增加重複次數。

惰性只會對帶有 ? 的量詞啟用。

其他量詞仍然是貪婪的。

例如

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

1. 模式 \d+ 會嘗試比對盡可能多的數字（貪婪模式），所以它會找到 123 並停止，因為下一個字元是空白 ' '。

2. 然後模式中有一個空白，它會相符。

3. 然後是 \d+?。量詞處於惰性模式，所以它會找到一個數字 4 並嘗試檢查模式的其餘部分是否從那裡開始相符。

   …但 \d+? 之後模式中沒有任何東西。

   惰性模式不會在不需要時重複任何東西。模式結束了，所以我們完成了。我們有一個相符項目 123 4。

替代方法

使用正規表示式，通常有不止一種方法可以執行相同的工作。

在我們的案例中，我們可以使用正規表示式 "[^"]+" 在非惰性模式下找到引號字串。

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

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

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

正規表示式 "[^"]+" 會提供正確的結果，因為它會尋找一個引號 '"' 後接一個或多個非引號 [^"]，然後再接上一個引號。

當正規表示式引擎尋找 [^"]+ 時，它會在遇到引號時停止重複，而我們就完成了。

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

它只是不同而已。有時我們需要一個，有時需要另一個。

讓我們來看一個惰性量詞失敗而這個變體正確運作的範例。

例如，我們想要找到任何 href 的連結形式為 <a href="..." class="doc">。

要使用哪個正規表示式？

第一個想法可能是：/<a href=".*" class="doc">/g。

讓我們檢查一下

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

// Works!
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;

// Whoops! Two links in one match!
alert( str.match(regexp) ); // <a href="link1" class="doc">... <a href="link2" class="doc">

現在結果是錯誤的，原因與我們的「女巫」範例相同。量詞 .* 取用了過多字元。

比對看起來像這樣

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

// Works!
alert( str.match(regexp) ); // <a href="link1" class="doc">, <a href="link2" class="doc">

現在它似乎運作了，有兩個比對

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

// Wrong match!
alert( str.match(regexp) ); // <a href="link1" class="wrong">... <p style="" class="doc">

現在它失敗了。比對不僅包括一個連結，還包括連結後面的許多文字，包括 <p...>。

為什麼？

以下是發生的事

1. 首先，正規表示式會找到一個連結開頭 <a href="。
2. 然後它會尋找 .*?：取一個字元（惰性！），檢查是否有 " class="doc"> 的比對（沒有）。
3. 然後再將另一個字元取到 .*? 中，以此類推…直到它最後到達 " class="doc">。

但問題是：這已經超出連結 <a...>，在另一個標籤 <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;

// Works!
alert( str1.match(regexp) ); // null, no matches, that's correct
alert( str2.match(regexp) ); // <a href="link1" class="doc">, <a href="link2" class="doc">

摘要

量詞有兩種工作模式

貪婪

預設情況下，正規表示式引擎會嘗試盡可能多次重複量化的字元。例如，\d+ 會消耗所有可能的數字。當無法再消耗更多（沒有更多數字或字串結束）時，它會繼續比對模式的其餘部分。如果沒有比對，它會減少重複次數（回溯）並再次嘗試。

惰性

量詞後加上問號 ? 啟用。regexp 引擎會嘗試在量化字元的每次重複之前比對模式的其餘部分。

正如我們所見，惰性模式並非貪婪搜尋的「萬靈丹」。另一種方法是「微調」貪婪搜尋，並加上排除，例如在模式 "[^"]+" 中。