Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Unambiguous grammar for exponentiation operation

E -> E+T | E-T | T
T -> T*F | T/F | F
F -> i | (E)

How can I modify this grammar to allow an exponentiation operation ^ so that I can write i+i^i*i? Since we know that order of operations is higher for ^ then all I know is that I must make it right associative.

like image 578
aluminumMonster Avatar asked Jun 18 '13 07:06

aluminumMonster


Video Answer


2 Answers

In EBNF (Extended Backus-Naur Form), this could look as follows:

expr -> term [ ('+' | '-') term ]*
term -> factor [ ('*' | '/') factor ]*
factor -> base [ '^' exponent ]*
base -> '(' expr ')' | identifier | number
exponent -> '(' expr ')' | identifier | number

(taken from here)

Translated to your notation (no distinction between numbers and identifiers):

E -> E+T | E-T | T
T -> T*F | T/F | F
F -> F^X | B
B -> i | (E)
X -> i | (E)

One could merge "B" and "X" for the sake of clarity.

like image 200
Axel Kemper Avatar answered Oct 16 '22 03:10

Axel Kemper


Both answers provided here are wrong. In these answers ^ associates to the left, when in fact it should associate to the right. The correct modified grammar should be:

  E -> E+T | E-T | T
  T -> T*X | T/X | X
  X -> F^X | F //Note: it's F^X not X^F
  F -> i | (E)

In this way, your grammar works as expected with an expression like :

a+b^c^d^e*f

Thanks!

like image 42
ToxicAbe Avatar answered Oct 16 '22 03:10

ToxicAbe