Is the following Grammar LL(1)

Question

I was given the following grammar

$S \rightarrow S ( S ) S\mid \epsilon$

First I was asked to eliminate left recursion, yielding me the following :

$S \rightarrow S' $

$S' \rightarrow (S)SS' \mid \epsilon$

I was then asked If the grammar is LL(1). So I computed the FIRST and FOLLOW sets shown below:

$\mathrm{FIRST}(S) = \mathrm{FIRST}(S') = \{ ( , \epsilon \}$,

$\mathrm{FOLLOW}(S) = \mathrm{FOLLOW}(S') = \{ \$, ( , ) \}$.

I now tried building the LL(1) parsing table $M$ as follow:

Since we have production $S \rightarrow S' $ and $\mathrm{FIRST}(S') = \{ ( , \epsilon \}$, the table's entry $M [ S , ( ] = S \rightarrow S'$.

But since $\epsilon$ belongs in $\mathrm{FIRST}(S')$ then for each element $b$ in $\mathrm{FOLLOW}(S)$,

$M [ S , b ] = S \rightarrow S' $.

This would entail that $M [ S , ( ] = S \rightarrow S' $.

Since the entry was already populated, is this a conflict? If yes, what kind?

Or since the 2 productions are the same we can just ignore it?

Also if the second case is the right one, is the grammar LL(1)?

Answer 1

Since the entry was already populated, is this a conflict? If yes, what kind? Or since the 2 productions are the same we can just ignore it? Also if the second case is the right one, is the grammar LL(1)?

Although the entry was populated, this is not a conflict since the same rule is put into the table entry $M [ S , ( ]$, which can be ignored.

However, the grammar is not LL(1). This can be seen from either of the following.

• The string ()() has following two different leftmost derivations. $$S\rightarrow S'\rightarrow (S)SS'\rightarrow (S')SS'\rightarrow ()SS'\rightarrow()S'S'\\ \rightarrow()(S)SS'S'\rightarrow()(S')SS'S'\rightarrow()()SS'S'\\ \rightarrow()()S'S'S'\rightarrow()()S'S'\rightarrow()()S'\rightarrow()()$$ $$S\rightarrow S'\rightarrow (S)SS'\rightarrow (S')SS'\rightarrow ()SS'\rightarrow()S'S'\\ \rightarrow()S'\rightarrow()(S)SS'\rightarrow()(S')SS'\rightarrow()()SS'\\ \rightarrow()()S'S'\rightarrow()()S'\rightarrow()()$$

• When we build the table entry $M[S', (]$, it will have two entries, $S' \rightarrow ( S ) S S'$ and $S' \rightarrow\epsilon$.

Although neither the new grammar nor the original grammar is LL(1), the language generated by either of them is LL(1) since it is generated by following LL(1) grammar.

$$S \rightarrow (S)S \mid \epsilon $$