1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.