http://www.perlmonks.org?node_id=971864


in reply to Re: Perl Complains of Nested Quantifiers
in thread Perl Complains of Nested Quantifiers

The Extended Patterns documentation mentions that "(?>pattern) does not disable backtracking altogether once it has matched." A concern was expressed about "catastrophic backtracking." I'm curious about the nature of the 'catastrophe,' and whether your solution would satisfactorily avert it.

Replies are listed 'Best First'.
Re^3: Perl Complains of Nested Quantifiers
by demerphq (Chancellor) on May 22, 2012 at 21:38 UTC

    Well, what this means is that a pattern like /foo(?:baz)++baz/ will never match. If you had a string like "foobazbazbaz" it would fail because (?:baz)++ will "gobble up" all of the "baz" in the string, and then refuse to give anything back. What it means by "does not disable backtracking" is that "foobazbazbaz foobazbazbaz" will *attempt* the /(?:baz)++/ twice, once after each "foo". Neither will match of course, and if the RE was _really_ smart it would know it could never match and wouldn't try at all, but it isn't. :-)

    ---
    $world=~s/war/peace/g

[reply]
[d/l]
Re^3: Perl Complains of Nested Quantifiers
by AnomalousMonk (Archbishop) on May 22, 2012 at 23:14 UTC
    A concern was expressed about "catastrophic backtracking." I'm curious about ... whether your solution would satisfactorily avert it.

    It would not. AFAIU, possessive quantifiers like  ++ *+ ?+ {n,m}+ are just special, limited cases of the general  (?>...) atomic grouping. See example below. 

    >perl -wMstrict -le
"my $s = 'foobazbazbaz foobazbazbaz';
 print 'match 1'
   if $s =~ m{ foo (?> (?:baz)+) baz }xms;
 print 'match 2'
   if $s =~ m{ foo (?> .* baz) baz }xms;
"

    [download]
    (no output)
[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom