Re: Perl 5's "non-greedy" matching can be TOO greedy!

On Fri, 15 Dec 2000, Tom Christiansen wrote:

> >Actually, I'm not sure -- it's conceivable that the ending point would ALSO
> >move inward for a different starting point within the original match.  But
> >the ending point should NEVER be advanced further -- that's where the
> >"leftmost over nongreedy" rule should apply instead...
> 
> Please show us your implementation for a pattern matching engine
> that lets the current end-point vary.  This is very exciting,
> because now you can relax the restriction that lookbehinds
> must be constant width.

I don't know if it can be implemented.  I'm just not assuming out of hand
that it CANNOT.  Just because we can't see how to implement it doesn't mean
there isn't a technique we haven't thought of yet.  I won't go so far as to
say that "I can't think of one" until such time as I've seriously TRIED to.

When I do try, maybe then I'll be convinced that the answer is beyond me,
or that it doesn't exist.  Until then, I consider it an interesting, yet
unresolved question.

However, that wasn't the point of the above paragraph.  I meant that you
might have a match that the current engine would return, which starts at
position x and ends at position y.  Obviously, a less-greedy match is
possible which starts at position x', where x < x' <= y.  It might be
possible that such a match could also end at position y' where y' < y.
I don't have an example in mind, but I can't rule out the possibility.

In both cases above, it's the same thing -- I'm reluctant to jump to the
conclusion that something doesn't exist just because _I_ don't see it yet.

Deven