0
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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) = \{\$, +, *, )\}$? $\endgroup$
    – Haslo Vardos
    Jan 27, 2021 at 17:24
  • $\begingroup$ 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. $\endgroup$
    – rici
    Jan 27, 2021 at 20:30
  • $\begingroup$ As far as the correct value of FOLLOW(E) goes, it should be pretty easy to answer that by inspection of the grammar. FOLLOW doesn't have a hidden meaning: the FOLLOW set of a non-terminal is the set of terminals which might immediately follow the terminal in some sentential form derived from the grammar's start symbol. $\endgroup$
    – rici
    Jan 27, 2021 at 20:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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