贪婪、勉强和占有限定符的区别

Question

贪婪、勉强和占有限定符的区别

419

我在stackoverflow上找到了这个正则表达式的教程，虽然我直观地理解了“贪婪”、“勉强”和“占有”限定符的作用，但我的理解似乎存在重大漏洞。

具体来说，在以下示例中：

Enter your regex: .*foo // Greedy qualifier
Enter input string to search: xfooxxxxxxfoo
I found the text "xfooxxxxxxfoo" starting at index 0 and ending at index 13.

Enter your regex: .*?foo // Reluctant qualifier
Enter input string to search: xfooxxxxxxfoo
I found the text "xfoo" starting at index 0 and ending at index 4.
I found the text "xxxxxxfoo" starting at index 4 and ending at index 13.

Enter your regex: .*+foo // Possessive qualifier
Enter input string to search: xfooxxxxxxfoo
No match found.

这段解释提到了“吃掉”整个输入字符串，字母被“消耗”，匹配器“回退”，“foo”的最右出现位置被“反刍”等。尽管这些比喻很好，但我仍然不理解是由谁来吃掉什么...你知道有没有其他教程可以简明地解释正则表达式引擎的工作原理吗？

或者，如果有人可以用稍微不同的措辞来解释以下段落，那将非常感激：

第一个例子使用贪婪量词.*来查找“任何东西”，零次或多次出现，后跟字母"f"，"o"，"o"。因为量词是贪婪的，所以表达式中的.*部分首先吃掉整个输入字符串。此时，整个表达式无法成功，因为最后三个字母（"f"，"o"，"o"）已经被消耗掉了[由谁？]。因此，匹配器一次回退[从右到左?]一个字母，直到“foo”的最右出现位置被“反刍”[这是什么意思？]，此时匹配成功并结束搜索。

但是，第二个例子是慢性的，所以它首先吃掉[由谁？]“nothing”。因为"foo"不出现在字符串的开头，所以它被迫吞下第一个字母（一个"x"），这触发了第一个匹配0和4。我们的测试工具继续该过程，直到输入字符串用尽。它在4和13处找到另一个匹配项。

第三个例子无法找到匹配项，因为量词是占有性的。在这种情况下，整个输入字符串都被.*+[如何？]消耗掉，没有剩余的内容来满足表达式末尾的“foo”。对于想要全部占有某些内容而永不回退的情况，请使用占有性量词；在匹配未立即找到的情况下，它将比等效的贪婪量词性能更好。

- Regex Rookie

33

类似于*、+和?的最大匹配量词是贪婪的。类似于*?、+?和??的最小匹配量词是懒惰的。类似于*+、++和?+的占有式匹配量词是固执的。 - tchrist

8

这个问题已经被添加到Stack Overflow 正则表达式 FAQ中的“量词 > 更多差异”部分。 - aliteralmind

1

值得关注的是：Java™教程 - 贪婪、勉强和占有量词之间的差异 - 向下滚动查看章节。 - Guy Coder

我觉得那个资源中的术语和解释相当糟糕。 - java-addict301

7个回答

74

这只是我的实践输出，用于展示场景-

- SIslam

4

除了最后一种情况（所有格），我认为不需要多次传递 -- 直接一次性获取整个字符串即可。 - treat your mods well

@phyzome 我认为现在可以了吗？ - SIslam

2

感谢您的视觉解释 :) - Lars Moelleken

在 EXPRESSION .*?foo () 中，第五遍不应该将 [f][o][o] 矩形标记为黄色吗？ - tonix

1

@tonix 是的！在表达式 .*?foo 和 .*+foo 中，需要对匹配部分进行黄色标记。 - SIslam

24

我以前没有听说过“regurgitate”或“backing off”的确切术语；替换这些短语的词组是“backtracking”，但“regurgitate”似乎是一个不错的词语，用于描述“在回溯之前被暂时接受的内容再次被丢弃”。

需要了解有关大多数正则表达式引擎的重要事情是它们具有回溯功能：当尝试匹配正则表达式的整个内容时，它们将“暂时”接受可能的部分匹配。如果无法在第一次尝试中完全匹配正则表达式，则正则表达式引擎将回溯到其匹配的一项上。它将尝试使用不同的方式匹配`*`、`+`、`?`、选择、或者`{n，m}`重复，并尝试再次匹配。（是的，这个过程可以很长时间。）

引用：

第一个示例使用贪婪量词`.*`查找“任何东西”，零次或多次，然后是字母“f”“o”“o”。由于量词是贪婪的，表达式中的`.*`部分首先吃掉了整个输入字符串。此时，整个表达式不能成功，因为最后三个字母（“f”“o”“o”）已经被消耗掉了（由谁消耗？）。

最后三个字母`f`、`o`和`o`已经被规则的初始`.*`部分消耗了。但是，正则表达式中的下一个元素`f`在输入字符串中没有剩余内容。引擎将被迫回溯到其初始的`.*`匹配，并尝试匹配除最后一个字符以外的所有字符。（它可能会很“聪明”，回溯到除最后三个字符以外的所有字符，因为它有三个文字项，但我不知道这个级别的实现细节。）

引用：slowly backs off (从右向左？) 每次退回一个字母，直到 "foo" 最右边的出现被拒绝 (这是什么意思？)。

这意味着在匹配 .* 时，foo 已被尝试性地包括在内。因为该尝试失败了，正则表达式引擎尝试接受比.*少一个字符的匹配。如果在此示例中的.*之前已成功匹配，则引擎可能会尝试缩短.*的匹配（从右到左，如您所指出，因为它是贪婪限定符），如果无法匹配所有输入，则可能被迫重新评估其在我的假设示例中匹配的内容。在.*之前匹配的任何内容。

匹配成功的点，并结束搜索。

然而，第二个示例是不情愿的，因此它首先消耗 (由谁？) "nothing"。因为 "foo" 不出现在字符串开头，它被强制吞下。

初始的 nothing 被.?*消耗，.?*将消耗最短可能的任何内容，只要使其余正则表达式能够匹配。

第一个字母（一个 "x"）触发了第一次在 0 和 4 匹配。我们的测试工具继续这个过程，直到输入字符串用尽。它在 4 和 13 找到另一个匹配项。

第三个示例找不到匹配项。

由于量词是占有性的，.*+会尽可能多地匹配，在正则表达式整体无法找到匹配项时不会回溯以查找新的匹配项。因为占有形式不执行回溯，您可能不会经常看到使用.*+，而是看到类似字符类或相似限制： account: [[:digit:]]*+ phone: [[:digit:]]*+。

这可以极大地加快正则表达式匹配速度，因为您要告诉正则表达式引擎，如果输入不匹配，它就应该永远不回溯到潜在的匹配项上。（如果您必须手动编写所有匹配代码，则类似于从未使用putc(3)来“推回”输入字符。这将非常类似于单个字符的推回，但是正则表达式引擎比一个字符的推回更好，它们可以倒退到零并再次尝试。 :)

但最重要的是，这也可以让您编写恰好匹配所需内容的正则表达式。我很难想出一个简单的例子 :) 但是，使用占有量词和贪婪量词编写正则表达式可以得到不同的匹配项，其中一个可能更合适。

在表达式末尾留下不足以满足“foo”的内容，使用占有量词处理需要全部获取某项内容而从未回退（什么是“回退”？）的情况；在无法立即找到匹配项的情况下，使用等效的贪婪量词。

在这个上下文中，“回退”指的是“回溯”-放弃试图另外一部分匹配项以尝试另一部分匹配项，这可能成功也可能失败。

- sarnold

2

我怀疑永远不会出现占有量词匹配到一些贪婪量词无法匹配的情况。我相信以下证明了这一点：贪婪量词总是尽可能地匹配，如果找不到匹配就回溯。而占有量词也是尽可能地匹配，但如果找不到匹配，则直接退出。因此，可能存在一些贪婪量词能够匹配而占有量词无法匹配的内容，但反之则不行，因为它们都以相同的顺序搜索"树"，只是占有量词更容易放弃。 ;) - Wildcard

2

确认：原子组和占有量词就是为了提高效率而禁止回溯。 来自regular-expressions.info 因此，这个答案中的语句“但更重要的是，这也可以让您编写正则表达式，精确匹配您需要匹配的内容。”实际上并不完全准确。 - Wildcard

1

@Wildcard，谢谢您的评论；这可能解释了为什么我很难举出一个例子。嘿嘿。 - sarnold

21

http://swtch.com/~rsc/regexp/regexp1.html

我不确定这是互联网上最好的解释，但它写得相当好并且详细适当，我一直回来看。你也许想去看看。

如果您需要更高级别（较少详细的）解释，对于像您查看的简单正则表达式，正则表达式引擎通过回溯工作。基本上，它选择（“吃掉”）字符串的一部分并尝试将正则表达式与该部分匹配。如果匹配成功，则很好。如果没有，则引擎会改变其选择的字符串部分，并尝试将正则表达式与该部分匹配，以此类推，直到它尝试了每个可能的选择。

这个过程是递归使用的：在尝试将字符串与给定的正则表达式匹配时，引擎将正则表达式拆分成多个片段，并将算法分别应用于每个片段。

贪婪、勉强和占有量词之间的区别在于引擎在选择要尝试匹配的字符串部分以及如何修改该选择（如果第一次无法匹配）时的处理。规则如下：

贪婪量词告诉引擎从整个字符串开始（或者至少所有前面未被前面的正则表达式部分匹配的部分）并检查它是否与正则表达式匹配。如果是，则很好；引擎可以继续处理剩下的正则表达式。如果没有，它会再次尝试，但是会将待匹配的字符串部分减少一个字符（即最后一个字符）。如果还不行，它就会再减去一个字符，以此类推。因此，贪婪量词按长度从长到短的顺序检查可能的匹配项。
不情愿的量词告诉引擎从字符串的最短可能匹配开始。如果匹配成功，引擎可以继续；如果不行，它会在正在检查的字符串段中添加一个字符并尝试，直到找到匹配或整个字符串被用完为止。因此，不情愿的量词按从短到长的顺序检查可能的匹配项。
占有量词在第一次尝试时就像贪婪量词一样：它告诉引擎从检查整个字符串开始。不同之处在于，如果它失败了，占有量词会立即报告匹配失败。引擎不会改变正在查看的字符串部分，也不会再做任何尝试。

这就是为什么在你的例子中占有量词匹配失败的原因：`.*+` 被匹配整个字符串，它匹配成功，但然后引擎继续寻找 `foo` 之后的其他字符——但当然没有找到，因为你已经到达了字符串的末尾。如果是贪婪量词，它将回溯并尝试使 `.*` 仅匹配到倒数第二个字符，然后匹配到倒数第三个字符，然后匹配到倒数第四个字符，这样才成功，因为只有在 `.*` “吞食” 字符串的早期部分后还剩一个 `foo` 。

- David Z

1

那是一个很棒的资源。我喜欢状态机图。 :) - Regex Rookie

@正则表达式新手：很高兴你喜欢它 :) 然而，在查看了那个网站之后，我认为我应该澄清一下它的目的是推广正则表达式引擎的另一种实现。我（部分地）和其他答案描述的回溯算法是_慢_的方法；它是与网页中描述的NFA/DFA思想完全不同的算法。回溯只是更容易理解，这就是为什么正则表达式通常向初学者解释的原因。 - David Z

@David Zaslavsky：解释得很好。你在“贪婪量词告诉引擎从整个字符串开始（或者至少是所有还没有被前面的正则表达式匹配的部分）”中括号里的评论很重要。它们也适用于勉强和占有量词。这使得你的解释与我们将示例模式从（“.foo”;“.?foo”;和“.+foo”）更改为（“foo.”;“foo.?”;和“foo.+”）时发生的情况相容。 - John Bentley

实际上，在正则表达式的常规（计算机科学意义上），xfooxxxxxxfoo确实与.*foo匹配。NFA将是一个状态，其中它在任何字符之间循环，并且然后可以跳转到foo。DFA将是该NFA的直接翻译。它可以在8个状态中完成。 - user4951

@JimThio 是的，因为那不是一个所有格量词。 - David Z

15

这里是我使用单元格和索引位置的方法（请参见此处的图解来区分单元格和索引位置）。

贪婪模式 - 尽可能多地匹配贪婪量词和整个正则表达式。如果没有匹配，回溯到贪婪量词。

输入字符串：xfooxxxxxxfoo
正则表达式: .*foo

上述正则表达式由两部分组成：
(i)'.*' 和
(ii)'foo'

以下每个步骤将分析这两个部分。对于“通过”或“失败”的匹配，额外的注释在大括号中解释。

步骤1:
(i) .* = xfooxxxxxxfoo - 通过（“.*”是一个贪婪量词，将使用整个输入字符串）
(ii) foo = 索引13后没有字符可匹配 - 失败
匹配失败。

步骤2:
(i) .* = xfooxxxxxxfo - 通过（回溯到贪婪量词“.*”）
(ii) foo = o - 失败
匹配失败。

步骤3:
(i) .* = xfooxxxxxxf - 通过（回溯到贪婪量词“.*”）
(ii) foo = oo - 失败
匹配失败。

步骤4:
(i) .* = xfooxxxxxx - 通过（回溯到贪婪量词“.*”）
(ii) foo = foo - 通过
报告匹配成功

结果: 找到1个匹配项
我发现文本“xfooxxxxxxfoo”从索引0开始，到索引13结束。

懒惰模式 - 尽可能少地匹配懒惰量词并匹配整个正则表达式。如果没有匹配，请添加字符到懒惰量词。

输入字符串：xfooxxxxxxfoo

正则表达式： .*?foo

上面的正则表达式分为两部分：
(i) '.*?' 和
(ii) 'foo'

步骤1：
.*? = ''（空）- 通过（尽可能少地匹配迟疑量词“.*？” 。索引0包含''，是一次匹配。）
foo = xfo - 失败（单元格0、1、2 - 即0和3之间的索引）
匹配失败。

步骤2：
.*? = x - 通过（向迟疑量词“.*？”中添加字符。单元格0包含'x'，是一次匹配。）
foo = foo - 通过
报告匹配

步骤3：
.*? = ''（空）- 通过（尽可能少地匹配迟疑量词“.*？” 。索引4包含''是一次匹配。）
foo = xxx - 失败（单元格4、5、6 - 即4和7之间的索引）
匹配失败。

步骤4：
.*? = x - 通过（向迟疑量词“.*？”中添加字符。单元格4是一次匹配。）
foo = xxx - 失败（单元格5、6、7 - 即5和8之间的索引）
匹配失败。

步骤5：
.*? = xx - 通过（向迟疑量词“.*？”中添加字符。单元格4到5是一次匹配。）
foo = xxx - 失败（单元格6、7、8 - 即6和9之间的索引）
匹配失败。

步骤6：
.*? = xxx - 通过（向迟疑量词“.*？”中添加字符。单元格4到6是一次匹配。）
foo = xxx - 失败（单元格7、8、9 - 即7和10之间的索引）
匹配失败。

步骤7：
.*? = xxxx - 通过（向迟疑量词“.*？”中添加字符。单元格4到7是一次匹配。）

foo = xxf - 失败（单元格8、9、10，即索引在8和11之间）
匹配失败。

第8步：
.*? = xxxxx - 通过（向勉强量词“.*？”添加字符。单元格4至8。）
foo = xfo - 失败（单元格9、10、11，即索引在9和12之间）
匹配失败。

第9步：
.*? = xxxxxx - 通过（向勉强量词“.*？”添加字符。单元格4至9。）
foo = foo - 通过（单元格10、11、12，即索引在10和13之间）
报告匹配

第10步：
.*? =''（空白）- 通过（以最少的可能性匹配勉强量词“.*？”。索引13为空白。）
foo =无可匹配字符-失败（在索引13之后没有任何内容可以匹配）
匹配失败。

结果：2个匹配项
我发现文本“xfoo”从索引0开始，结束于索引4。
我发现文本“xxxxxxfoo”从索引4开始，结束于索引13。

占有 - 尽可能多地匹配占用量词并匹配整个正则表达式。不要回溯。

输入字符串：xfooxxxxxxfoo
正则表达式： .*+foo

上述正则表达式分为两部分：“.*+”和“foo”。

第1步：
.*+ = xfooxxxxxxfoo - 通过（尽可能多地匹配占有量词“.*+”）
foo =无可匹配字符-失败（索引13之后没有内容可以匹配）
匹配失败。

注意：不允许回溯。

结果：0个匹配项

- raka

2

贪婪模式: "匹配尽可能长的字符序列"

懒惰模式: "匹配尽可能短的字符序列"

占有模式: 这有点奇怪，因为它与贪婪和懒惰相比，并不尝试找到整个正则表达式的匹配。

顺便说一下：没有正则表达式模式匹配器实现会使用回溯。所有现实生活中的模式匹配器都非常快速 - 几乎与正则表达式的复杂性无关！

- Tilo Koerbs

据我所知，现在大多数通用实现都充斥着各种功能，因此不使用回溯已经变得不可能。因此理论上来说，它们在某些情况下应该非常（指数级）缓慢。但是对于这些情况，模式匹配器中内置了特殊的优化。 - Robert

回溯是真实存在的，而且很容易编写出在你不希望回溯时却会回溯的示例。https://blog.cloudflare.com/details-of-the-cloudflare-outage-on-july-2-2019/ 是一个很好的现实生活中的例子。使用所有权量词可以是避免回溯的好方法。 - Robert Tupelo-Schneck

0

贪婪量词是指在迭代过程中使用字符串中所有未经验证的字符进行模式匹配。未经验证的字符位于活动序列中。每次不匹配时，末尾的字符会被隔离，然后再次进行检查。

当正则表达式模式的前导条件仅满足活动序列时，将尝试使用隔离区验证剩余条件。如果此验证成功，则隔离区中的匹配字符将被验证，未匹配的剩余字符将保持未验证状态，并在下一次迭代开始时使用。

字符的流动是从活动序列到隔离区。结果行为是尽可能包含原始序列中的内容。

懒惰量词与贪婪量词大致相同，只是字符的流动方向相反--即它们从隔离区开始流入活动序列。结果行为是尽可能少地包含原始序列中的内容。

占有量词没有隔离区，并且包括固定的活动序列中的所有内容。

- Chad Philip Johnson

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Anomie · Accepted Answer

我会尝试一下。

贪婪量词首先尽可能匹配，所以.*匹配整个字符串。然后匹配器尝试匹配后面的f，但是没有剩余字符了。所以它“回溯”，使贪婪量词匹配一个字符少（留下字符串末尾的“o”未匹配）。仍然无法匹配正则表达式中的f，所以它再次回溯一步，使贪婪量词再次减少一个字符的匹配（留下字符串末尾的“oo”未匹配）。这仍然无法匹配正则表达式中的f，所以它又回溯了一步（留下字符串末尾的“foo”未匹配）。现在，匹配器终于匹配到了正则表达式中的f，并且也匹配了o和下一个o。成功！

勉强或“非贪婪”量词首先尽可能少地匹配。因此，.*一开始什么都不匹配，导致整个字符串都没有匹配成功。然后匹配器尝试匹配后面的f，但是未匹配部分以“x”开头，因此无法匹配。所以匹配器回溯，并使非贪婪量词匹配一个字符（现在匹配了“x”，留下字符串末尾的“fooxxxxxxfoo”未匹配）。然后它尝试匹配f，这次成功了，并且正则表达式中的o和下一个o也匹配。成功！

在您的示例中，它接着使用剩余未匹配部分“xxxxxxfoo”重复同样的过程。

一个占有量词与贪婪量词非常相似，但它不会回溯。因此，它以.*匹配整个字符串，没有留下任何未匹配的内容。接着，它已经没有剩余的内容可以与正则表达式中的f匹配。由于占有量词不回溯，匹配也随之失败。