How can I convert the extended Backus Naur grammar to its normal representation?
I have a grammar containing expressions between brackets '{}' that represent 0 or more times this expression, and expressions between square brackets '[]' that represent 1 or more times this expression, I think these kind of grammars are called expanded Grammars of the Backus-Naur form. I would like to convert the grammar to its normal form (where there are no brackets or square brackets).
Is there an existing algorithm for this?
I know that I can replace something like A -> B [CD] E with A -> BE, A -> BCDE, but I would like to know if there are existing algorithms that I could implement to transform these expressions.
source to share
The easiest way to do this is to replace each EBNF with a new rule. Here are the equivalents you can use:
Option
A ::= B [C D] E ;
A ::= B X E ;
X ::= C D | ɛ ;
Where ɛ represents an empty string.
Repetitions
A ::= B {C D} E ;
Zero or more times:
A ::= B X E ;
X ::= C D X | ɛ ;
One or more times:
A ::= B X E ;
X ::= C D | C D X ;
Grouping
A ::= B (C D) E ;
A ::= B X E ;
X ::= C D ;
Apply these transformations recursively and you end up with vanilla BNF.
source to share