How to handle operator precedence in an LL(1) parser

Question

I was writing an LL(1) parser for an expression grammar. I had the following grammar:

E -> E + E
E -> E - E
E -> E * E
E -> E / E
E -> INT

However, this is left recursive and I removed the left recursion with the following grammar:

E -> INT E'
E' -> + INT E'
E' -> - INT E'
E' -> * INT E'
E' -> / INT E'
E' -> ε

If I was to have the expression 1 + 2 * 3, how would the parser know to evaluate the multiplication before the addition?

Your second grammar will produce a parse tree that's right-associative. That is, `1 + 2 * 3` will produce a parse tree that correctly has `2 * 3` as the right operand of the `+`, but `1 * 2 + 3` would incorrectly consider `2 + 3` to be the right operand of `*`. Your first grammar is ambiguous and can derive either parse tree for `1 + 2 * 3`. — sepp2k, Nov 04 '21 at 15:29
Does this answer your question: https://stackoverflow.com/a/69591031/14298586 ? — Nikolay Handzhiyski, Nov 04 '21 at 16:29

score 1 · Accepted Answer · answered Nov 06 '21 at 07:57

Try this:

; an expression is an addition
E   -> ADD          

; an addition is a multiplication that is optionally followed
; by +- and another addition
ADD -> MUL T  
T   -> PM ADD
T   -> ε
PM  -> +
PM  -> -

; a multiplication is an integer that is optionally followed
; by */ and another multiplication
MUL -> INT G
G   -> MD MUL
G   -> ε
MD  -> *
MD  -> /

; an integer is a digit that is optionally followed by an integer
INT -> DIGIT J
J   -> INT
J   -> ε

; digits
DIGIT -> 0
DIGIT -> 1
DIGIT -> 2
DIGIT -> 3
DIGIT -> 4
DIGIT -> 5
DIGIT -> 6
DIGIT -> 7
DIGIT -> 8
DIGIT -> 9

How to handle operator precedence in an LL(1) parser

1 Answers1