Почему 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))+\)) вызывает катастрофический c возврат .

Чтобы исправить рекурсивный шаблон, используйте ++ собственнический квантификатор с [^()], [^()]++ или используйте группу атома c вместо группы без захвата, (?>[^()]+|(?&brace))+.

Итак, используйте любой из

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

См. онлайн демо .