Your original grammar is not only left-recursive, it is also ambiguous. Left-recursion only matters to certain parsing techniques, but ambiguous grammars are, by definition, impossible to parse with a deterministic parser. And removing left-recursion does not in general fix ambiguity.
The ambiguity is in the production
R → R + R
which allows 1 + 2 + 3
to be parsed in two different ways: as the result of adding 3
to 1 + 2
or as the result of adding 2 + 3
to 1
. (These have the same value, but if the operator had been -
instead of +
, the ambiguity would allow two different evaluations.)
The correct way to write this grammar unambiguously is
S → L = R
L → *L | id
R → F | R + F
F → L | num
With that grammar, 1 + 2 + 3
can only be parsed as the sum of 1 + 2
and 3
, because 2 + 3
is not an F
. That makes +
a left-associative operator, which is the normal usage. (Again, this is clearer if you consider the operator -
: 1 - 2 - 3
is -4
, not 0
.)
You can then, if you want to, apply the left-recursion elimination algorithm, to yield:
S → L = R
L → *L | id
R → F R'
R'→ + F R' | ε
F → L | num
Note, however, that after left-recursion elimination, the associativity of +
is not so clear. With a simple operator grammar like this, left-recursion elimination is essentially the same as the two steps:
Change left-associative operators (left-recursive productions) to being right-associative.
Left-factor the productions.
Thus, after left-recursion elimination, a left-associative grammar and a right-associative grammar are the same.