正则表达式贪婪解析方向

Question

我发现对于贪婪regex的执行方式有两种不同的观点：

• 一种是，读取所有输入字符串并从后面匹配模式，首先匹配整个输入，第一次尝试是整个字符串。支持这一观点的一些文章是Oracle offical Java tutorial：

Greedy quantifiers are considered "greedy" because they force the matcher to read in, or eat, the entire input string prior to attempting the first match. If the first match attempt (the entire input string) fails, the matcher backs off the input string by one character and tries again, repeating the process until a match is found or there are no more characters left to back off from.

另请参阅本文：Performance of Greedy vs. Lazy Regex Quantifiers

• 另一个是从前面匹配，第一个匹配尝试是从左边的0索引开始。当找到匹配项时，引擎不会停止，继续匹配其余项直到失败，然后它将返回。我发现支持这一观点的文章是：

Repetition with Star and PlusLooking Inside The Regex Engine部分讨论<.+>：

The first token in the regex is <. This is a literal. As we already know, the first place where it will match is the first < in the string.

我想知道哪一个是正确的？这很重要，因为它会影响regex的效率。我添加了各种语言标记，因为我想知道它在每种语言中的实现是否不同。在

Answer 1

regex在不同环境和编程语言中的实现不一定要相同，所以您的问题没有确切的答案。在

如果您使用Perl，那么您应该知道regex实现是非常优化的，因为这是这种编程语言最强大的特性之一。所以，不用担心效率：）

Answer 2

假设它们在功能上是等价的（根据我对Java regex的使用，它们是相同的），这只是引擎实现的不同。正则表达式在所有语言中的实现方式并不完全相同，根据所使用的语言的不同，正则表达式的功能可能会有所不同。在

第二个链接描述的是Perl，所以我相信Oracle在Java方面是可靠的。在

两者都试图得到最大的匹配。在

通过添加?键使量词变懒，将尝试尽可能的最小匹配。在

Answer 3

“matcher将输入字符串后退一个字符，然后再试一次”只是描述回溯，因此“then'llbacktrack”也是这么说的。既然你们两个关于贪婪的引语都说了同样的话，那两个都是正确的。（你的第三句话与贪婪无关。）

---

让我们举个例子。在

'xxabbbbbxxabbbbbbbbb' =~ /([ab]*)bb/;

1. 在位置0尝试。
   1. [ab]*匹配0个字符“”。
      1. 在位置0，bb无法匹配⇒回溯。在
   2. [ab]*无法匹配任何更少的⇒回溯。在
2. 在位置1尝试。
   1. [ab]*匹配0个字符“”。
      1. 在位置1，bb无法匹配⇒回溯。在
   2. [ab]*无法匹配任何更少的⇒回溯。在
3. 在2号位置试试。
   1. [ab]*匹配6个字符“abbbbb”。
      1. 在位置8，bb无法匹配⇒回溯。在
   2. [ab]*匹配5个字符“abbbb”。（退一步）
      1. 在位置7，bb无法匹配⇒回溯。在
   3. [ab]*匹配4个字符“abbb”。（退一步）
      1. 在位置6，bb匹配。
         1. 成功。在

所以1美元是“abbb”。（不是abbbbbbb。“贪婪”并不意味着“可能的最长匹配”。）

---

现在，让我们看看如果我们让“*”非贪婪会发生什么。在

^{pr2}$

1. 在位置0尝试。
   1. [ab]*?匹配0个字符“”。
      1. 在位置0，bb无法匹配⇒回溯。在
   2. [ab]*无法再匹配⇒回溯。在
2. 在位置1尝试。
   1. [ab]*?匹配0个字符“”。
      1. 在位置1，bb无法匹配⇒回溯。在
   2. ^{⇒任何回溯都无法匹配。在
3. 在2号位置试试。
   1. [ab]*?匹配0个字符“”。
      1. 在位置2，bb无法匹配⇒回溯。在
   2. [ab]*?匹配1个字符“a”。（添加一个）
      1. 在位置3，bb匹配。
         1. 成功。在

所以1美元是“a”。在

---

具体的实现作为一个优化可能会做不同的事情，只要它给出的结果与这里介绍的一样。您可以看到Perl使用

^{3}$