正则表达:谁更贪婪？

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

Answer 1

\1将具有优先权,\2并且\3将始终不匹配.\2然后优先考虑\3.

一般来说这样想,反向跟踪只会满足匹配,不会出现满足贪婪,所以留下最好:)

解释追溯跟踪和贪婪是我在这里要解决的问题,我建议使用Friedl的掌握正则表达式

Answer 2

添加具体示例会大大改变问题的本质.它仍然像我在第一个答案中描述的那样开始,首先(.*)吞噬所有角色,第二组和第三组让它拥有它们,但是它必须匹配等号.

显然字符串末尾没有一个字符串,因此组#1逐个返回字符,直到=正则表达式中的字符=与目标中的字符匹配.然后正则表达式引擎开始尝试匹配(\1|\2|\3)+$,真正的乐趣开始.

第1组放弃了d和第2组(仍然是空的)接受它,但其余的正则表达式仍然无法匹配.第1组放弃了第o2组和第2组匹配od,但正则表达式的其余部分仍然无法匹配.因此,随着第三组的参与,他们三人以各种可能的方式切换输入,直到实现整体匹配.据RegexBuddy报道,到达那里需要13426步.

在第一个例子中,贪婪(或缺乏贪婪)并不是真正的因素; 唯一可以实现匹配的方法是单词Oh,My并God在不同的组中捕获,所以最终会发生这种情况.甚至哪个群体捕获哪个词 - 这只是先到先得,正如我之前所说的那样.

在第二个和第三个例子中,只需要将前缀分成两个块:Oh和MyGod.第2组MyGod在第二个例子中捕获,因为它是下一个并且它是贪婪的,就像在第一个例子中一样.在第三个例子中,每当第1组丢弃一个角色时,第2组(不情愿)让第3组取而代之,这样就是最后拥有的那个MyGod.

当然,它比那更复杂(和乏味),但我希望这能回答你的问题.我不得不说,这是你选择的一个有趣的目标字符串; 如果一个正则表达式引擎有可能达到性高潮,我认为这些正则表达式将是它的关闭.:d