regex - 分隔符之间的匹配文本：贪婪或惰性正则表达式？

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

大多数人在处理此类问题时没有考虑的是，当正则表达式无法找到匹配项时会发生什么。 那是最有可能出现杀手级性能漏洞的时候。例如，以 Tim 为例，您正在寻找类似<tag>Hello!. 考虑会发生什么：

<.*?>Hello!

正则表达式引擎找到 a<并很快找到关闭>，但不是>Hello!。所以.*?继续寻找后面跟着的a >。如果没有，它将在放弃之前一直走到文档的末尾。然后正则表达式引擎继续扫描，直到找到另一个，然后再试一次。 我们已经知道结果会如何，但是正则表达式引擎通常不知道；它与文档中的每个都经历了相同的繁琐。现在考虑另一个正则表达式：Hello!<<

<[^>]*>Hello!

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

但它甚至比这更糟糕。如果你仔细想想，.*?实际上相当于一个负前瞻。它的意思是“在使用下一个字符之前，确保正则表达式的其余部分不能在这个位置匹配。” 换句话说，

/<.*?>Hello!/

...相当于：

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

因此，在您执行的每个位置上，不仅仅是正常的匹配尝试，而是更昂贵的前瞻。（这至少是两倍的成本，因为前瞻必须扫描至少一个字符，然后.继续并消耗一个字符。）

（(*FAIL)是 Perl 的回溯控制动词之一（PHP 也支持）。 |\z(*FAIL)意思是“或到达文档末尾并放弃”。）

最后，否定字符类方法还有另一个优点。虽然它（正如@Bart 指出的那样）不像量词是所有格一样，但如果你的风格支持它，没有什么可以阻止你让它成为所有格：

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

...或将其包装在一个原子组中：

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

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