Re: BNF to LPEG

[Chris Emerson <chris-lua@...>]

On Sat, Apr 09, 2016 at 07:47:18AM +0200, Dirk Laurie wrote:
> I can understand that to get from BNF (or EBNF) to LPeg with equivalent
> functionality is highly nontrivial.
> 
> When doing it manually, though, a very large part of the work is tedious
> but straightforward: precisely the sort of thing that computers do perfectly
> but humans don't.
>
> For example, just mechanically substituting notation.
> 
> {something} becomes (something)^0
> [something] becomes (something)^-1
> | becomes +
> juxtaposition becomes multiplication

But simple substitutions like this doesn't actually do the right thing due to
PEG patterns having a different (but deceptively similar) meaning.

Regular expressions, which are less powerful than BNF, can be converted
automatically[1], but the conversion, while mechanical, isn't as simple as
the above.

As an example from the paper, the regular expression "(ba|a)*a" is not, as you
might expect, converted to the structurally similar:

    ((P"ba" + P"a")^0) * P"a"

The correct conversion is actually the recursive grammar:
    P{"A", A=(P"ba" * V"A") + (P"a" * V"A") + P"a"}

I have implemented regex-to-LPeg conversion in case it's of any use for simple
BNF cases.

https://luarocks.org/modules/jugglerchris/pegex

Regards,

Chris

[1] Roberto et al's paper: http://www.inf.puc-rio.br/~roberto/docs/ry10-01.pdf