I'm aware of how $FIRST$ and $FOLLOW$ sets are used to construct a parsing table for $LL(1)$ grammars.

However, I've encountered this statement from my notes:

With $\epsilon$ productions in the grammar, we may have to look beyond the current non-terminal to what can come after it

In my opinion, this suggests that $FOLLOW$ is not necessary for $LL(1)$ grammars that have no $\epsilon$ transition. Am I wrong? And if I'm not, why is this the case?



That's correct for $LL(1)$: if there are no $\epsilon$ productions, the $LL$ parser-generation algorithm will never consult $FOLLOW$, because it only does that if it finds $\epsilon$ in the $FIRST$ set for the first non-terminal in the right-hand side of a production. (So it might not need the $FOLLOW$ sets even if there are some $\epsilon$ productions, provided that none of those productions occur at the beginning of a right-hand side.)

The observation doesn't generalise well to other values of $k$. You'll need $FOLLOW_k(\alpha)$ if any production can derive a string whose length is less than $k$.


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.