正则表达式:谁更贪婪?

2022-09-03 05:34:30

我主要关心的是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>"

答案 1

\1将具有优先级,并且始终不匹配任何内容。 然后,将优先于 。\2\3\2\3

作为一般规则,这样想,回溯只会为了满足比赛而发生,它不会为了满足贪婪而发生,所以左:)

解释回溯跟踪和贪婪对我来说是很多问题,我建议弗里德尔的掌握正则表达式


答案 2

添加您的具体示例会极大地改变问题的性质。它仍然像我在第一个答案中描述的那样开始,第一个吞噬了所有字符,第二组和第三组让它拥有它们,但随后它必须匹配一个等号。(.*)

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

组 1 放弃了,组 2(仍然是空的)接受它,但正则表达式的其余部分仍然无法匹配。第1组放弃了和第2组的比赛,但正则表达式的其余部分仍然无法匹配。事情就这样,第三组参与进来,他们三个人以各种可能的方式切分输入,直到实现整体匹配。RegexBuddy报告说,需要13,426个步骤才能到达那里。dood

在第一个例子中,贪婪(或缺乏贪婪)并不是一个真正的因素;实现匹配的唯一方法是将单词捕获在单独的组中,因此最终就是这样发生的。哪一组捕获哪个单词甚至无关紧要 - 正如我之前所说,这只是先到先得,先到先得。OhMyGod

在第二个和第三个示例中,只需将前缀分成两个块:和 。组 2 在第二个示例中捕获,因为它是下一行并且很贪婪,就像在第一个示例中一样。在第三个示例中,每次第 1 组删除一个字符,第 2 组(不情愿)让第 3 组代替它,所以这就是最终拥有的那个字符。OhMyGodMyGodMyGod

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