为什么正则表达式默认是贪婪模式？

Question

对于初学者编写正则表达式来说，这似乎是一个巨大的困惑源，可能会导致隐藏的性能问题，而典型的用例似乎应该是非贪婪的。

这只是出于传统原因（它最初是如此完成的，并且每个实现都复制了它），还是有其它原因呢？

- Yishai

---

谁投票将其关闭为主观和争论性，请详细说明一下？ - falstro

正则表达式默认情况下不贪婪，但它们的量词是贪婪的 :-) - Andy E

在我看来，真正的问题是，为什么懒惰匹配符比贪婪匹配符更难以使用和/或不太受支持？ - Ipsquiggle

这个问题也困扰着我，从逻辑上讲，创建一个懒惰的正则表达式引擎比贪婪的引擎更有效率和容易，他们应该将默认模式设置为懒惰，因为那是默认情况下所感知到的。此外，在我使用正则表达式的生活中，我不记得使用贪婪匹配的情况超过1%的时间。 - shabby

Answer 1

歇斯底里的干果

---

答案的一部分可能涉及正则表达式在实际计算中的起源。它们最初是从自动机理论和形式语言理论中的一个理论概念，直到Ken Thompson本人编写了真正的实现并在qed和ed(1)中使用它们。

最初版本只有贪婪语法，所以甚至没有需要做出的决定。

- DigitalRoss

---

我不确定理论上的正则语言默认是"贪婪"的说法是否正确。我认为Kleene正则表达式定义了所有可能匹配的字符串的集合，因此/x*/可以匹配""、"x"或"xxx"（等等）。这种表达式定义了一个包括""、"x"和"xxx"在内的正则语言。请注意，这并没有涉及如何在文本中搜索匹配项；只有当你应用这个理论时，你才会关心贪婪性。 - Nate C-K

当然，当我提到“原始版本”时，我只是指“Ken Thompson为那些编辑器键入的版本”，在那些版本中以及之后的近十年中，ed、grep、ex和vi仅执行贪婪模式匹配。 - DigitalRoss

啊，这样的话我们是达成一致了。 - Nate C-K

Answer 2

就性能而言，因为会回溯，懒惰量词并不总是更快： http://blog.stevenlevithan.com/archives/greedy-lazy-performance

至于实际设计，我真的不知道为什么量词默认是贪婪的，但我确实想知道使用哪个控制字符来使量词变得贪婪而不是懒惰。我认为 ? 不够用 :-)

- Andy E

---

@forefinger：那不是匹配字符串/行的结尾吗？ - Andy E

可以，它确实如此。它只是看起来像最好的贪婪符号。 - forefinger

Answer 3

可能的原因：如果正则表达式是非贪婪模式，那么正则引擎需要频繁地回溯。

- kennytm

---

@roe：是的，两种量词行为都可能需要回溯。 - Gumbo

Answer 4

在可能的情况下，计算机的行为应该是可预测的。因此，正确的行为应该遵循一个简单的规则，比如贪婪匹配，这样至少有经验的程序员可以预测代码的结果。

至于典型用例是否应该是非贪婪的，那么以下情况怎么办：假设我有一个条目类似于foo1909，bar3939，baz3331的文件，并且我只想提取这些数字。使用(\d*)作为正则表达式似乎很自然。

你可能会说写(\d*)\D或其他方式同样容易，但通常情况下程序员可以更明确、更少歧义。由于我们希望默认行为是100%可预测的，并且可以轻松地在头脑中计算，所以我认为这很合理。

- forefinger

---

这是一个完全合乎逻辑和合理的推测，但它与真正的原因没有太大关系，真正的原因很简单，那就是非贪婪模式出现得晚得多，所以它不是默认选项。 - DigitalRoss

Answer 5

这里真正的问题是 Kleene 闭包操作符（星号）；对于正则表达式中的其他所有内容，最长匹配与最短匹配相同。当你从这个角度考虑时，你会意识到更现代的工具需要同时支持两种匹配方式。我举两个例子：

- ksh 和 bash 都提供“最长匹配”和“最短匹配”形式的大多数特殊变量修改运算符。 - Lua 正则表达式中包括 * 用于 Kleene 闭包最长匹配和 - 用于 Kleene 闭包最短匹配。当我忘记转义字面上的 - 符号时，它总是让我很困扰。

回到 Kleene 的原始工作可能会有趣，看看它是否影响了早期工具的最长匹配方式。

- Norman Ramsey

---

关于替代方案呢？给定正则表达式 /foo|foobar/ 和目标字符串 blahfoobarblah，一个数学上纯粹的正则表达式总是匹配 foobar，而 Perl 派生的 NFA 正则表达式将会匹配 foo。 - Alan Moore

Answer 6

看起来典型的使用情况应该是非贪婪的。

我想澄清一点，除非“典型的使用情况”指的是HTML黑客技巧，否则这是错误的。

编程语言的词法分析器就是一个简单的例子。你根本不希望

foo = 42

被解释为3个变量，后跟等号，再后面是2个数字。相反地，通常你希望你的解析器考虑最长可能的匹配。

在HTML出现之前，我们这些老人已经用贪婪正则表达式生活了几十年，而且做得很好。即使今天，在99%的情况下我也不使用非贪婪正则表达式，承认因为我太懒去查找语法，但也因为很少有情况下你不能编写一个良好终止的贪婪正则表达式。例如，匹配字符串：

"(\\"|[^"])*"

- Ingo

---

我认为词法分析器从“查找某些内容”中获得的收益不大，同时还要确保其他所有内容都“不是某些内容”。当然，对于由单个符号分隔的字符串来说，这看起来还不错，但如果你尝试对其他由多个符号分隔的内容进行操作，比如多行注释：/\*((?!\*/).)*\*/与/\*.*?\*/相比，后者更加简洁。随着分隔符数量的增加，情况会变得更糟，因为您必须否定所有分隔符。贪婪匹配在大多数情况下都可以正常工作，因为这些问题并不经常出现，但声称它有利于词法分析或者说它是错误的... - TrisT