# Computing FOLLOW sets for LL(1) grammar. Stuck on question

Calculate the FOLLOW sets for all the non terminals:

$S \rightarrow bEx \mid Db \mid b \mid F$

$D \rightarrow EDc \mid Y$

$E \rightarrow dED \mid dDY$

$Y \rightarrow ab \mid aDx \mid \varepsilon$

So I know that:

FOLLOW($S$) = $\{\$\}$since it doesn't appear anywhere FOLLOW($D$) =$\{b, a, x, c\}$, since it is followed by terminal$b$in$S$,$c$in$D$, FIRST($Y$) in$E$which is$\{a\}$($\varepsilon$not included), and$x$in$Y$FOLLOW($E$) =$\{x, c, a, d\}$, since it is followed by terminal$x$in$S$, FIRST($D$) in$D$which is$\{a, d, c\}$but how do I calculate FOLLOW($Y$)? It isn't followed by anything. I'm guessing since it's at the end of$D$and$E$its the union of their follow sets including$\$$since there's an \varepsilon? Have been stuck on this for a while, any help is HIGHLY appreciated. Thanks in advance for any input ## 2 Answers For posterity, the FOLLOW set of any non-terminal can be computed with the following rules (an example using these rules can be found here): 1. \$$ (the end of input symbol) is in FOLLOW($S$) where $S$ is the start symbol.
2. If $A \rightarrow \alpha B\beta$, then everything in FIRST($\beta$) except $\varepsilon$ is in FOLLOW($B$).
3. If we have $A \rightarrow \alpha B\beta$ as before and $\varepsilon$ is in FIRST($\beta$), then all of FOLLOW($A$) is in FOLLOW($B$).
4. If $A \rightarrow \alpha B$, then all of FOLLOW($A$) is in FOLLOW($B$).

So for $Y$, we need to apply rule $4$ (as you correctly guessed), so FOLLOW($Y$) $=$ FOLLOW($D$) $\cup$ FOLLOW($E$) $= \{a,b,c,d,x\}$ (I'm trusting your working on the two follow sets).

• This makes perfect sense to me but on my assignment 3 weeks ago with this question, for some reason I included $in Follow(Y) and got full marks for it. So I probably calculated Follow(D) or Follow(E) wrong? :p – eyes enberg Dec 29 '14 at 13:16 • Or maybe it's because Y has EPISILON ? – eyes enberg Dec 29 '14 at 14:32 • @eyesenberg should the$S \rightarrow F$rule actually be$S \rightarrow E$? This would put all of FOLLOW($S$) in FOLLOW($E$) and hence in FOLLOW($Y$). – Luke Mathieson Dec 29 '14 at 15:02 • Nevermind, spoke to other students and confirmed that her marking was wrong. Many thanks – eyes enberg Dec 29 '14 at 15:12 • @eyesenberg that's always a good way to get confused ;) – Luke Mathieson Dec 29 '14 at 15:13$FOLLOW\ (Y) = FOLLOW\ (D)FOLLOW\ (Y) = FOLLOW\ (E)$A general Rule of thumb is, for any grammar 1. S -> XAB 2. A -> BC 3. X -> Bt$ Follow (B) = Follow (S) $(Since there isn't anything after B in Production-1)$Follow (B) = First (C) $(Since C follows B in Production-2 and is a non-terminal)$Follow (B) = t \$ (since it follows B in Production-3 and is a terminal)

• Thanks for this. Just for clarification, this also means that Follow(C) = Follow(A) (since there isn't anything after C in production A) right? – eyes enberg Dec 29 '14 at 13:13
• @eyesenberg Absolutely. It is a generic rule and is applied whenever there isn't anything after a Non-terminal in a Production. So Follow(C) = Follow(A) – SimpleGuy Dec 29 '14 at 13:15
• @eyesenberg And if you think the answer helps you and can benefit others, you may choose to accept it ! – SimpleGuy Dec 29 '14 at 13:16