There are actually two problems with our expression grammar. Obviously, it does not tell which operator, + or *, has higher precedence. But an equally bad problem, also due to it ambiguity, is that it does not say whether a sequence of + operations are done from left to right or from right to left (or something else). Here are two different parse trees for n + n + n.
E E
/|\ /|\
/ | \ / | \
E + E E + E
| /|\ /|\ |
n / | \ / | \ n
E + E E + E
| | | |
n n n n
Does it matter? After all, addition is associative.
But keep in mind that we are only concerned with syntax here, not with meaning. What + means is a separate issue. What if + means subtraction? Then it definitely makes a difference which parse tree is chosen.
It turns out to be easy to make an unambiguous grammar that derives exactly the same sequences of tokens.
The heart of the problem with our expression grammar is its symmetry. You see E + E and E * E.
The key to making an unambiguous grammar is to introduce some asymmetries that force a derivation to be done in a particular way.
We create a nonterminal for each level of precedence.
E derives any expression,
T derives only expressions that do not contain + except possibly inside parentheses,
F derives only expressions that have no operators except possibly inside parentheses.
We also introduce asymmetries in the right-hand sides of production to force operations to be done from left to right.
| E | → | T |
| E | → | E + T |
| T | → | F |
| T | → | T * F |
| F | → | n |
| F | → | ( E ) |
A little thought shows that this grammar is unambiguous. Here is the only parse tree for expression n + n * n.
E
/|\
/ | \
E + T
| /|\
T T * F
| | |
F F n
| |
n n
Additions are forced to be done from left to right. Here is the unique parse tree for n + n + n.
E
/|\
/ | \
E + T
/|\ |
E + T F
| | |
T F n
| |
F n
|
n
For variety, let's define an expression grammar where * still has precedence over +, + is done from right to left and * is done from left to right.
| E | → | T |
| E | → | T + E |
| T | → | F |
| T | → | T * F |
| F | → | n |
| F | → | ( E ) |
A production of the form N → αN is right recursive because the recursive reference to nonterminal N is at the right end of the right-hand side.
For example, production E → T + E is right recursive, and it indicates that + is right associative (done from right to left).
Similarly, a production of the form N → Nα is left recursive. Left-recursive rule T → T * F indicates that * is left-associative (done from left to right).