3

我发现关于如何执行贪婪的正则表达式有两种不同的看法：

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

贪婪量词被认为是“贪婪的”，因为它们强制匹配器在尝试第一次匹配之前读入或吃掉整个输入字符串。如果第一次匹配尝试（整个输入字符串）失败，匹配器将输入字符串回退一个字符并再次尝试，重复该过程直到找到匹配或没有更多字符可以回退。

另请参阅这篇文章：贪婪与惰性正则表达式量词的性能

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

与 Star 和 Plus的 重复Looking Inside The Regex Engine部分讨论<.+>：

正则表达式中的第一个标记是 <。这是字面意思。正如我们已经知道的，它将匹配的第一个位置是字符串中的第一个 <。

我想知道哪个是正确的？这很重要，因为它会影响正则表达式的效率。我添加了各种语言标签，因为我想知道每种语言的实现方式是否不同。

4

4 回答 4

3

假设它们在功能上是等效的（并且基于我的 Java 正则表达式使用，它们是），这只是引擎实现的不同。正则表达式在所有语言中的实现方式并不完全相同，并且根据您使用的语言可能或多或少地强大。

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

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

通过添加键使量词变得惰性?将尝试尽可能小的匹配。

于 2012-06-14T15:18:31.440 回答
0

在不同的环境和编程语言中实现正则表达式不必相同，因此您的问题没有确切的答案。

如果你使用Perl，那么你应该知道正则表达式的实现是非常优化的，因为这是这种编程语言最强大的特性之一。所以，不用担心效率:)

于 2012-06-14T15:25:26.123 回答
0

没有区别，也没有暗示“从背后匹配”。当第一个引用说“匹配器”时，它表示重复的正则表达式原子，而不是整个表达式 - 即当匹配/ab+/“方丈”时，我们不知道先验不会b+匹配整个字符串的其余部分。我认为 Java 教程可能正在讨论正则表达式匹配流的行为，并指出贪婪的重复会急切地消耗流的其余部分，而非贪婪的重复会根据需要懒惰地消耗流。

于 2012-06-14T15:41:35.850 回答
0

“匹配器将输入字符串回退一个字符并重试”只是描述回溯，因此“然后它会回溯”是说同样的事情。由于您关于贪婪的两个引述都说同样的话，因此两者都是正确的。（您的第三句话与贪婪无关。）

让我们举个例子。

'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。“贪婪”并不意味着“可能的最长匹配”。）

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

'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]*?匹配 0 个字符“”。
      1. 在位置 2，bb匹配失败⇒ 回溯。
    2. [ab]*?匹配 1 个字符“ a”。（添加一个）
      1. 在位置 3，bb匹配。
        1. 成功。

所以 1 美元是“a”。

特定的实现可能会以不同的方式进行优化，只要它给出的结果与此处显示的相同。你可以看到 Perl 在工作中使用

perl -Mre=debug -E'say "xxabbbbbxxabbbbbbbbb" =~ /([ab]*)bb/;'
perl -Mre=debug -E'say "xxabbbbbxxabbbbbbbbb" =~ /([ab]*?)bb/;'
于 2012-06-14T17:23:46.660 回答