这个正则表达式不应该发生灾难性的回溯

2024-04-03

有人可以解释为什么 Java 的正则表达式引擎会在此正则表达式上进入灾难性的回溯模式吗？据我所知，每个交替都与其他每个交替相互排斥。

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

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

向某些交替添加所有格匹配可以解决问题，但我不知道为什么 - Java 的正则表达式库在互斥分支上回溯肯定非常错误。

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

EDIT:最后添加了 Java 版本——尽管它本质上很笨拙、不可读且不可维护。

¡不再有丑陋的图案！

The first你需要做的就是以一种可以被人类可读并因此可维护的方式编写您的正则表达式。 The second您需要做的就是分析它以查看它实际上在做什么。

这意味着至少你需要编译它Pattern.COMMENTS模式（或前缀"(?x)"），然后添加空白以提供一些视觉活动空间。据我所知，您实际尝试匹配的模式是这样的：

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

正如你所看到的，我在可能的地方引入了垂直和水平空白，以引导眼睛和思想作为一种认知分块。我还删除了所有无关的反斜杠。这些要么是彻底的错误，要么是混淆器，除了让读者感到困惑之外什么也不做。

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

完成此操作后，我终于可以看到，这里是一场以开始为基础的比赛，然后是三个选项的选择。因此，我用描述性注释标记了这三种替代方案，这样人们就不必猜测。

我还注意到您的第一个选择有两个略有不同的（否定的）方括号字符类。第二个缺少第一个中看到的单引号排除。这是故意的吗？即使是这样，我也发现这对我的口味来说太多重复了；其中部分或全部应该位于变量中，这样您就不会面临更新一致性问题的风险。

分析

您必须做的两件事中的第二件事也是更重要的事情是对此进行分析。您需要准确查看该模式被编译成哪个正则表达式程序，并且需要在它运行数据时跟踪其执行情况。

Java’s Patternclass 目前无法做到这一点，尽管我已经与 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。这就是我们在这里要做的，以避免源代码被黑客攻击。

正则表达式编译

The 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 处的指令是一个分支，如果它失败，则继续执行分支 26，另一个分支。第二个分支是正则表达式程序的唯一其他部分，由单个 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~:/"...

您看到那里发生的情况是，特里树快速分支到节点 55，这是三个替代方案中的最后一个after它与单引号匹配，因为您的目标字符串以单引号开头。就是这个：

  | ' (?: [^']+ | '' )+ '        # 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

节点 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~:/"...

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

EDIT

看来 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 中的模式匹配有很多值得讨论的地方，但绝对没有一个能通过那些满口脏话的警察。这简直是一件令人头疼的事。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)