BNF to LPEG

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

BNF to LPEG

Dirk Laurie-2
Is there a module that can convert BNF to LPEG?
The test case being the Lua grammar in §9 of in the manual.

Reply | Threaded
Open this post in threaded view
|

Re: BNF to LPEG

Roberto Ierusalimschy
> Is there a module that can convert BNF to LPEG?
> The test case being the Lua grammar in §9 of in the manual.

Not that I know. Such a conversion is tricky for at least two reasons:

- Usually, BNF assumes a separate scanner, while LPeg works directly
on the character level.

- Although BNF and LPeg may look similar, they have different meanings.
(If the BNF is LL(n), then a corresponding LPeg would have equal
meaning, but the scanner problem is still there. In particular, the
Lua grammar in the manual is not LL(n).)

-- Roberto

Reply | Threaded
Open this post in threaded view
|

Re: BNF to LPEG

Dirk Laurie-2
2016-04-07 15:22 GMT+02:00 Roberto Ierusalimschy <[hidden email]>:

>> Is there a module that can convert BNF to LPEG?
>> The test case being the Lua grammar in §9 of in the manual.
>
> Not that I know. Such a conversion is tricky for at least two reasons:
>
> - Usually, BNF assumes a separate scanner, while LPeg works directly
> on the character level.
>
> - Although BNF and LPeg may look similar, they have different meanings.
> (If the BNF is LL(n), then a corresponding LPeg would have equal
> meaning, but the scanner problem is still there. In particular, the
> Lua grammar in the manual is not LL(n).)

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

Etc.

After converting about twenty lines of a particular EBNF (not Lua's)
in this way, and making the occasional mistake, I thought "This job
will take less total time if I write a litlle Lua program". After writing
about twenty lines of that program, I thought "someone must have
done this before".

Oh well. :-(

Reply | Threaded
Open this post in threaded view
|

Re: BNF to LPEG

Chris Emerson
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


Reply | Threaded
Open this post in threaded view
|

Re: BNF to LPEG

Dirk Laurie-2
2016-04-09 8:27 GMT+02:00 Chris Emerson <[hidden email]>:
> 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"

That is the sort of thing I don't mind having to do manually.
With LPeg, there is no need to express every single case in
the PEG itself, you've got all of Lua to help you.  P(1)^0/myfunc
if nothing else works.