0

我有一个 perl 脚本，它需要指数时间来根据正在解析的字符串的长度来解析正则表达式。代码如下：

$BRACE_MATCH = qr/ (?: [^\(\)]+ | \((??{$BRACE_MATCH})\))* /x;
$expr="(abcdef || abcdefghijklmno)"
timethis(1, sub {$expr =~ /^($BRACE_MATCH)\|\|($BRACE_MATCH)$/});

这需要 8 秒才能运行。如果我在字符串中添加另一个字母，则需要 16 个。有没有一种有效的方法来做到这一点？

4

2 回答 2

2

正如 ikegami 所说，需要这么长时间的原因是模式可以将字符串分成块的方式呈指数级增长。为了让它在 Perl 的正则表达式引擎中有效地工作，你必须限制回溯。

您可以使用++所有格量词来做到这一点。这通过说它是全部或全部来限制回溯。但要让它发挥作用，你必须小心它匹配的内容。

不起作用的原因[^()]++（您不需要那里的反斜杠，括号在字符类中并不特殊）是它也匹配|，这是您更大的正则表达式正在寻找的字符。您需要能够回溯|，但不能回溯其他字符（因为将字符串拆分为除( )或|不会帮助正则表达式匹配的字符）。

尝试这个：

$BRACE_MATCH = qr/ (?: [^()|]++ | \| | \((??{$BRACE_MATCH})\))* /x;

这表示这$BRACE_MATCH是任意数量的 3 件事的序列：

  1. 字符串以外的字符()|（将作为单个块回溯）
  2. 一个|字符
  3. 平衡的(...)表达

原因是

$BRACE_MATCH = qr/ (?: [^()]++ | \((??{$BRACE_MATCH})\))* /x;

不匹配(XX || YY) || ZZ的是 . 后面有空格)。该空格与该[^()]++部分匹配，但也与字符串的其余部分匹配（因为没有更多的括号），然后不会将其部分返回（因为它是所有格量词）。

于 2013-03-07T06:09:44.260 回答
1

问题是引擎必须尝试许多可能性，然后才能确定它们都不匹配。

Perl 的引擎旨在避免不必要的回溯（即使以匹配比其他引擎慢一点为代价），但优化显然无法帮助您。

所以你需要做的是减少回溯的数量，这很容易做到。

our $BRACE_MATCH = qr/ (?> (?: [^()]+ | \( (??{ $BRACE_MATCH }) \) )* ) /x;
                       ^^^                                            ^

或者正如我在两小时前的评论中建议的那样：

our $BRACE_MATCH = qr/ (?: [^()]++ | \( (??{ $BRACE_MATCH }) \) )*+ /x;
                                 ^                                ^

通过这些更改中的任何一个，测试需要 0 秒而不是 22 秒。

顺便说一句，您可能想研究使用(?PARNO)

类似于，(??{ code })除了它不涉及编译任何代码

于 2013-03-06T20:27:24.053 回答