Perl 显然是如何避免灾难性的回溯的？-解网

问：

我正在使用 Perl 5.34.1 和 Python 3.10.12。

以下脚本在 Python 中需要 16 秒：

import re
patt = re.compile(r"W(X|Y+)+Z")
print(patt.search("WYYYYYYYYYYYYYYYYYYYYYYYYYYYYA"))

但是在Perl中几乎不需要任何时间：

use v5.34;
my $patt = qr/W(X|Y+)+Z/;
print("WYYYYYYYYYYYYYYYYYYYYYYYYYYYYA" =~ $patt);

这是 https://medium.com/bigpanda-engineering/catastrophic-backtracking-the-dark-side-of-regular-expressions-80cab9c443f6 提供的灾难性回溯的一个例子。

我预计在这种情况下，任何回溯正则表达式引擎都会受到影响，但显然 Perl 正则表达式引擎不会。在此示例中，它如何避免灾难性的回溯？它是否真的在内部“灾难性地”回溯，但比 Python 引擎快几个数量级？它是否使用了一些快速路径优化来防止在完成完整的回溯序列之前尽早失败？

正则表达式 Perl

$ perl -Mre=debug -e'
    use v5.34;
    my $patt = qr/W(X|Y+)+Z/;
    print("WYYYYYYYYYYYYYYYYYYYYYYYYYYYYA" =~ $patt);
'
Compiling REx "W(X|Y+)+Z"
Final program:
   1: EXACT <W> (3)
   3: CURLYX<1:1>[0]{1,INFTY} (21)
   7:   OPEN1 (9)
   9:     BRANCH (buf:1/1) (13)
  11:       EXACT <X> (18)
  13:     BRANCH (buf:1/1) (FAIL)
  15:       PLUS (18)
  16:         EXACT <Y> (0)
  18:   CLOSE1 (20)
  20: WHILEM[1/1] (0)
  21: NOTHING (22)
  22: EXACT <Z> (24)
  24: END (0)
anchored "W" at 0..0 floating "Z" at 2..9223372036854775807 (checking floating) minlen 3
Matching REx "W(X|Y+)+Z" against "WYYYYYYYYYYYYYYYYYYYYYYYYYYYYA"
Intuit: trying to determine minimum start position...
  doing 'check' fbm scan, [2..30] gave -1
  Did not find floating substr "Z"...
Match rejected by optimizer
Freeing REx: "W(X|Y+)+Z"

也就是说，使用会绕过该优化。qr/W(X|Y+)+(Z|!)/

$ perl -Mre=debug -e'
    use v5.34;
    my $patt = qr/W(X|Y+)+Z/;
    print("WYYYYYYYYYYYYYYYYYYYYYYYYYYYYA" =~ $patt);
' 2>&1 | wc -l
22

$ perl -Mre=debug -e'
    use v5.34;
    my $patt = qr/W(X|Y+)+(Z|!)/;
    print("WYYYYYYYYYYYYYYYYYYYYYYYYYYYYA" =~ $patt);
' 2>&1 | wc -l
2971

尽管如此，在我的机器上，差异还不到 1 毫秒。

$ time perl -e'
    use v5.34;
    my $patt = qr/W(X|Y+)+Z/;
    print("WYYYYYYYYYYYYYYYYYYYYYYYYYYYYA" =~ $patt);
' 2>&1 | wc -l
0

real    0m0.002s
user    0m0.002s
sys     0m0.000s

$ time perl -e'
    use v5.34;
    my $patt = qr/W(X|Y+)+(Z|!)/;
    print("WYYYYYYYYYYYYYYYYYYYYYYYYYYYYA" =~ $patt);
' 2>&1 | wc -l
0

real    0m0.002s
user    0m0.002s
sys     0m0.000s

显然，还有其他优化。此版本包含以下消息：-Mre=debug

WHILEM: Detected a super-linear match, switching on caching...

你可以试着看看Yves “demerphq” Orton是否就此做过任何演讲。

2赞 Dave Mitchell 9/29/2023 #2

在其他优化中，perl 的正则表达式引擎有一个叫做超线性缓存的东西。经过一定次数的迭代后，引擎确定匹配已变为“超线性”，并分配一个缓存，该缓存是与字符串长度相似的字节数组。它使用此缓存中的位来标记字符串中的某些匹配位置，这些位置在模式中的某个点失败，如果达到类似位置，它们将始终再次失败。因此，跳过了类似案例的无休止的重试。是否使用此技术取决于模式的细节。

上一个：Perl 脚本将两个模式之间的行合并为一行并打印整个文件

下一个：Perl 在正则表达式替换中调用 tr 函数

Perl 显然是如何避免灾难性的回溯的？

How does Perl apparently avoid catastrophic backtracking?

评论