在分隔符之间匹配文本:贪婪或懒惰的正则表达式？

Question

对于在分隔符(例如<和>)之间匹配文本的常见问题,有两种常见的模式:

• 使用形式中的贪婪*或+量词START [^END]* END,例如<[^>]*>,或
• 使用形式中的惰性*?或+?量词START .*? END,例如<.*?>.

是否有一个特别的理由支持一个而不是另一个？

Answer 1

一些优点:

[^>]*:

• 更具表现力.
• 无论/s旗帜如何,都可以捕获换行符.
• 考虑得更快,因为引擎不必回溯以找到成功的匹配([^>]引擎不做出选择 - 我们只给出一种方法来匹配模式与字符串).

.*?

• 没有"代码重复" - 结束字符只出现一次.
• 在结束定界符超过字符长度的情况下更简单.(在这种情况下,一个字符类不起作用)一个常见的替代方案是(?:(?!END).)*.如果END定界符是另一种模式,则更糟糕.

Answer 2

第一个是更明确的,即它肯定会将结束分隔符排除在匹配文本的一部分之外.在第二种情况下不保证这一点(如果正则表达式被扩展为不仅仅匹配此标记).

例如:如果你尝试匹配<tag1><tag2>Hello!用<.*?>Hello!,正则表达式匹配

<tag1><tag2>Hello!

而<[^>]*>Hello!将匹配

<tag2>Hello!

Answer 3

大多数人在接近这样的问题时未能考虑的是正则表达式无法找到匹配时会发生什么. 那时杀手性能下沉最有可能出现.例如,以蒂姆的例子为例,你正在寻找类似的东西<tag>Hello!.考虑一下会发生什么:

<.*?>Hello!

正则表达式引擎找到一个<并且很快找到结束>,但不是>Hello!.因此,.*?继续寻找>那是其次Hello!.如果没有,它会在文件放弃之前一直到文档的末尾.然后正则表达式引擎继续扫描,直到找到另一个<,然后再次尝试. 我们已经知道结果如何,但通常情况下,正则表达式引擎不会; 它与<文档中的每一个都经历了相同的繁琐.现在考虑另一个正则表达式:

<[^>]*>Hello!

和以前一样,它很快从匹配<的>,但不能匹配Hello!.它将回溯到<,然后退出并开始扫描另一个<.它仍然会<像第一个正则表达式那样检查每一个,但是每次找到它时它都不会一直搜索到文档的末尾.

但它甚至比这更糟糕.如果你考虑一下,.*?实际上相当于一个消极的先行.它说"在使用下一个字符之前,请确保正则表达式的其余部分在此位置不匹配." 换一种说法,

/<.*?>Hello!/

......相当于:

/<(?:(?!>Hello!).)*(?:>Hello!|\z(*FAIL))/

因此,在您执行的每个位置,不仅仅是正常的匹配尝试,而是更昂贵的前瞻.(它至少要贵两倍,因为前瞻必须扫描至少一个角色,然后.继续前进并消耗一个角色.)

((*FAIL)是Perl的回溯控制动词之一(在PHP中也支持). |\z(*FAIL)表示"或到达文档的末尾并放弃".)

最后,否定字符类方法还有另一个优点.虽然它没有(正如@Bart指出的那样)量词就像占有欲一样,如果你的味道支持它,没有什么可以阻止你使它占有欲:

/<[^>]*+>Hello!/

...或将其包装在原子组中:

/(?><[^>]*>)Hello!/

这些正则表达式不仅不会不必要地回溯,它们不必保存使回溯成为可能的状态信息.