Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question.If this question can be reworded to fit the rules in the help center, please edit the question.

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

We're looking for long answers that provide some explanation and context. Don't just give a one-line answer; explain why your answer is right, ideally with citations. Answers that don't include explanations may be removed.

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

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