正则表达式: 谁更贪婪？

Question

我的主要关注点是Java语言，但我也希望获得有关其他语言的信息。

假设你有一个像这样的子模式：

(.*)(.*)

这并不是很有用，但我们假设这两个捕获组（假设为\1和\2）是较大模式的一部分，并与对这些组的回溯匹配等。

因此，两者都是贪婪的，即它们尽可能地捕获尽可能多的内容，在必要时才进行少量捕获。

我的问题是：谁更贪婪？\1优先获取，只有在必要时才给\2留下其份吗？

那么又该如何呢：

(.*)(.*)(.*)

假设\1首先获得优先权。 假设它变得太贪心，然后吐出一个字符。 谁会第一个得到它？总是\2还是可以是\3？

我们假设是\2获得了\1的拒绝。 如果这仍然不起作用，现在谁会吐出来？\2会吐给\3，还是\1首先要吐给\2另一个字符？

---

附加问题

如果您编写类似以下内容的东西，会发生什么：

(.*)(.*?)(.*)

现在\2不情愿了。这是否意味着\1对\3进行了拒绝，并且\2只是勉强地接受了\3的拒绝？

---

示例

也许我没有给出具体的示例来展示我如何使用这些模式是一个错误，但这里有一些示例：

System.out.println(
    "OhMyGod=MyMyMyOhGodOhGodOhGod"
    .replaceAll("^(.*)(.*)(.*)=(\\1|\\2|\\3)+$", "<$1><$2><$3>")
); // prints "<Oh><My><God>"

// same pattern, different input string
System.out.println(
    "OhMyGod=OhMyGodOhOhOh"
    .replaceAll("^(.*)(.*)(.*)=(\\1|\\2|\\3)+$", "<$1><$2><$3>")
); // prints "<Oh><MyGod><>"

// now \2 is reluctant
System.out.println(
    "OhMyGod=OhMyGodOhOhOh"
    .replaceAll("^(.*)(.*?)(.*)=(\\1|\\2|\\3)+$", "<$1><$2><$3>")
); // prints "<Oh><><MyGod>"

- polygenelubricants

Answer 1

\1 会被优先匹配，\2 和 \3 将总是匹配失败。然后 \2 会优先于 \3 进行匹配。

一般来说，回溯(back-tracking)只会出现在满足匹配的情况下，而不是满足贪婪性(greediness)，因此左边优先匹配 :)

解释回溯和贪婪性需要涉及太多内容，我建议阅读Friedl的《精通正则表达式》(Mastering Regular Expressions)。

- Paul Creasey

Answer 2

您提供的具体示例使问题的性质发生了巨大变化。它仍然像我在第一个答案中描述的那样开始，第一个(.*)匹配所有字符，第二个和第三个组让它们匹配，但接下来它必须匹配一个等号。

显然，在字符串末尾没有等号，因此第一组逐个字符地返回字符，直到正则表达式中的=与目标中的=匹配。然后，正则表达式引擎开始尝试匹配(\1|\2|\3)+$，真正有趣的事情开始了。

第一组放弃了d，第二组（仍为空）接管了它，但是正则表达式的其余部分仍无法匹配。第一组放弃了o，第二组匹配了od，但是正则表达式的其余部分仍无法匹配。如此往复，第三组也参与其中，他们以各种可能的方式切割输入，直到实现整体匹配。RegexBuddy报告需要13,426步才能到达目标。

在第一个示例中，贪婪（或不贪婪）并不是一个因素；只有当单词Oh，My和God分别被捕获时，才能实现匹配，所以最终就是这样发生的。哪个组捕获了哪个单词甚至都不重要--就像我之前说过的那样，先到先得。

在第二个和第三个示例中，只需要将前缀分成两个部分：Oh和MyGod。在第二个示例中，由于它紧挨着并且贪婪，因此第二组捕获了MyGod。在第三个示例中，每当第一组放弃一个字符时，第二组（不情愿）就让第三组接管，因此最终MyGod归第三组所有。

当然，这比那更加复杂（和乏味），但我希望这回答了您的问题。我必须说，您选择的目标字符串很有趣；如果正则表达式引擎可以有性高潮，我认为这些正则表达式将是带来高潮的那个。:D

- Alan Moore

---

“哪一组捕捉哪个单词其实并不重要”——这是我问题的核心。当有多个解决方案时，到底选择哪一个呢？是否有一个正则表达式规范来说明应该具体怎么做，如何明确优先级等等？另外，你提到了RegexBuddy和n-steps等，听起来几乎像是步进调试器，这将是很棒的。我会去研究一下。谢谢。 - polygenelubricants

哦，对了，我基本上把这些组想象成三只小鸡，它们在竞争吃东西、暴食和清洁等方面，直到希望达到和谐至极的高潮状态。这使得使用正则表达式比它本来就有趣的更加有趣。 - polygenelubricants

正则表达式并没有标准或规范，至少对于像 Java、Perl、Python、.NET 等采用 NFA 或 regex-directed 引擎的情况是这样。但是如果它们在相同的输入下产生不同的结果，我会感到惊讶。 - Alan Moore

Answer 3

量词默认情况下并不是贪婪的，它们只是匆忙地匹配。在你的例子中，第一个(.*)首先会尽可能地匹配所有内容，而不考虑正则表达式整体的需求。然后才把控制权交给下一个部分，如果需要的话，它会回溯并放弃刚刚匹配到的一些或全部内容，以便让正则表达式的其余部分工作。

在这种情况下这是不必要的，因为其他所有部分都可以合法地匹配零个字符。如果量词真的很贪婪，那么三个组将争抢，直到它们将输入尽可能平均地分割; 相反，第二个和第三个组就让第一个组保留它所取的内容。如果将 possessive 量词（即 (.*)(.*+)(.*+)）应用到它们身上，结果也是一样的。

使第二个点星变得不情愿不会改变任何事情，但是改变第一个点星会有所不同。不情愿的量词仅在必要时才开始匹配，然后将控制权移交给下一个部分。因此，在(.*?)(.*)(.*) 中，第一个组最初没有匹配任何内容，然后第二个组匹配了所有内容，第三个组则一路哭到家。

这里有一个额外的问题：你：如果将所有三个量词变得不情愿会发生什么？（提示：在 Java 中，这不仅是一个正则表达式问题，也是一个 API 问题。）

- Alan Moore

---

回复：对我来说，只要正则表达式无法匹配，\3 就必须开始吃东西，如果它吃饱了，那么 \3 就会把所有的东西都吐出来，\2 就会咬一口，然后 \3 再次开始吃东西，以此类推。 - polygenelubricants

如果您使用matches()，那是正确的，因为正则表达式在两端隐式地被锚定。但是find()方法不是这种情况，所以它匹配不到任何内容。 - Alan Moore

Answer 4

正则表达式按顺序工作，这意味着当Regex-evaluator无法再找到该组的解决方案时，它将离开该组，最终进行一些回溯，以使字符串适合下一个组。如果您执行此正则表达式，则会在第一组中评估所有字符，下一组中没有任何字符（问号也无关紧要）。

- Willem Van Onsem

---

回复：“你将在第一组中获得所有字符的评估，而在下一组中没有。”以及“（问号也无关紧要）”--我只是添加了一些例子来证明这两个声明都不正确。 - polygenelubricants

你没有正确处理这些组，我测试了以下正则表达式： String s = "Oh(MyGod"; System.out.println( s.replaceAll("^(\w+)(.)(.)$", "<$1><$2><$3>") ); 它返回了我期望的结果: "<Oh><(My god><>"。 你不需要显式地分配这些组，或者你至少做错了。 - Willem Van Onsem

Answer 5

作为一个简单的通用规则：最左边的量词胜出。因此，只要以下量词仅标识纯可选子模式（无论它们是否被设置为非贪婪模式），第一个量词就会占据所有权。

- Matteo Riva

---

“第一次全拿走” - 我只是添加了一个示例以表明这并不总是正确的。 - polygenelubricants

只有在将反向引用添加到模式中时，所有规则都会被放在实际匹配模式的更高需求之前。在您的原始消息中，没有反向引用，只有量词。 - Matteo Riva

您可以查看修订历史并注意到我总是说这些捕获组是子模式，以便稍后与反向引用一起使用，因为否则它没有太大用处等——但是您是对的，我的错误在于没有包含示例以使其更加明确。 - polygenelubricants