393

我找到了这个关于正则表达式的教程，虽然我直观地理解了“贪婪”、“不情愿”和“占有”限定词的作用，但我的理解似乎有一个严重的漏洞。

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

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"）已经被 [by who?] 消耗掉了。因此，匹配器慢慢地后退 [从右到左？] 一次一个字母，直到最右边出现的"foo"被反刍 [这是什么意思？]，此时匹配成功并且搜索结束。

然而，第二个例子是不情愿的，所以它首先消耗[由谁？]“无”。因为"foo"没有出现在字符串的开头，所以它被迫吞下[谁吞下？]第一个字母（an "x"），这会在 0 和 4 处触发第一次匹配。我们的测试工具继续这个过程，直到输入字符串用完. 它在 4 点和 13 点找到另一个匹配项。

第三个示例找不到匹配项，因为量词是所有格。在这种情况下，整个输入字符串被.*+[how?] 使用，没有留下任何东西来满足表达式末尾的“foo”。使用所有格量词表示你想抓住所有东西而不退缩[退缩是什么意思？]；在没有立即找到匹配的情况下，它将优于等效的贪婪量词。

4

7 回答 7

553

我会试一试。

贪心量词首先尽可能匹配。所以.*匹配整个字符串。然后匹配器尝试匹配f以下内容，但没有剩余字符。所以它“回溯”，使贪婪的量词少匹配一个字符（使字符串末尾的“o”不匹配）。这仍然与正则表达式中的不匹配f，因此它又回溯了一步，使贪婪的量词再次少匹配一个字符（使字符串末尾的“oo”不匹配）。这仍然与正则表达式中的不匹配f，因此它又回溯了一步（使字符串末尾的“foo”不匹配）。现在，匹配器终于匹配了f正则表达式中的oo也很匹配。成功！

一个不情愿或“非贪婪”的量词首先尽可能少地匹配。所以.*起初不匹配，使整个字符串不匹配。然后匹配器尝试匹配f以下内容，但字符串的不匹配部分以“x”开头，因此不起作用。所以匹配器回溯，使非贪婪量词再匹配一个字符（现在它匹配“x”，留下“fooxxxxxxfoo”不匹配）。然后它尝试匹配f成功的 , 以及正则表达式匹配中的theo和下一个。o成功！

在您的示例中，然后它会按照相同的过程使用字符串的剩余不匹配部分“xxxxxxfoo”重新开始该过程。

所有格量词就像贪婪量词一样，但它不会回溯。所以它从.*匹配整个字符串开始，没有任何不匹配的东西。然后没有任何东西可以与f正则表达式中的匹配。由于所有格量词不会回溯，因此匹配失败。

于 2011-03-16T01:22:08.730 回答
66

可视化场景只是我的练习输出-

视觉形象

于 2015-11-07T12:18:18.320 回答
24

我以前没有听过确切的术语“反刍”或“后退”；取代这些的短语是“回溯”，但“反刍”似乎与“在回溯之前暂时接受的内容再次将其丢弃”的任何短语一样好。

对于大多数正则表达式引擎，需要意识到的重要一点是它们正在回溯：它们会暂时接受潜在的部分匹配，同时尝试匹配正则表达式的全部内容。如果第一次尝试时无法完全匹配正则表达式，则正则表达式引擎将回溯其匹配项之一。它将尝试以不同的方式匹配、、、*交替或重复，然后重试+。（是的，这个过程可能需要很长时间。）?{n,m}

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

最后三个字母 、f、o和o已被.*规则的初始部分使用。但是，正则表达式中的下一个元素 ,f在输入字符串中没有任何内容。引擎将被迫回溯其初始.*匹配，并尝试匹配除最后一个字符之外的所有字符。（它可能很聪明，可以回溯到最后三个，因为它有三个字面术语，但我不知道这个级别的实现细节。）

所以匹配器慢慢地后退（从右到左？）一次一个字母，直到最右边出现的“foo”被反刍（这是什么意思？），此时

这意味着在匹配的时候foo已经暂时.*包含了。由于该尝试失败，正则表达式引擎尝试在.*. 如果在这个例子中之前有一个成功的匹配.*，那么引擎可能会尝试缩短.*匹配（从右到左，正如你所指出的，因为它是一个贪婪的限定符），如果它无法匹配整个输入，那么在我的假设示例中，它可能会被迫重新评估它之前匹配的内容。.*

点匹配成功，搜索结束。

然而，第二个例子是不情愿的，所以它首先消耗（由谁？）“无”。因为“富”

最初的 nothing 被 消耗.?*，这将消耗尽可能少的任何东西，以使正则表达式的其余部分匹配。

没有出现在字符串的开头，它被强制吞下（谁吞下？）

.?*在回溯初始失败以将整个正则表达式与最短的匹配项匹配之后，再次消耗第一个字符。（在这种情况下，正则表达式引擎将匹配.*?从左到右扩展，因为.*?不情愿。）

第一个字母（一个“x”），它在 0 和 4 处触发第一个匹配。我们的测试工具继续该过程，直到输入字符串用完。它在 4 点和 13 点找到另一个匹配项。

第三个示例找不到匹配项，因为量词是所有格。在这种情况下，整个输入字符串被 .*+ 消耗，（如何？）

A.*+将尽可能多地消耗，并且当整个正则表达式无法找到匹配项时，不会回溯以查找新匹配项。因为所有格形式不执行回溯，所以您可能不会看到很多使用.*+，而是使用字符类或类似限制：account: [[:digit:]]*+ phone: [[:digit:]]*+.

这可以大大加快正则表达式匹配，因为您告诉正则表达式引擎，如果输入不匹配，它永远不应该回溯潜在的匹配项。（如果您必须手动编写所有匹配的代码，这将类似于从不使用putc(3)“推回”输入字符。这与第一次尝试时可能编写的幼稚代码非常相似。除了正则表达式引擎是比单个后推字符要好得多，他们可以将所有回退到零并重试。:)

但除了潜在的加速之外，这还可以让您编写与您需要匹配的内容完全匹配的正则表达式。我在想出一个简单的例子时遇到了麻烦：）但是使用所有格与贪婪量词编写正则表达式可以为您提供不同的匹配项，其中一个或另一个可能更合适。

没有留下任何东西来满足表达式末尾的“foo”。使用所有格量词表示你想抓住所有东西而不退缩（退缩是什么意思？）；它会表现出色

在这种情况下，“退避”意味着“回溯”——放弃一个暂定的部分匹配来尝试另一个部分匹配，这可能会也可能不会成功。

在没有立即找到匹配的情况下等效的贪婪量词。

于 2011-03-16T01:24:45.843 回答
20

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

我不确定这是否是互联网上最好的解释，但它写得相当好，而且详细得当，我一直在回来。你可能想检查一下。

如果您想要更高级别（不太详细的解释），对于简单的正则表达式，例如您正在查看的正则表达式，正则表达式引擎通过回溯工作。本质上，它选择（“吃”）字符串的一部分，并尝试将正则表达式与该部分进行匹配。如果匹配，那就太好了。如果不是，引擎会更改其对字符串部分的选择，并尝试将正则表达式与该部分进行匹配，依此类推，直到尝试了所有可能的选择。

此过程以递归方式使用：在尝试将字符串与给定的正则表达式匹配时，引擎会将正则表达式拆分为多个片段，并将算法单独应用于每个片段。

贪婪、不情愿和所有格量词之间的区别在于引擎选择尝试匹配字符串的哪个部分，以及如果第一次不工作时如何修改该选择。规则如下：

  • 一个贪婪的量词告诉引擎从整个字符串开始（或者至少，所有它还没有被正则表达式的前面部分匹配）并检查它是否匹配正则表达式。如果是这样，那就太好了；引擎可以继续使用正则表达式的其余部分。如果不是，它会再次尝试，但会从要检查的字符串部分中删除一个字符（最后一个字符）。如果这不起作用，它会剪掉另一个字符，等等。所以一个贪婪的量词会按照从最长到最短的顺序检查可能的匹配。

  • 一个不情愿的量词告诉引擎从字符串中最短的一段开始。如果匹配，则引擎可以继续；如果不是，它将一个字符添加到正在检查的字符串部分并尝试，依此类推，直到找到匹配项或整个字符串已用完。因此，不情愿的量词按从最短到最长的顺序检查可能的匹配。

  • 所有格量词就像第一次尝试时的贪婪量词：它告诉引擎通过检查整个字符串来启动。不同之处在于，如果它不起作用，所有格量词会报告匹配当时和那里失败。引擎不会更改正在查看的字符串部分，也不会再进行任何尝试。

这就是为什么所有格量词匹配在您的示例中失败的原因： 对匹配.*+的整个字符串进行检查，但随后引擎继续查找其他字符foo- 但当然它没有找到它们，因为您' 已经在字符串的末尾。如果它是一个贪婪的量词，它会回溯并尝试使.*唯一匹配到倒数第二个字符，然后到倒数第三个字符，然后到倒数第四个字符，这会成功，因为只有这样在“吃掉”字符串的较早部分之后有一个foo左边。.*

于 2011-03-16T01:25:06.560 回答
15

这是我使用单元格和索引位置的看法（请参阅此处的图表以区分单元格和索引）。

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

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

上面的Regex有两部分：
(i)'.*'和
(ii)'foo'

下面的每一步都会对这两部分进行分析。大括号中解释了匹配“通过”或“失败”的附加注释。

第 1 步：
(i) .* = xfooxxxxxxfoo - PASS（'.*' 是一个贪婪的量词，将使用整个输入字符串）
(ii) foo = 在索引 13 后没有剩余字符可匹配 - FAIL
匹配失败。

第 2 步：
(i) .* = xfooxxxxxxfo - PASS（在贪婪量词 '.*' 上回溯）
(ii) foo = o - FAIL
匹配失败。

第 3 步：
(i) .* = xfooxxxxxxf - PASS（在贪婪量词 '.*' 上回溯）
(ii) foo = oo - FAIL
匹配失败。

第 4 步：
(i) .* = xfooxxxxxx - PASS（在贪婪量词 '.*' 上回溯）
(ii) foo = foo - PASS
报告匹配

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

Reluctant - 尽可能少地匹配不情愿的量词并匹配整个正则表达式。如果没有匹配，则将字符添加到不情愿的量词中。

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

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

第 1 步：
.*? = '' (空白) - PASS (尽可能少匹配不情愿的量词'.*?'。索引 0 有 '' 是匹配的。)
foo = xfo - FAIL (单元格 0,1,2 - 即之间的索引0 和 3)
匹配失败。

第 2 步：
.*? = x - PASS（将字符添加到不情愿的量词 '.*?'。单元格 0 具有 'x' 是匹配项。）
foo = foo - PASS
报告匹配

第 3 步：
.*? = '' (空白) - PASS (尽可能少地匹配不情愿的量词'.*?'。索引 4 有 '' 是匹配的。)
foo = xxx - FAIL (单元格 4,5,6 - 即之间的索引4 和 7)
匹配失败。

第 4 步：
.*? = x - PASS（将字符添加到不情愿的量词'.*？'。单元格4。）
foo = xxx - FAIL（单元格5,6,7 - 即5和8之间的索引）
匹配失败。

第 5 步：
.*? = xx - PASS（将字符添加到不情愿的量词 '.*?'。单元格 4 到 5。）
foo = xxx - FAIL（单元格 6,7,8 - 即 6 和 9 之间的索引）
匹配失败。

第 6 步：
.*? = xxx - PASS（将字符添加到不情愿的量词 '.*?'。单元格 4 到 6。）
foo = xxx - FAIL（单元格 7,8,9 - 即 7 和 10 之间的索引）
匹配失败。

第 7 步：
.*? = xxxx - PASS（将字符添加到不情愿的量词'.*？'。单元格 4 到 7。）
foo = xxf - FAIL（单元格 8、9、10 - 即 8 和 11 之间的索引）
匹配失败。

第 8 步：
.*? = xxxxx - PASS（将字符添加到不情愿的量词'.*？'。单元格 4 到 8。）
foo = xfo - FAIL（单元格 9,10,11 - 即 9 和 12 之间的索引）
匹配失败。

第 9 步：
.*? = xxxxxx - PASS（将字符添加到不情愿的量词 '.*?'。单元格 4 到 9。）
foo = foo - PASS（单元格 10,11,12 - 即 10 和 13 之间的索引）
报告匹配

第 10 步：
.*? = '' (空白) - PASS (尽可能少匹配不情愿的量词'.*?'。索引 13 为空白。)
foo = 没有剩余字符可匹配 - FAIL (索引 13 后没有任何内容可匹配)
匹配失败的。

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

Possessive - 尽可能匹配所有格量词并匹配整个正则表达式。不要回溯。

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

上面的正则表达式有两个部分：'.*+' 和 'foo'。

第 1 步：
.*+ = xfooxxxxxxfoo - PASS（尽可能匹配所有格量词 '.*'）
foo = 没有剩余字符可匹配 - FAIL（索引 13 后无匹配）
匹配失败。

注意：不允许回溯。

结果： 0 场比赛

于 2015-02-04T00:28:58.050 回答
2

贪婪：“匹配最长的字符序列”

不情愿：“匹配最短的字符序列”

Possessive：这有点奇怪，因为它不会（与贪婪和不情愿相比）尝试为整个正则表达式找到匹配项。

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

于 2013-09-03T14:45:45.673 回答
0

贪婪量化涉及在迭代期间使用字符串的所有剩余未验证字符进行模式匹配。未经验证的字符以活动序列开始。每次不匹配时，最后的字符被隔离并再次执行检查。

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

字符流从活动序列进入隔离区。产生的行为是尽可能多的原始序列包含在匹配中。

勉强量化与贪婪量化基本相同，只是字符的流动是相反的——即它们从隔离区开始，流入活动序列。结果行为是尽可能少的原始序列包含在匹配中。

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

于 2015-09-27T07:09:56.480 回答