0

I'm trying to make an expression parser and although it works, it does calculations chronologically rather than by BIDMAS; 1 + 2 * 3 + 4 returns 15 instead of 11. I've rewritten the parser to use recursive descent parsing and a proper grammar which I thought would work, but it makes the same mistake.

My grammar so far is:

exp     ::= term op exp | term
op      ::= "/" | "*" | "+" | "-"
term    ::= number | (exp)

It also lacks other features but right now I'm not sure how to make division precede multiplication, etc.. How should I modify my grammar to implement operator-precedence?

Cyclip
  • 11
  • 1
  • 2
  • 4
  • Does this (https://stackoverflow.com/a/69591031/14298586) answer your question? – Nikolay Handzhiyski Nov 05 '21 at 10:27
  • Division doesn't precede multiplication. Division and multiplication have the same precedence, grouped from left to right. They group more strongly than addition and subtraction, which are also grouped left to right. The bottom line is that you can't clump all the operators into a single `op` non-terminal. In fact, operator non-terminals are not usually a good idea, even if you define one such non-terminal for each precedence level. Better to separate the productions which use each different operator. – rici Nov 05 '21 at 20:22

1 Answers1

0

Try this:

exp   ::= add
add   ::= mul (("+" | "-") mul)*
mul   ::= term (("*" | "/") term)*
term  ::= number | "(" exp ")"

Here ()* means zero or more times. This grammar will produce right associative trees and it is deterministic and unambiguous. The multiplication and the division are with the same priority. The addition and subtraction also.

Nikolay Handzhiyski
  • 1,360
  • 1
  • 6
  • 20