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):
- $\$$ (the end of input symbol) is in FOLLOW($S$) where $S$ is the start symbol.
- If $A \rightarrow \alpha B\beta$, then everything in FIRST($\beta$) except $\varepsilon$ is in FOLLOW($B$).
- 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$).
- 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
0 comments:
Post a Comment
Let us know your responses and feedback