regex - 为什么 Perl 正则表达式挂起？

Question

我有以下代码(使用递归正则表达式)。一切似乎都很顺利，除了在一个特定的地方，我有一个无与伦比的支架。我试图了解到底是什么导致了挂起。我有:

use strict;
use warnings;
use Carp;
use Data::Dumper;

my $matchBracePtrn =    qr/(?<brace>\((?:[^()]+|(?&brace))+\))/;
my $mkVarPtrn =         qr/\$(?:\w|${matchBracePtrn})/;

# my $testString='$(a) $(a $(c)';   # OK: reports $(a) and $(c)...
# my $testString='$(foreach i,$(LIST),$(eval $(call foo,$i)))'; # OK
my $testString='$(a) $(foreach i,$(LIST),$(eval $(call foo,$i))'; #not OK!

while ($testString =~ /($mkVarPtrn)/g) {
    print "$1\n"
}

输出:

$(a)

然后挂起。这是 perl 5.22.0，以防万一。

Answer 1

(?<brace>\((?:[^()]+|(?&brace))+\))模式原因catastrophic backtracking .

为了修复递归模式，可以使用 ++所有格量词 [^()] , [^()]++ ，或使用原子组代替非捕获组，(?>[^()]+|(?&brace))+ .

因此，使用其中之一

my $matchBracePtrn =    qr/(?<brace>\((?:[^()]++|(?&brace))+\))/;
my $matchBracePtrn =    qr/(?<brace>\((?>[^()]+|(?&brace))+\))/;

请参阅online demo .