贪婪和懒惰量词

量词乍一看非常简单，但实际上它们可能很棘手。

如果我们计划查找比 /\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. 第一步相同：它在第 3 个位置找到模式开始 '"'

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"

正则表达式 "[^"]+" 给出了正确的结果，因为它查找一个引号 '"'，后跟一个或多个非引号 [^"]，然后是结束引号。

当正则表达式引擎查找 [^"]+ 时，它会在遇到结束引号时停止重复，我们就完成了。

请注意，这种逻辑不会取代懒惰量词！

它只是不同。有时我们需要一个或另一个。

让我们看一个懒惰量词失败而这种变体工作正常的例子。

例如，我们想要找到形如<a href="..." class="doc">的链接，其中href可以是任何内容。

应该使用哪个正则表达式呢？

第一个想法可能是：/<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+消耗所有可能的数字。当无法再消耗更多数字（没有更多数字或字符串结束）时，它继续匹配模式的其余部分。如果没有匹配项，则减少重复次数（回溯）并再次尝试。

懒惰

由量词后的问号?启用。正则表达式引擎尝试在每次重复量词字符之前匹配模式的其余部分。

正如我们所见，懒惰模式并不是贪婪搜索的“灵丹妙药”。另一种方法是“微调”的贪婪搜索，带有排除项，如模式"[^"]+"。