Grammar translation

[Ivan Perez]

Hi all,

I have a general question about how to best use BNFC.

I would love to work with an ideal grammar that is not adapted to any particular parsing algorithms. However, I always find myself having to write grammars that are adapted so that parser generators know how to parse them well, which makes them harder to read in the abstract. For example, regardless of whether BNFC can handle this particular case, think of the following production:

A ::= (B)*

Some parsing algorithms would like that to be:

A ::= epsilon

A ::= A B

Others would prefer to see:

A ::= epsilon

A ::= B A

Both of those generate B*, which maybe can be proven in some cases.

What would be the best way to approach describing the translation of a grammar, from its ideal, potentially ambiguous form, to a more concrete, easy-to-parse form?

Thanks,

Ivan

[Andreas Abel]

Hi Ivan,

since BNFC serves mostly LR-parser generators in its backends (exception
is the Java/ANTLR backend), lists should be written in right-recursive
style since these are handled more efficiently by some LR parsers than
left-recursive lists (which are also handled by LR parser). In
contrast, LL parsers such as ANTLR fare better with left-recursion.

> A ::= epsilon
> A ::= A B

This is left-recursion suited for LL parsing.

> A ::= epsilon
> A ::= B A

This is right-recursion generally favored for LR parsing.

However, in BNFC you do not really have to worry, since there are
dedicated list constructions. The pragma

terminator A "";

allows you to use [A] for white-space separated lists of A.

Best,
Andreas

> --
> You received this message because you are subscribed to the Google
> Groups "BNFC Developers and Users" group.
> To unsubscribe from this group and stop receiving emails from it, send
> an email to bnfc-dev+u...@googlegroups.com
> <mailto:bnfc-dev+u...@googlegroups.com>.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/bnfc-dev/f1f1fd10-f8af-4f3b-84d7-816dca10f0e5o%40googlegroups.com
> <https://groups.google.com/d/msgid/bnfc-dev/f1f1fd10-f8af-4f3b-84d7-816dca10f0e5o%40googlegroups.com?utm_medium=email&utm_source=footer>.

[Ivan Perez]

Thanks. I know. I used lists as a example of a common case in which translation is used in parser generators, but that's why I said "regardless of whether BNFC can handle this particular case".

My question is more general than that.

What is the best way to establish that correspondence between a language's "ideal" grammar and the one that has been altered to facilitate parsing?

Ivan

> an email to bnfc...@googlegroups.com
> <mailto:bnfc...@googlegroups.com>.