Re: [RFC] Method of feeding input to regexp matching

Hi --

On Fri, 4 Nov 2005, Nikolai Weibull wrote:

> David A. Black wrote:
>
>> I'm thinking of cases like this:
>>
>>   re = /abc.*def/
>>
>> The first chunk out of the file might match this -- but then you'd
>> have to keep going, really until EOF, to get the greedy match if it's
>> there.  Then you'd have to go back.
>
> Well, think of it like this instead.  The Regexp simply reads from the
> input source when it needs more data.  The Regexp will concatenate the
> new data with the old and continue on its matching routine.  We build
> the input as we go along, i.e., we’re in a sense dealing with
> implementing lazy Strings.  This won’t cause any issues with
> backtracking, as the data will still be there.

In the /abc.*def/ case, though, you'd always have to take all the
input (at least up to the third-to-last character in the file), even
if you had an intermediate match.  So "needs more data" would not be
something the regex could tell you.  It would say, "Yes, there's a
match", but you would have to know that the "yes" didn't mean you
could stop.

But if the regex were /abc.*?def/, then as soon as there was a "yes",
you could stop.

There's also a question of: if the first 4096 bytes started with "abc"
and ended with "de", then you'd add the next 4096 -- but you'd have to
perform the match again.  Or else you'd have to know to rewind by
exactly two characters.  But if you're changing where you start the
match, that could affect how anchors worked.

Basically you'd have to get two state machines to talk to each other.
Not to say it couldn't be done, but it seems to me there's are areas
of impedance mismatch.


David

-- 
David A. Black
[e-mail]