# Computing FOLLOW sets of left recursive grammar

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

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

• Is it correct that $Follow(E)$ in right hand side of expression $Follow(E) = First(+E) \cup First(*E) \cup First\bigl()\bigr) \cup Follow(E) \cup$ {\$} is redundant and$Follow(E) = \{\$, +, *, )\}$? – Haslo Vardos Jan 27 at 17:24
• I'm not sure that "redundant" is exactly the right word. Consider the equation $X = X \cup Y$. That is true iff $Y \subset X$, which is not the same thing as $X = Y$. But suppose it's all we have to go on, so all we know is that $X = X \cup Y$ (or, in other words, $Y \subset X$). And suppose we also know the value of $Y$. We clearly cannot provide a definite answer for the value of $X$, as we could in the case that we were told that $X = Y$. But we can say what is the least (i.e. smallest) set which could satisfy the equation, which is $Y$. That's why we say the algo is least fixed-point. – rici Jan 27 at 20:30