0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – eyes enberg Dec 29 '14 at 13:16
  • $\begingroup$ Or maybe it's because Y has EPISILON ? $\endgroup$ – eyes enberg Dec 29 '14 at 14:32
  • $\begingroup$ @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$). $\endgroup$ – Luke Mathieson Dec 29 '14 at 15:02
  • $\begingroup$ Nevermind, spoke to other students and confirmed that her marking was wrong. Many thanks $\endgroup$ – eyes enberg Dec 29 '14 at 15:12
  • $\begingroup$ @eyesenberg that's always a good way to get confused ;) $\endgroup$ – Luke Mathieson Dec 29 '14 at 15:13
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – eyes enberg Dec 29 '14 at 13:13
  • $\begingroup$ @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) $\endgroup$ – SimpleGuy Dec 29 '14 at 13:15
  • $\begingroup$ @eyesenberg And if you think the answer helps you and can benefit others, you may choose to accept it ! $\endgroup$ – SimpleGuy Dec 29 '14 at 13:16

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.