这个正则表达式不应该出现灾难性回溯

Question

这个正则表达式不应该出现灾难性回溯

3

有人能解释一下为什么Java的正则表达式引擎在这个正则表达式上进入了灾难性回溯模式吗？据我所知，每个替代项都与其他替代项互斥。

^(?:[^'\"\\s~:/@#\\|\\^\\&\\[\\]\\(\\)\\\\\\{\\}][^\"\\s~:/@#\\|\\^\\&\\[\\]\\(\\)\\\\\\{\\}]*|
\"(?:[^\"]+|\"\")+\"|
'(?:[^']+|'')+')

文本: 'pão de açúcar itaucard mastercard platinum SUSTENTABILIDADE])

在某些交替项中添加所有格匹配可解决问题，但我不知道为什么- Java的正则表达式库必须极其有缺陷才能在互斥分支上进行回溯。

 ^(?:[^'\"\\s~:/@#\\|\\^\\&\\[\\]\\(\\)\\\\\\{\\}][^\"\\s~:/@#\\|\\^\\&\\[\\]\\(\\)\\\\\\{\\}]*|
 \"(?:[^\"]++|\"\")++\"|
 '(?:[^']++|'')++')

- Lilith River

1

你尝试使用其他正则表达式引擎（Perl、Python或PHP）进行检查了吗？那个实现是否没有表现出这种行为？ - Bart Kiers

1

你的模式混乱了，首先。在某些地方你有太多反斜杠。如果 \" 是一个双引号字面值，那么 \\s 就是一个字面上的反斜杠后跟一个 s。此外，在字符类中你有不必要的额外反斜杠。 - tchrist

@tchrist：\" 和 \\s 在 Java 字符串字面量中很有意义，但我同意第一行大部分反斜杠根本不需要存在，更不用说重复输入了。 - Alan Moore

1

@Alan：天啊，那是一个字符串字面量而不是模式？太可怕了！我希望人们发布模式而不是这样的东西。他说它是正则表达式，但它不是。太糟糕了。任何需要我处理四个连续反斜杠的东西都是疯了。 - tchrist

1

@tchrist：一般来说，我认为最好将正则表达式发布为它们在实际源代码中出现的样子--例如，String regex = "[\"\\s\\\\]";。采用其他任何方法都会让某些人感到困惑，这是我观察到的情况。 - Alan Moore

显示剩余2条评论

3个回答

6

我必须承认这也让我感到惊讶，但是在RegexBuddy中我得到了相同的结果：它在一百万步后停止尝试。我知道有关灾难性回溯的警告往往集中在嵌套量词上，但根据我的经验，选择至少同样危险。实际上，如果我将您的正则表达式的最后一部分从此更改：

'(?:[^']+|'')+'

…变成这样：

'(?:[^']*(?:''[^']*)*)'

只需11个步骤就可以使其失效。这是“展开循环”技术的一个例子，其由 Friedl 提出，并分解如下：

opening normal * ( special normal * ) * closing
   '     [^']        ''     [^']           '

嵌套的星号只有在以下情况下才是安全的：

special 和 normal 永远不会匹配同一个字符，
special 总是至少匹配一个字符，且
special 是原子的（它必须只有一种匹配方式）。

正则表达式将以最小的回溯失败，而无需回溯即可成功匹配。另一方面，选择版本几乎肯定会回溯，在没有匹配的情况下，随着目标字符串长度的增加，它很快就会失控。如果在某些风格中它没有过度回溯，那是因为它们专门针对此问题构建了优化 - 到目前为止，很少有几种风格这样做。

- Alan Moore

一百万步，Alan？哦天啊。这比我的答案差了两个数量级。不知道出了什么问题；有什么想法吗？我猜这就是为什么你只能相信你实际使用的引擎结果的原因。 - tchrist

使用占有量词或原子组在那里会更好，而且失败得更快，不是吗？ - Qtax

我注意到RegexBuddy在分配“步骤”方面非常慷慨。例如，无论是[^']+还是(?:[^']+|'')+都会因吞掉初始 '后的所有内容而单独获得信用，然后有三个所谓的“回溯”步骤，然后它才会执行我认为的回溯操作。 - Alan Moore

@Qtax: 你是指除了展开循环以外的方法吗？可能只会快上一两步而已。顺便说一句，我并不是在说当存在所有权量词和/或原子组时应该使用这种技术。但是理解它的工作原理将永远有益于你。 - Alan Moore

我的天啊。Java版本真的比相同的Perl版本多花费了100倍的步骤。Perl版本完成得很慢，但Java版本似乎挂起了，所以它遭受了更严重的问题。我不知道为什么。我们永远不会知道，因为我们无法对其进行分析。唉。 - tchrist

当RegexBuddy的调试器显示“backtrack”时，它的意思是：“此标记未能匹配，现在我必须回溯”。调试器为每个量词的每次迭代显示一步，并且不以任何方式优化正则表达式的执行，因此新手可以轻松地跟踪发生的情况。您无法将调试器的步骤与另一种编程语言的步骤进行比较。但是，您可以比较调试器中两个不同正则表达式之间的步骤数以比较它们的复杂性。而'(?:[^']+|'')+'具有嵌套的量词。 - Jan Goyvaerts

0

有人能解释一下为什么Java的正则表达式引擎在这个正则表达式上进入了灾难性模式吗？

对于字符串：

'pão de açúcar itaucard mastercard platinum SUSTENTABILIDADE])

看起来正则表达式的这一部分可能是问题所在：

'(?:[^']+|'')+'

匹配第一个'，然后未能匹配闭合'，因此回溯所有嵌套量词的组合。

如果允许正则表达式回溯，则会回溯（失败时）。使用原子组和/或贪婪量词来防止这种情况发生。

顺便说一下，您在那个正则表达式中不需要大多数转义字符。在字符类（[]）中，您唯一需要转义的是字符 ^-]。但通常您可以将它们定位到不需要转义的位置。当然，\和您引用字符串的任何内容仍然需要（双重）转义。

"^(?:[^]['\"\\s~:/@#|^&(){}\\\\][^][\"\s~:/@#|^&(){}\\\\]*|\"(?:[^\"]++|\"\")++\"|'(?:[^']++|'')++')"

- Qtax

1

实际上，你仍然需要转义反斜杠，所以你必须有两个而不是一个。如果^是第一个字符，则只需要转义，如果-不是终止符（第一个或最后一个）则也需要转义。但这并不重要：我仍然认为那种模式完全难以阅读和维护。当人们写出那样的东西时，我真的很恼火。我知道你只是在模仿原始代码，但原始代码应该受到谴责而不是效仿。 - tchrist

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- tchrist · Accepted Answer

编辑：在结尾处添加了Java版本 - 尽管它本质上是笨拙的、难以阅读和难以维护的。

没有丑陋的模式！

你需要做的第一件事情是以一种易于人类阅读和维护的方式编写您的正则表达式。

你需要做的第二件事情是对其进行剖析，以查看它正在实际执行什么操作。

这意味着至少需要在Pattern.COMMENTS模式下编译它（或在前缀中加入"(?x)"），然后添加空格以提供一些可视化的空间。据我所知，你实际上要匹配的模式是这个：

^ 
(?: [^'"\s~:/@\#|^&\[\]()\\{}]    # alt 1: unquoted
    [^"\s~:/@\#|^&\[\]()\\{}] *
  | " (?: [^"]+ | "" )+ "        # alt 2: double quoted
  | ' (?: [^']+ | '' )+ '        # alt 3: single quoted
)

注意，我已经在可以的地方引入了垂直和水平的空白，以引导视线和思维作为某种认知分块。我还删除了所有多余的反斜杠。这些都是明显的错误或混淆读者的障碍物。

请注意，当应用垂直空白时，我使从一行到下一行相同的部分出现在同一列，以便您可以立即看到哪些部分是相同的，哪些部分是不同的。

做到这一点后，我最终可以看到你在这里匹配一个锚定到起始位置的模式，然后跟随三个备选项之一。因此，我用描述性注释标记了这三个备选项，这样就不必猜测。

我还注意到你的第一个备选项有两个微妙不同（否定的）方括号字符类。第二个缺少第一个中看到的单引号排除。这是有意的吗？即使是这样，我发现这种重复太多，不符合我的口味；其中一些或全部应该在变量中，这样就不会出现更新一致性问题。

性能分析

你必须完成的两件事中，第二件更为重要，即对其进行性能分析。你需要查看该模式编译成的确切正则表达式程序，并在运行数据时跟踪其执行。

Java的 Pattern 类目前还不能做到这一点，尽管我已经与OraSun的当前代码管理员详谈过这个问题，他非常希望将这种能力添加到Java中，并认为他知道如何做到。他甚至给我发送了一个原型，可以完成第一部分：编译。因此，我期望它会有一天可用。

同时，让我们转而使用一种工具，其中正则表达式是编程语言本身的一个组成部分，而不是作为笨拙附加的东西。虽然有几种语言符合这个标准，但在没有一种语言中，模式匹配艺术达到了Perl中所见到的复杂程度。

因此，这里是等效的程序。

#!/usr/bin/env perl
use v5.10;      # first release with possessive matches
use utf8;       # we have utf8 literals
use strict;     # require variable declarations, etc
use warnings;   # check for boneheadedness

my $match = qr{
    ^ (?: [^'"\s~:/@\#|^&\[\]()\\{}]
          [^"\s~:/@\#|^&\[\]()\\{}] *
        | " (?: [^"]+ | "" )+ "
        | ' (?: [^']+ | '' )+ '
    )
}x;

my $text = "'pão de açúcar itaucard mastercard platinum SUSTENTABILIDAD])";

my $count = 0;

while ($text =~ /$match/g) {
    print "Got it: $&\n";
    $count++;
}

if ($count == 0) {
    print "Match failed.\n";
}

如果我们运行该程序，则会得到预期的答案，即匹配失败。问题是为什么以及如何。

现在我们想要查看两件事情：我们想要看一下该模式编译成的正则表达式程序，然后跟踪该正则表达式程序的执行。

这两者都可以通过

控制。

use re "debug";

pragma可以通过-Mre=debug命令行指定。为避免在源代码上进行修改，我们将在此处使用它。

正则表达式编译

re调试指示通常会显示模式的编译和执行过程。为了分离这两个过程，我们可以使用Perl的“仅编译”开关-c，它不会尝试执行已编译的程序。这样我们只需查看编译后的模式即可。这将产生以下36行输出：

$ perl -c -Mre=debug /tmp/bt
Compiling REx "%n    ^ (?: [^'%"\s~:/@\#|^&\[\]()\\{}]%n          [^%"\s~:/"...
Final program:
   1: BOL (2)
   2: BRANCH (26)
   3:   ANYOF[^\x09\x0a\x0c\x0d "#&-)/:@[-\^{-~][^{unicode}+utf8::IsSpacePerl] (14)
  14:   STAR (79)
  15:     ANYOF[^\x09\x0a\x0c\x0d "#&()/:@[-\^{-~][^{unicode}+utf8::IsSpacePerl] (0)
  26: BRANCH (FAIL)
  27:   TRIE-EXACT["'] (79)
        <"> (29)
  29:     CURLYX[0] {1,32767} (49)
  31:       BRANCH (44)
  32:         PLUS (48)
  33:           ANYOF[\x00-!#-\xff][{unicode_all}] (0)
  44:       BRANCH (FAIL)
  45:         EXACT <""> (48)
  47:       TAIL (48)
  48:     WHILEM[1/2] (0)
  49:     NOTHING (50)
  50:     EXACT <"> (79)
        <'> (55)
  55:     CURLYX[0] {1,32767} (75)
  57:       BRANCH (70)
  58:         PLUS (74)
  59:           ANYOF[\x00-&(-\xff][{unicode_all}] (0)
  70:       BRANCH (FAIL)
  71:         EXACT <''> (74)
  73:       TAIL (74)
  74:     WHILEM[2/2] (0)
  75:     NOTHING (76)
  76:     EXACT <'> (79)
  78: TAIL (79)
  79: END (0)
anchored(BOL) minlen 1 
/tmp/bt syntax OK
Freeing REx: "%n    ^ (?: [^'%"\s~:/@\#|^&\[\]()\\{}]%n          [^%"\s~:/"...

如你所见，编译后的正则表达式程序有点像自己的“正则表达式汇编语言”。（它看起来非常像向我演示的Java原型所生成的内容，因此我想你们有朝一日也会在Java中看到这种东西。）这些细节对本文不是很重要，但我要指出节点2处的指令是BRANCH，如果失败，就会执行分支26，另一个BRANCH。那第二个BRANCH，也是正则表达式程序中唯一的其他部分，由单个TRIE-EXACT节点组成，因为它知道这些选项具有不同的起始文字字符串。我们将讨论这两个trie分支内部发生了什么。

正则表达式执行

现在是时候看看运行时会发生什么了。您使用的文本字符串会导致相当多的回溯，这意味着在最终失败之前，您需要浏览大量输出。输出量有多少？好吧，这么多：

$ perl -Mre=debug /tmp/bt 2>&1 | wc -l
9987

我假设你所说的“灾难性回溯模式”是指10,000个步骤。我们来看看能否将其简化为更容易理解的内容。你的输入字符串长度为61个字符。为了更好地了解发生了什么，我们可以将其缩减为仅包含'pão，这仅有4个字符。(嗯，在NFC中是这样的；在NFD中它是五个码点，但这里没有改变任何东西)。这会导致167行输出:

$ perl -Mre=debug /tmp/bt 2>&1 | wc -l
167

事实上，当您的字符串长度为此时，您将获得正则表达式（编译加执行）性能分析的行：

chars   lines   string
    1     63   ‹'›
    2     78   ‹'p›  
    3    109   ‹'pã›
    4    167   ‹'pão› 
    5    290   ‹'pão ›
    6    389   ‹'pão d›
    7    487   ‹'pão de›
    8    546   ‹'pão de ›
    9    615   ‹'pão de a›
   10    722   ‹'pão de aç›
  ....
   61   9987   ‹'pão de açúcar itaucard mastercard platinum SUSTENTABILIDAD])›

现在让我们看一下当字符串为四个字符'pão时的调试输出。这次我省略了编译部分，只显示执行部分：

$ perl -Mre=debug /tmp/bt
Matching REx "%n    ^ (?: [^'%"\s~:/@\#|^&\[\]()\\{}]%n          [^%"\s~:/"... against "'p%x{e3}o"
UTF-8 string...
   0 <> <'p%x{e3}o>  |  1:BOL(2)
   0 <> <'p%x{e3}o>  |  2:BRANCH(26)
   0 <> <'p%x{e3}o>  |  3:  ANYOF[^\x09\x0a\x0c\x0d "#&-)/:@[-\^{-~][^{unicode}+utf8::IsSpacePerl](14)
                            failed...
   0 <> <'p%x{e3}o>  | 26:BRANCH(78)
   0 <> <'p%x{e3}o>  | 27:  TRIE-EXACT["'](79)
   0 <> <'p%x{e3}o>  |      State:    1 Accepted: N Charid:  2 CP:  27 After State:    3
   1 <'> <p%x{e3}o>  |      State:    3 Accepted: Y Charid:  0 CP:   0 After State:    0
                            got 1 possible matches
                            TRIE matched word #2, continuing
                            only one match left, short-circuiting: #2 <'>
   1 <'> <p%x{e3}o>  | 55:  CURLYX[0] {1,32767}(75)
   1 <'> <p%x{e3}o>  | 74:    WHILEM[2/2](0)
                              whilem: matched 0 out of 1..32767
   1 <'> <p%x{e3}o>  | 57:      BRANCH(70)   1 <'> <p%x{e3}o>          | 58:        PLUS(74)
                                  ANYOF[\x00-&(-\xff][{unicode_all}] can match 3 times out of 2147483647...
   5 <'p%x{e3}o> <>  | 74:          WHILEM[2/2](0)
                                    whilem: matched 1 out of 1..32767
   5 <'p%x{e3}o> <>  | 57:            BRANCH(70)
   5 <'p%x{e3}o> <>  | 58:              PLUS(74)
                                        ANYOF[\x00-&(-\xff][{unicode_all}] can match 0 times out of 2147483647...
                                        failed...
   5 <'p%x{e3}o> <>  | 70:            BRANCH(73)
   5 <'p%x{e3}o> <>  | 71:              EXACT <''>(74)
                                        failed...
                                      BRANCH failed...
                                    whilem: failed, trying continuation...
   5 <'p%x{e3}o> <>  | 75:            NOTHING(76)
   5 <'p%x{e3}o> <>  | 76:            EXACT <'>(79)
                                      failed...
                                    failed...
   4 <'p%x{e3}> <o>  | 74:          WHILEM[2/2](0)
                                    whilem: matched 1 out of 1..32767
   4 <'p%x{e3}> <o>  | 57:            BRANCH(70)
   4 <'p%x{e3}> <o>  | 58:              PLUS(74)
                                        ANYOF[\x00-&(-\xff][{unicode_all}] can match 1 times out of 2147483647...
   5 <'p%x{e3}o> <>  | 74:                WHILEM[2/2](0)
                                          whilem: matched 2 out of 1..32767
   5 <'p%x{e3}o> <>  | 57:                  BRANCH(70)
   5 <'p%x{e3}o> <>  | 58:                    PLUS(74)
                                              ANYOF[\x00-&(-\xff][{unicode_all}] can match 0 times out of 2147483647...
                                              failed...
   5 <'p%x{e3}o> <>  | 70:                  BRANCH(73)
   5 <'p%x{e3}o> <>  | 71:                    EXACT <''>(74)
                                              failed...
                                            BRANCH failed...
                                          whilem: failed, trying continuation...
   5 <'p%x{e3}o> <>  | 75:                  NOTHING(76)
   5 <'p%x{e3}o> <>  | 76:                  EXACT <'>(79)
                                            failed...
                                          failed...
                                        failed...
   4 <'p%x{e3}> <o>  | 70:            BRANCH(73)
   4 <'p%x{e3}> <o>  | 71:              EXACT <''>(74)
                                        failed...
                                      BRANCH failed...
                                    whilem: failed, trying continuation...
   4 <'p%x{e3}> <o>  | 75:            NOTHING(76)
   4 <'p%x{e3}> <o>  | 76:            EXACT <'>(79)
                                      failed...
                                    failed...
   2 <'p> <%x{e3}o>  | 74:          WHILEM[2/2](0)
                                    whilem: matched 1 out of 1..32767
   2 <'p> <%x{e3}o>  | 57:            BRANCH(70)
   2 <'p> <%x{e3}o>  | 58:              PLUS(74)
                                        ANYOF[\x00-&(-\xff][{unicode_all}] can match 2 times out of 2147483647...
   5 <'p%x{e3}o> <>  | 74:                WHILEM[2/2](0)
                                          whilem: matched 2 out of 1..32767
   5 <'p%x{e3}o> <>  | 57:                  BRANCH(70)
   5 <'p%x{e3}o> <>  | 58:                    PLUS(74)
                                              ANYOF[\x00-&(-\xff][{unicode_all}] can match 0 times out of 2147483647...
                                              failed...
   5 <'p%x{e3}o> <>  | 70:                  BRANCH(73)
   5 <'p%x{e3}o> <>  | 71:                    EXACT <''>(74)
                                              failed...
                                            BRANCH failed...
                                          whilem: failed, trying continuation...
   5 <'p%x{e3}o> <>  | 75:                  NOTHING(76)
   5 <'p%x{e3}o> <>  | 76:                  EXACT <'>(79)
                                            failed...
                                          failed...
   4 <'p%x{e3}> <o>  | 74:                WHILEM[2/2](0)
                                          whilem: matched 2 out of 1..32767
   4 <'p%x{e3}> <o>  | 57:                  BRANCH(70)
   4 <'p%x{e3}> <o>  | 58:                    PLUS(74)
                                              ANYOF[\x00-&(-\xff][{unicode_all}] can match 1 times out of 2147483647...
   5 <'p%x{e3}o> <>  | 74:                      WHILEM[2/2](0)
                                                whilem: matched 3 out of 1..32767
   5 <'p%x{e3}o> <>  | 57:                        BRANCH(70)
   5 <'p%x{e3}o> <>  | 58:                          PLUS(74)
                                                    ANYOF[\x00-&(-\xff][{unicode_all}] can match 0 times out of 2147483647.
..
                                                    failed...
   5 <'p%x{e3}o> <>  | 70:                        BRANCH(73)
   5 <'p%x{e3}o> <>  | 71:                          EXACT <''>(74)
                                                    failed...
                                                  BRANCH failed...
                                                whilem: failed, trying continuation...
   5 <'p%x{e3}o> <>  | 75:                        NOTHING(76)
   5 <'p%x{e3}o> <>  | 76:                        EXACT <'>(79)
                                                  failed...
                                                failed...
                                              failed...
   4 <'p%x{e3}> <o>  | 70:                  BRANCH(73)
   4 <'p%x{e3}> <o>  | 71:                    EXACT <''>(74)
                                              failed...
                                            BRANCH failed...
                                          whilem: failed, trying continuation...
   4 <'p%x{e3}> <o>  | 75:                  NOTHING(76)
   4 <'p%x{e3}> <o>  | 76:                  EXACT <'>(79)
                                            failed...
                                          failed...
                                        failed...
   2 <'p> <%x{e3}o>  | 70:            BRANCH(73)
   2 <'p> <%x{e3}o>  | 71:              EXACT <''>(74)
                                        failed...
                                      BRANCH failed...
                                    whilem: failed, trying continuation...
   2 <'p> <%x{e3}o>  | 75:            NOTHING(76)
   2 <'p> <%x{e3}o>  | 76:            EXACT <'>(79)
                                      failed...
                                    failed...
                                  failed...
   1 <'> <p%x{e3}o>  | 70:      BRANCH(73)
   1 <'> <p%x{e3}o>  | 71:        EXACT <''>(74)
                                  failed...
                                BRANCH failed...
                              failed...
                            failed...
                          BRANCH failed...
Match failed
Match failed.
Freeing REx: "%n    ^ (?: [^'%"\s~:/@\#|^&\[\]()\\{}]%n          [^%"\s~:/"...

你看到的是trie树快速分支到节点55，这是您三个备选项中最后一个。在匹配到单引号后，由于目标字符串以单引号开头，trie树最终会匹配到该节点。

  | ' (?: [^']+ | '' )+ '        # alt 3: single quoted

节点55是此Trie分支：

        <'> (55)
  55:     CURLYX[0] {1,32767} (75)
  57:       BRANCH (70)
  58:         PLUS (74)
  59:           ANYOF[\x00-&(-\xff][{unicode_all}] (0)
  70:       BRANCH (FAIL)
  71:         EXACT <''> (74)

以下是执行跟踪，显示您的灾难性退避发生的位置：

   1 <'> <p%x{e3}o>  | 74:    WHILEM[2/2](0)
                              whilem: matched 0 out of 1..32767
   1 <'> <p%x{e3}o>  | 57:      BRANCH(70)
   1 <'> <p%x{e3}o>  | 58:        PLUS(74)
                                  ANYOF[\x00-&(-\xff][{unicode_all}] can match 3 times out of 2147483647...
   5 <'p%x{e3}o> <>  | 74:          WHILEM[2/2](0)
                                    whilem: matched 1 out of 1..32767
   5 <'p%x{e3}o> <>  | 57:            BRANCH(70)
   5 <'p%x{e3}o> <>  | 58:              PLUS(74)
                                        ANYOF[\x00-&(-\xff][{unicode_all}] can match 0 times out of 2147483647...
                                        failed...
   5 <'p%x{e3}o> <>  | 70:            BRANCH(73)
   5 <'p%x{e3}o> <>  | 71:              EXACT <''>(74)
                                        failed...
                                      BRANCH failed...
                                    whilem: failed, trying continuation...
   5 <'p%x{e3}o> <>  | 75:            NOTHING(76)
   5 <'p%x{e3}o> <>  | 76:            EXACT <'>(79)
                                      failed...
                                    failed...
   4 <'p%x{e3}> <o>  | 74:          WHILEM[2/2](0)
                                    whilem: matched 1 out of 1..32767
   4 <'p%x{e3}> <o>  | 57:            BRANCH(70)
   4 <'p%x{e3}> <o>  | 58:              PLUS(74)
                                        ANYOF[\x00-&(-\xff][{unicode_all}] can match 1 times out of 2147483647...
   5 <'p%x{e3}o> <>  | 74:                WHILEM[2/2](0)
                                          whilem: matched 2 out of 1..32767

Node 58吞掉了字符串中剩余的3个字符“pão”，导致单引号终止精确匹配失败。因此，它尝试使用替代方案，即一对单引号，但也失败了。在这一点上，我必须质疑你的模式。是否应该

' (?: [^']+ | '' )+ '

这真的可以这么简单吗？

' [^']* '

所发生的情况是，有很多方法可以通过回溯寻找逻辑上永远不可能出现的事情。您有一个嵌套量词，并且这会导致各种无望和毫无意义的繁忙工作。

如果我们将模式简化为以下内容：

^ (?: [^'"\s~:/@\#|^&\[\]()\\{}] +
    | " [^"]* "
    | ' [^']* '
  )

现在它输出的跟踪信息行数不管输入字符串的大小都是相同的：只有40行，这还包括编译过程。请看完整字符串的编译和执行过程：

Compiling REx "%n    ^ (?: [^'%"\s~:/@\#|^&\[\]()\\{}]%n          [^%"\s~:/"...
Final program:
   1: BOL (2)
   2: BRANCH (26)
   3:   ANYOF[^\x09\x0a\x0c\x0d "#&-)/:@[-\^{-~][^{unicode}+utf8::IsSpacePerl] (14)
  14:   STAR (61)
  15:     ANYOF[^\x09\x0a\x0c\x0d "#&()/:@[-\^{-~][^{unicode}+utf8::IsSpacePerl] (0)
  26: BRANCH (FAIL)
  27:   TRIE-EXACT["'] (61)
        <"> (29)
  29:     STAR (41)
  30:       ANYOF[\x00-!#-\xff][{unicode_all}] (0)
  41:     EXACT <"> (61)
        <'> (46)
  46:     STAR (58)
  47:       ANYOF[\x00-&(-\xff][{unicode_all}] (0)
  58:     EXACT <'> (61)
  60: TAIL (61)
  61: END (0)
anchored(BOL) minlen 1 
Matching REx "%n    ^ (?: [^'%"\s~:/@\#|^&\[\]()\\{}]%n          [^%"\s~:/"... against "'p%x{e3}o de a%x{e7}%x{fa}car itaucard mast
ercard platinum S"...
UTF-8 string...
   0 <> <'p%x{e3}o >  |  1:BOL(2)
   0 <> <'p%x{e3}o >  |  2:BRANCH(26)
   0 <> <'p%x{e3}o >  |  3:  ANYOF[^\x09\x0a\x0c\x0d "#&-)/:@[-\^{-~][^{unicode}+utf8::IsSpacePerl](14)
                             failed...
   0 <> <'p%x{e3}o >  | 26:BRANCH(60)
   0 <> <'p%x{e3}o >  | 27:  TRIE-EXACT["'](61)
   0 <> <'p%x{e3}o >  |      State:    1 Accepted: N Charid:  2 CP:  27 After State:    3
   1 <'> <p%x{e3}o d> |      State:    3 Accepted: Y Charid:  0 CP:   0 After State:    0
                             got 1 possible matches
                             TRIE matched word #2, continuing
                             only one match left, short-circuiting: #2 <'>
   1 <'> <p%x{e3}o d> | 46:  STAR(58)
                             ANYOF[\x00-&(-\xff][{unicode_all}] can match 60 times out of 2147483647...
                             failed...
                           BRANCH failed...
Match failed
Match failed.
Freeing REx: "%n    ^ (?: [^'%"\s~:/@\#|^&\[\]()\\{}]%n          [^%"\s~:/"...

我知道你可能认为使用所有格匹配可能是解决方案，但我认为问题实际上在于原始模式中的错误逻辑。现在看看这个更加明智的运行方式。

如果我们使用旧模式上的你的所有格匹配，即使我认为那没有意义，我们仍然会得到恒定的运行时间，但需要更多步骤。使用这个模式：

   ^ (?: [^'"\s~:/@\#|^&\[\]()\\{}] +    # alt 1: unquoted
       | " (?: [^"]++ | "" )++ "        # alt 2: double quoted
       | ' (?: [^']++ | '' )++ '        # alt 3: single quoted
     )

编译和执行的过程如下：

Compiling REx "%n    ^ (?: [^'%"\s~:/@\#|^&\[\]()\\{}]%n          [^%"\s~:/"...
Final program:
   1: BOL (2)
   2: BRANCH (26)
   3:   ANYOF[^\x09\x0a\x0c\x0d "#&-)/:@[-\^{-~][^{unicode}+utf8::IsSpacePerl] (14)
  14:   STAR (95)
  15:     ANYOF[^\x09\x0a\x0c\x0d "#&()/:@[-\^{-~][^{unicode}+utf8::IsSpacePerl] (0)
  26: BRANCH (FAIL)
  27:   TRIE-EXACT["'] (95)
        <"> (29)
  29:     SUSPEND (58)
  31:       CURLYX[0] {1,32767} (55)
  33:         BRANCH (50)
  34:           SUSPEND (54)
  36:             PLUS (48)
  37:               ANYOF[\x00-!#-\xff][{unicode_all}] (0)
  48:             SUCCEED (0)
  49:           TAIL (53)
  50:         BRANCH (FAIL)
  51:           EXACT <""> (54)
  53:         TAIL (54)
  54:       WHILEM[1/2] (0)
  55:       NOTHING (56)
  56:       SUCCEED (0)
  57:     TAIL (58)
  58:     EXACT <"> (95)
        <'> (63)
  63:     SUSPEND (92)
  65:       CURLYX[0] {1,32767} (89)
  67:         BRANCH (84)
  68:           SUSPEND (88)
  70:             PLUS (82)
  71:               ANYOF[\x00-&(-\xff][{unicode_all}] (0)
  82:             SUCCEED (0)
  83:           TAIL (87)
  84:         BRANCH (FAIL)
  85:           EXACT <''> (88)
  87:         TAIL (88)
  88:       WHILEM[2/2] (0)
  89:       NOTHING (90)
  90:       SUCCEED (0)
  91:     TAIL (92)
  92:     EXACT <'> (95)
  94: TAIL (95)
  95: END (0)
anchored(BOL) minlen 1 
Matching REx "%n    ^ (?: [^'%"\s~:/@\#|^&\[\]()\\{}]%n          [^%"\s~:/"... against "'p%x{e3}o de a%x{e7}%x{fa}car itaucard mastercard platinum S"...
UTF-8 string...
   0 <> <'p%x{e3}o > |  1:BOL(2)
   0 <> <'p%x{e3}o > |  2:BRANCH(26)
   0 <> <'p%x{e3}o > |  3:  ANYOF[^\x09\x0a\x0c\x0d "#&-)/:@[-\^{-~][^{unicode}+utf8::IsSpacePerl](14)
                            failed...
   0 <> <'p%x{e3}o > | 26:BRANCH(94)
   0 <> <'p%x{e3}o > | 27:  TRIE-EXACT["'](95)
   0 <> <'p%x{e3}o > |      State:    1 Accepted: N Charid:  2 CP:  27 After State:    3
   1 <'> <p%x{e3}o d>|      State:    3 Accepted: Y Charid:  0 CP:   0 After State:    0
                            got 1 possible matches
                            TRIE matched word #2, continuing
                            only one match left, short-circuiting: #2 <'>
   1 <'> <p%x{e3}o d>| 63:  SUSPEND(92)
   1 <'> <p%x{e3}o d>| 65:    CURLYX[0] {1,32767}(89)
   1 <'> <p%x{e3}o d>| 88:      WHILEM[2/2](0)
                                whilem: matched 0 out of 1..32767
   1 <'> <p%x{e3}o d>| 67:        BRANCH(84)
   1 <'> <p%x{e3}o d>| 68:          SUSPEND(88)
   1 <'> <p%x{e3}o d>| 70:            PLUS(82)
                                      ANYOF[\x00-&(-\xff][{unicode_all}] can match 60 times out of 2147483647...
  64 <NTABILIDAD])> <| 82:              SUCCEED(0)
                                        subpattern success...
  64 <NTABILIDAD])> <| 88:          WHILEM[2/2](0)
                                    whilem: matched 1 out of 1..32767
  64 <NTABILIDAD])> <| 67:            BRANCH(84)
  64 <NTABILIDAD])> <| 68:              SUSPEND(88)
  64 <NTABILIDAD])> <| 70:                PLUS(82)
                                          ANYOF[\x00-&(-\xff][{unicode_all}] can match 0 times out of 2147483647...
                                          failed...
                                        failed...
  64 <NTABILIDAD])> <| 84:            BRANCH(87)
  64 <NTABILIDAD])> <| 85:              EXACT <''>(88)
                                        failed...
                                      BRANCH failed...
                                    whilem: failed, trying continuation...
  64 <NTABILIDAD])> <| 89:            NOTHING(90)
  64 <NTABILIDAD])> <| 90:            SUCCEED(0)
                                      subpattern success...
  64 <NTABILIDAD])> <| 92:  EXACT <'>(95)
                failed...
              BRANCH failed...
Match failed
Match failed.
Freeing REx: "%n    ^ (?: [^'%"\s~:/@\#|^&\[\]()\\{}]%n          [^%"\s~:/"...

我仍然更喜欢我的解决方案。它更简短。

编辑

看起来Java版本的执行步骤真的比完全相同的Perl版本多100倍，而我不知道为什么——除了Perl正则表达式编译器比Java正则表达式编译器聪明大约100倍之外，后者几乎没有进行任何优化，但应该有。

这是等效的Java程序。我已删除了前导锚点，以便我们可以正确循环。

$ cat java.crap
import java.util.regex.*;

public class crap {

public static void
main(String[ ] argv) {
    String input = "'pão de açúcar itaucard mastercard platinum SUSTENTABILIDAD])";
    String regex = "\n"
                + "(?: [^'\"\\s~:/@\\#|^&\\[\\]()\\\\{}]    # alt 1: unquoted         \n"
                + "    [^\"\\s~:/@\\#|^&\\[\\]()\\\\{}] *                     \n"
                + "  | \" (?: [^\"]++ | \"\" )++ \"       # alt 2: double quoted   \n"
                + "  | ' (?: [^']++ | '' )++ '       # alt 3: single quoted   \n"
                + ")                                                          \n"
                ;
    System.out.printf("Matching ‹%s› =~ qr{%s}x\n\n", input, regex);

    Pattern regcomp = Pattern.compile(regex, Pattern.COMMENTS);
    Matcher regexec = regcomp.matcher(input);

    int count;
    for (count = 0; regexec.find(); count++) {
       System.out.printf("Found match: ‹%s›\n", regexec.group());
    }
    if (count == 0) {
        System.out.printf("Match failed.\n");
    }
  }
}

运行时，会产生以下内容：

$ javac -encoding UTF-8 crap.java && java -Dfile.encoding=UTF-8 crap
Matching ‹'pão de açúcar itaucard mastercard platinum SUSTENTABILIDAD])› =~ qr{
(?: [^'"\s~:/@\#|^&\[\]()\\{}]    # alt 1: unquoted         
    [^"\s~:/@\#|^&\[\]()\\{}] *                     
  | " (?: [^"]++ | "" )++ "       # alt 2: double quoted   
  | ' (?: [^']++ | '' )++ '       # alt 3: single quoted   
)                                                          
}x

Found match: ‹pão›
Found match: ‹de›
Found match: ‹açúcar›
Found match: ‹itaucard›
Found match: ‹mastercard›
Found match: ‹platinum›
Found match: ‹SUSTENTABILIDAD›

正如你明显所见，在Java中进行模式匹配是有很多需要谈论的地方，而且其中绝对没有一个能通过下流语言审查。这简直让人头疼。