Is this an LL(1) grammar? How to solve First - Follow conflict?

Question

im trying to check if this grammar is LL(1).

S -> L = R
L -> * L | id
R -> L | R + R | num

As you can see there is a Left recursion on R production. So i remove that and what i get is:

S -> L = R
L -> * L | id
R -> L R' | num R'
R' -> + R R' | ε

Now the problem that i have is that First and Follow set of R' rule have a common non-terminal ("+") and also FIRST(R) and FOLLOW(R') has a common non-terminal. So i wonder how to create the parsing table if there's this conflict. My question is: is there a way to solve this problem or simply this isn't an LL(1) grammar?

Thanks.

Answer 1

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:

1. Change left-associative operators (left-recursive productions) to being right-associative.

2. Left-factor the productions.

Thus, after left-recursion elimination, a left-associative grammar and a right-associative grammar are the same.

Answer 2

Your factoring is wrong. It should be (written as regular espressions):

$\begin{align*} R &\to (L \mid \operatorname{num}) (+ R)^* \end{align*}$

Thus the grammar with left recursion fixed is:

$\begin{align*} S &\to L = R \\ L &\to * L \mid \operatorname{id} \\ R &\to L R' \mid \operatorname{num} R' \\ R' &\to + R R' \mid \varepsilon \end{align*}$

You can check that this doesn't have conflicts.