regex - 最新的 Perl 不会匹配某些长度超过 32768 个字符的正则表达式

Question

我希望一些 Perl 大师可以对以下内容发表意见。这是我能找到的最小的示例，它重现了我的问题:

>./perl -e 'print (("a".("f"x32767)."a") =~ /a(?:[^a]|bb)*a/)'
1

但

>./perl -e 'print (("a".("f"x32768)."a") =~ /a(?:[^a]|bb)*a/)'
>

我确实从源代码编译了最新的 Perl，只是为了看看它是否能解决问题:

>./perl -v

This is perl 5, version 20, subversion 1 (v5.20.1) built for i686-linux

这是一个错误(在我看来)吗？

Answer 1

这是一个 known bug自 2002 年开始报告，至今仍未修复。您现在知道您不是第一个遇到此错误(或功能，您很快就会看到)的人。

来自 this comment在错误报告中，似乎量词( * 、 + 、 {n,m} 、 {n,} )被设计为对重复次数有上限，这可以防止引擎在堆栈用于回溯溢出，但违反了正则表达式中 Kleene 运算符的定义(重复任意次数的模式)并为查询给出错误答案1。

1 相比之下，Java 的正则表达式引擎(Oracle 的实现)只允许 StackOverflowError在这种情况下会发生，但量词的上限为 232 - 1，这对于大多数用例来说已经足够了。对于这种情况，存在一种解决方法，即使用所有格量词。

相同的注释还打印了正则表达式编译调试信息，并且输出清楚地表明 *翻译成 {0,32767} .它也可以在我的机器上重现(为 x86_64-linux-thread-multi 构建的 perl v5.10.1 (*))。

$ perl -Mre=debug -wce '/(A|B)*/'
Compiling REx "(A|B)*"
Final program:
   1: CURLYM[1] {0,32767} (15)
   5:   TRIE-EXACT[AB] (13)
        <A>
        <B>
  13:   SUCCEED (0)
  14: NOTHING (15)
  15: END (0)
minlen 0
-e syntax OK
Freeing REx: "(A|B)*"

下面的测试进一步证实了这个问题，它表明 perl 不允许您指定超出限制的重复。

$ perl -e 'print (("a".("f"x32767)."a") =~ /a(?:[^a]|bb){0,32767}a/)'
Quantifier in {,} bigger than 32766 in regex; marked by <-- HERE in m/a(?:[^a]|bb){ <-- HERE 0,32767}a/ at -e line 1.

使量词具有所有格 *+ 不是 解决问题，因为极限仍然存在:

$ perl -Mre=debug -wce '/(A|B)*+/'
Compiling REx "(A|B)*+"
Final program:
   1: SUSPEND (19)
   3:   CURLYM[1] {0,32767} (17)
   7:     TRIE-EXACT[AB] (15)
          <A>
          <B>
  15:     SUCCEED (0)
  16:   NOTHING (17)
  17:   SUCCEED (0)
  18: TAIL (19)
  19: END (0)
minlen 0
-e syntax OK
Freeing REx: "(A|B)*+"