Re: yet another pattern-matching library for Lua

[roberto@... (Roberto Ierusalimschy)]

> Maybe it's also interesting to show what cannot be expressed with
> PEGs. Apart from the textbook examples (see the Wikipedia links),
> I think I found one with practical relevance:
> 
> I found no closed PEG for properly parsing Lua 5.1 long strings
> and long comments. This is easy for any finite subset:
> 
>   "[==[" * (P(1)-"]==]")^0 * "]==]"
> 
> But it seems the middle finder approach cannot be used for
> recursively extending the grammar. The problem is that one needs
> to inject not only the ending pattern (easy), but also the
> non-matching pattern for arbitrary numbers of "=".
> 
> I think there is no PEG solution to this particular problem. But
> I'd really like to be proved wrong. Anyone?

As far as I can tell, this is neither solvable with PEGs nor with
regular expressions (the real ones) nor with deterministic context free
grammars.


> Extended regexps (really: irregular exps) can parse this with a
> backward reference to a capture:
> 
>   "%[(=*)%[.-%]%1%]"
> 
> But this only works because of implicit backtracking as part of
> the non-greedy repetition.

A happy coincidence, in other words :)

LPeg already supports arbitrary extensions through C functions. I plan
to add arbitrary extensions through Lua functions too. (That's one of
the main reasons I added the tools for keeping Lua values in patterns,
done in version 0.2.)

Another nice thing about PEGs is that it mixes well with these arbitrary
extensions, because of its more deterministic nature. A pattern built on
an external extension is as composable as any other.

-- Roberto