Search code examples
bnfassociativity

Backus Naur Form Assoicativity

Is this the correct way to implement right associativity for Exponentiation PowExp? So that 2^3^4 is actually (2^(3^4))

<Exp> ::= <Exp> + <MulExp>
| <Exp> - <MulExp>
| <MulExp>
<MulExp> ::= <MulExp> * <PowExp>
| <MulExp> / <PowExp>
| <PowExp>
<PowExp> ::= <NegExp> ^ <PowExp>
|<NegExp>
<NegExp> ::= - <RootExp>
| <RootExp>
<RootExp> ::= ( <Exp> )
| 1 | 2 | 3 | 4
Solution

  • The way you've written it is correct.

    Incidentally, you might want to reconsider your hierarchy; in regular math, −34 is −(34), not (−3)4. So you might want - 3 ^ 4 to mean - (3 ^ 4), in which case NegExp would include PowExp rather than the other way around. (But I suppose it could be confusing if -3 ^ 4 means -(3 ^ 4), so maybe there's no intuitive order-of-operations here? Another possibility is to require parentheses for either reading, by having PowExp and NegExp both depend directly on RootExp.)