Left recursive ambiguous expression Grammar:
$E \rightarrow E+E \mid E*E \mid (E) \mid \mathbf i\mathbf d$
I tried computing FIRST and FOLLOW sets of both left recursive grammar and after eliminating left recursion. In both the cases, I was able to compute FIRST sets successfully, but not FOLLOW sets. I have shown the work I did to compute the two sets below.
Note that to compute FIRST and FOLLOW sets, I followed the rules given in Compilers Principles, Techniques, & Tools Second Edition or The Dragon book
I computed FIRST and FOLLOW sets of left recursive grammar following this post.
Computing FIRST sets:
$First(E)$ = $First(E+E)$ $\cup$ $First(E*E)$ $\cup$ $First\bigl((E)\big)$ $\cup$ $First(id)$
Since $\epsilon\not\in\text{First}(E)$, ignore the rules $E$ $\rightarrow$ $E+E\mid E*E$
Therefore, $First(E) = \{(, id\}$
Computing the FOLLOW sets:
$Follow(E) = First(+E) \cup First(*E) \cup First\bigl()\bigr) \cup Follow(E) \cup$ {\$}
See that there is a recursive $Follow(E)$. I am not sure how to resolve this. I know that, a set does not include duplicates, so no matter how many times I union $Follow(E)$ with itself, the result does not change, though I am not sure if my argument even applies in this case. How do I proceed from here?
Since I was stuck, I tried computing FIRST and FOLLOW sets after eliminating left recursion.
Grammar after eliminating left recursion:
$E \rightarrow (E)E' \mid \mathbf i\mathbf dE'$
$E' \rightarrow +EE' \mid *EE' \mid \epsilon$
Computing the FIRST sets:
$First(E') = First(+EE') \cup First(*EE') \cup \{\epsilon\}$
Therefore, $Fisrt(E') = \{\epsilon, +, *\}$
$First(E) = First\bigl((E)E'\bigr) \cup First(\mathbf i\mathbf dE')$
Therefore, $First(E) = \{(, id\}$
Computing FOLLOW sets:
$Follow(E)$ = {\$} $\cup First\bigl()E'\bigr) \cup Follow(E')$
$Follow(E') = Follow(E) \cup Follow(E')$
Again I am stuck with the recursion issue. How do I proceed from here?
I suppose FIRST and FOLLOW sets do not change with elimination of left recursion, or do they? If yes, should one always calculate the sets after elimination of left recursion?