Search code examples
bnfebnf

Converting BNF to EBNF - Parentheses without recursion?


I need to convert the following grammar to EBNF:

<assign> -> <id> = <expr>
<id> -> A|B|C
<expr> -> <expr> + <expr>
    |<expr> * <expr>
    |<expr> * <expr>
    |( <expr> )
    |<id>

The progress I've currently made is below:

<assign> -> <id> = <expr>
<id> = (A | B | C)
<expr> -> <id> {(+ | * ) <expr>} | ‘(‘ <expr> ‘)’

Is it best to eliminate all recursion if using EBNF? Is there even a way to accomplish it using only <id> in <expr>?


Solution

  • How about this:

    <assign> -> <id> = <expr>
    <expr>   -> <mul>  {+ <mul>}
    <mul>    -> <term> {* <term>}
    <term>   -> ( <expr> ) | <id>
    <id>     -> A | B | C
    

    No left recursion, and * takes precedence over +, but not over ( ... ).