# Is the following Grammar LL(1)

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)?

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$$