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

ignougroup
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 Bbeta$, then everything in FIRST($beta$) except $varepsilon$ is in FOLLOW($B$).
  3. If we have $A rightarrow alpha Bbeta$ 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