为什么贪心量词比懒惰量词更便宜
http://www.rexegg.com/regex-quantifiers.html#tempered_greed
贪婪量词(默认) - 通过吞咽尽可能多的字符来缓慢减少一个一个匹配的字符数量,以便为模式的其余部分让路.
例如,.*world针对字符串的正则表达式hello world将首先尝试吞下整个字符串并将其放入.*.但它不能,因为然后world无法匹配,所以.*开始逐个放弃字符,直到它放弃world原始字符串 - 在这种情况下整个正则表达式可以匹配.
懒惰的量词 - 以类似的方式工作,除了反向.他们希望匹配尽可能少的字符,并且他们做同样的事情,逐个添加更多字符,直到模式的其余部分有可能匹配
但是根据我读到的这篇文章,这些看似相同的贪婪和懒惰量词的过程是不同的 - 因为只有懒惰的量词才需要"回溯".但是,当吐出先前被吞噬的元素时,贪婪量词还不需要"回溯"吗？
为什么会这样？它看起来很直观
正确应用时,贪婪和懒惰的量词同样(昂贵).然而,懒惰的量词因为它们可以并且经常被应用来补偿模式中的不精确而得到了缓慢的声誉.
考虑一个简单的例子:<.*?>vs <.*>.
当两个表达式都应用于同一输入时
<abcdefghijklmnopqrstuvwxyz0123456789>
它们完全匹配相同的文本.不同之处仅在于它们如何到达匹配:"懒惰"表达式尝试越来越长的字符串,在40步之后到达匹配(演示1).另一方面,贪婪的表情一直持续到最后,只需5步就可以回溯一次到达比赛(演示2).
请注意,如果您在以下位置后添加更多字符,则可以撤消这种情况>:
<abcdefghijklmnopqrstuvwxyz0123456789>abcdefghijklmnopqrstuvwxyz0123456789abcdefghijklmnopqrstuvwxyz0123456789abcdefghijklmnopqrstuvwxyz0123456789
现在贪婪的表达成为"慢速",采取149步(演示3),而懒惰表达继续采取与之前相同的40步(演示4).