Computing FOLLOW sets of left recursive grammar

Question

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?

Answer 1

The cited algorithm for FIRST and FOLLOW is a least fixed-point algorithm; recursive inclusion of the same set is a no-op.

That's clearly stated in the Dragon Book's description of this algorithm, which involves repeatedly evaluating the equations until no additional elements are added to any set during an iteration.

The algorithm works without the necessity to remove left recursion (and recursive equations in the FOLLOW set are possible without left recursion in the grammar). Left recursion elimination is not isomorphic, by the way; it's not a reversible procedure and the original grammar can not be recovered.