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 .