Re: yet another pattern-matching library for Lua

[Mike Pall <mikelu-0701@...>]

Hi,

Brian Hagerty wrote:
> PEGS are a kind of context-sensitive grammar, which are a proper 
> superset of CFGs, which in turn are a superset of RegExps.

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?

[
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.
]

Bye,
     Mike