定界符之间的匹配文本：贪婪或懒惰正则表达式？

Question

针对匹配定界符（例如<和>）之间的文本的常见问题，有两种常用模式：

• 使用贪婪的 * 或 + 量词并采用形式为START [^END]* END 的表示方式，例如 <[^>]*>，或
• 使用懒惰的 *? 或 +? 量词并采用形式为START .*? END 的表示方式，例如 <.*?>。

是否有特殊理由支持其中一种而不是另一种？

- Heinzi

Answer 1

一些优点：

[^>]* ：

• 更具表现力。
• 无论是否启用 /s 标志，都可以捕获换行符。
• 被认为更快，因为引擎不必回溯查找成功的匹配（使用 [^>] 时，引擎不需要做任何选择——我们只提供了一种匹配模式来针对字符串进行匹配）。

.*?

• 没有 "代码重复" —— 结束字符只出现一次。
• 在结束定界符超过一个字符的情况下更简单。 （在这种情况下，字符类将无效。）一个常见的替代方法是 (?:(?!END).)* 。如果 END 定界符是另一个模式，则情况会变得更糟。

- Kobi

---

请注意，[^>]* 只有在其后面跟随否定类中的内容([^>]*> 在这种情况下)时才会不回溯(backtrack)。Kobi，我知道你知道并且可能意味着这一点，但我想确保其他人不认为[^>]*和[^>]*+(占有形式)是相同的。除此之外，答案很好！ - Bart Kiers

Answer 2

第一个更加明确，即它明确排除了结束分隔符作为匹配文本的一部分。这在第二种情况下不能保证（如果正则表达式被扩展以匹配不仅仅是此标记）。例如：如果您尝试使用<.*?>Hello！匹配<tag1><tag2>Hello！，则正则表达式将匹配。

<tag1><tag2>Hello!

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

<tag2>Hello!

- Tim Pietzcker

---

在某些情况下，勉强匹配可以匹配两个子字符串，而许多人期望它只匹配一个。不错的例子。 - Bart Kiers

+1，很棒的例子。这次真的很难选择一个答案，但我选择了Kobis，因为他列出了两个选项的优缺点。 - Heinzi

Answer 3

当处理这类问题时，大多数人忽略了正则表达式无法找到匹配项时会发生什么。这时候最容易出现性能瓶颈。例如，以Tim的示例为例，您正在查找类似于<tag>Hello！的内容。考虑以下情况：

<.*?>Hello!

正则表达式引擎找到一个<，然后快速找到一个闭合的>，但没有找到>Hello！。因此，.*？继续寻找后面跟着Hello！的>。如果没有找到，它将一直查找到文档末尾才会放弃。然后，正则表达式引擎恢复扫描，直到找到另一个<，然后再次尝试。我们已经知道结果如何，但是正则表达式引擎通常不知道；它会在文档中的每个<上进行相同的操作。现在考虑其他的正则表达式：

<[^>]*>Hello!

与之前一样，它会快速匹配从<到>，但无法匹配Hello！。它将回溯到<，然后退出并开始扫描另一个<。它仍然像第一个正则表达式一样检查每个<，但不会每次找到一个就搜索整个文档的结尾。

但事实上比这更糟糕。如果您考虑一下，.*？实际上等效于负向先行断言。它的意思是“在消耗下一个字符之前，请确保正则表达式的剩余部分无法在此位置匹配。”换句话说，

/<.*?>Hello!/

...等同于：

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

所以在每个位置上，你不仅要执行普通的匹配尝试，而且还要执行一个更昂贵的向前查找。（它至少要花费两倍的代价，因为向前查找必须扫描至少一个字符，然后.会继续消耗一个字符。）

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

最后，否定字符类方法还有另一个优点。虽然它不像@Bart指出的那样表现得像量词具有占有性，但如果您的语言支持，没有什么可以阻止您使其具有占有性：

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

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

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

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

- Alan Moore

---

好的回答。然而，这里一个相当重要的点是，将<.*?>Hello!与<[^>]*>Hello!进行比较并不太公平。在这种情况下，您的结束定界符实际上是>Hello!，而[^>]根本无法处理它。我试图在我的答案的最后一点中提到了这一点。 - Kobi

是的，将Hello！附加到原始正则表达式上，有效地将闭合分隔符从单个字符更改为多个字符序列。这会使.*？版本变成潜在的黑洞，而[^>]*版本仍然可以正常工作。我想说的是，在孤立状态下，两种风格之间实际上几乎没有什么可选择的；不过，如果正则表达式变得更加复杂，选择就变得至关重要了。 - Alan Moore