Take the 2-minute tour ×

I'm studying for a Compiler Construction module I'm doing and I have a sample question as follows:

Calculate the FIRST and FOLLOW sets for the following grammar..
S -> uBDz
B -> Bv
B -> w
D -> EF
E -> y
E -> ε 
F -> x
F -> ε

I have tried to figure it out so far but I'm a bit unsure if I'm correct. Could someone verify if I'm doing it right, and if not, what am I missing? My answer is below:

    FIRST   |   FOLLOW

S |  {u}    |   {$}
B |  {w}    | {y,x,v,z}
D | {y,ε,x} |   {z}
E |  {y,ε}  |  {x,z}
F |  {x,ε}  |   {z}
share|improve this question

closed as unclear what you're asking by gnat, MichaelT, GlenH7, Bart van Ingen Schenau, Martijn Pieters Feb 17 at 22:14


I've checked your solution by hand and ran it in my parsing library, and it is correct. I'm not entirely sure how to answer your question. –  Alex ten Brink Jan 19 '13 at 18:31
Thanks for the confirmation on it being correct. I think I've figured it out but I'm in the same boat as you, can't really explain it. I id my exam and it seemed to go well anyway! –  Aimee Jones Jan 19 '13 at 22:54
When I said "I'm not entirely sure how to answer your question", I meant that I'm not sure how to 'prove' that your solution is really correct. I'm quite sure they are correct though, having implemented a compiler and multiple parsing algorithms myself. Anyway, I hope you did well on your exam. –  Alex ten Brink Jan 19 '13 at 23:39
add comment

2 Answers

up vote 0 down vote accepted

I was using this page as a guide for anyone that's finding it difficult in future. It provides good step by step instructions for calculating the first and follow sets.

share|improve this answer


add comment

i think the First(D)={y,epsilon}.there may be no x because u have to take only the first letter to calculate first and in D it is E and then as E is a non-terminal we have to see the first term of the non-terminal and for E there are two terminals {y,epsilon}.

share|improve this answer
For D, if E = epsilon, then F becomes the First of D. The First of F = {x,epsilon}. Since we already have epsilon from E then we just add x to the First set of D, making it {y,x,epsilon} from what I can remember. I did this for an exam ages ago and I think this was how the lecturer taught it anyway. –  Aimee Jones Nov 12 '13 at 12:32
add comment
