regex - 为什么贪婪的量词比懒惰的量词便宜

Question

http://www.rexegg.com/regex-quantifiers.html#tempered_greed



贪婪的量词(默认值)-吞下允许的尽可能多的字符，然后再慢慢减少逐一匹配的字符数，以便为其余的模式腾出空间。

例如，针对字符串.*world的正则表达式hello world将首先尝试吞下整个字符串并将其放入.*中。但是它不能，因为那时world无法匹配，所以.*开始一个接一个地放弃字符，直到它放弃了原始字符串中的world为止(在这种情况下，整个正则表达式都可以匹配)。

懒惰的量词-以相似的方式工作，除了反向操作之外。他们想匹配的字符越少越好，他们做同样的事情，一个接一个地添加更多的字符，直到模式的其余部分有匹配的机会

但是根据我阅读的这篇文章，贪婪和懒惰量词的这些看似相同的过程是不同的-仅懒惰量词需要“回溯”。但是，在吐出先前吞咽的元素时，贪婪的量词也不需要“回溯”吗？

为什么会这样呢？看起来太直观了

Answer 1

贪婪和惰性的量词在正确应用时同样(便宜)。但是，懒惰的量词因其速度慢而享有盛誉，因为它们可以并且经常被用于补偿模式中的不精确性。

考虑一个简单的示例:<.*?>与<.*>。

当两个表达式都应用于相同的输入时

<abcdefghijklmnopqrstuvwxyz0123456789>

它们匹配完全相同的文本。区别仅在于它们到达比赛的方式:“惰性”表达式尝试越来越长的字符串，在40步后到达比赛( demo 1)。另一方面，贪婪的表达会一直进行到最后，只有5步( demo 2)后退一次即可到达比赛。

请注意，如果在 >之后添加更多字符，则情况可以逆转:

<abcdefghijklmnopqrstuvwxyz0123456789>abcdefghijklmnopqrstuvwxyz0123456789abcdefghijklmnopqrstuvwxyz0123456789abcdefghijklmnopqrstuvwxyz0123456789

现在，贪婪的表情变成了“慢速表情”，迈出了149个步骤( demo 3)，而懒惰的表情继续了与之前( demo 4)一样的40个步骤。