Re: Prefixes of Lpeg patterns

[Gavin Wraith <gavin@...>]

In message <20150416142336.GA26114@inf.puc-rio.br>
          Roberto Ierusalimschy <roberto@inf.puc-rio.br> wrote:

>I don't think that is true. match("a", "a") returns 2, but match("ab",
>"a") fails; so, by your definition, match("a", "a") </= match("ab", "a").
>(and, so, lpeg.P("a") </= lpeg.P("ab")). ('</=' stands for 'not <='...)

You are right. What about:

B <= A if for all strings s for which A:match(s) = 1 + #s, B does not
fail on s?

What led me to think about the notion was the thought of lazy matching
of a pattern against a stream of characters. pat:lazy-match(stream)
should return a pair (result, continuation) where result is either
nil (fail) or an integer n (1 + the length of the accumulated string
it succeeds on) and continuation is a function of no arguments that
resumes the matching of the pattern against more of the stream.
To retest a whole accumulated string right from the start may be
uneconomic. A pattern will fail on a string if some prefix of the
pattern fails on it.

If a prefix of the string has been found to match, and it contains
no unresolved backtracking points, then it should be possible to
throw it away, I imagine, and continue with a possibly modified pattern.

-- 
Gavin Wraith (gavin@wra1th.plus.com)
Home page: http://www.wra1th.plus.com/