[Solved]: Computing FOLLOW sets for LL(1) grammar. Stuck on question

Problem Detail: 

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

Asked By : eyes enberg

Answered By : Luke Mathieson

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).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/35739