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

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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).

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

Improve this answer
$\endgroup$
3
  • $\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, 2014 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, 2014 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, 2014 at 13:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.