develooper Front page | perl.perl5.porters | Postings from February 2009

Re: regexp iteration limits

Thread Previous | Thread Next
Dave Mitchell
February 23, 2009 09:36
Re: regexp iteration limits
Message ID:
On Sun, Feb 22, 2009 at 11:11:04PM +0000, Zefram wrote:
> demerphq wrote:
> >                                      I guess we could bifurcate all
> >the regops, but that gets messy.
> I think only the iteration regops need this bifurcation.
> In /(?>(?:...)*)/, the "*" can be told at parse time that it's in a
> no-backtracking context, and it can compile to a regop that doesn't
> make backtracking records and throws away the internal backtracking
> records of the (?:...) at the end of each iteration.  Whatever's inside
> the (?:...) doesn't need to be compiled any differently from usual.
> Although, in fact, in this case one can impute a (?>...) around it,
> and so pass the non-backtracking context inwards.
> There are more complicated cases.  Generally, in /(?>(?:...){N,M})/, the
> (?:...) needs to keep its backtracking records for the first N iterations.
> After N iterations are complete, we know that we'll never backtrack
> through there, so all those backtracking records can be discarded, and
> each subsequent iteration's backtracking records can be discarded at
> the end of the iteration.

Note that if the inner (?:...) isn't too complex, then currenty only a
single backtracking record is pushed on the stack, and the counter within
that record is updated for each iteration.

"Strange women lying in ponds distributing swords is no basis for a system
of government. Supreme executive power derives from a mandate from the
masses, not from some farcical aquatic ceremony."
    -- Dennis, "Monty Python and the Holy Grail"

Thread Previous | Thread Next Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at | Group listing | About