Search code examples
programming-languagesbnf

Question regarding BNF

I have this grammar written in BNF. How do I convert it to give + precedence over * and force + to be right associative?

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

This is my solution: 

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

How could I check the correctness of a given grammar? Any idea?
Thanks,

Solution

  • Looks strange that you want to revert the precedence of multiplication over addition, but anyway if you need the grammar that way, then the correct BNF would be (you made a typo on the third production)

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

    Which is right for an LR parser (bottom-up).

    For a LL parser (top-down), the above grammar will cause left recursion on <expr> and <term>. To workaround this issue, you should use this grammar for LL parsers:

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