I am trying to learn compiler design. But I get confused when I have to deal with computing the follow set specifically for the empty word.

Given the grammar:

A-> Aa|b
B-> Bc|d
C-> Ce|f

I've come up with the following first and follow sets:

1 S->ABC   First(1)-{b}
2 A->bA'   First(2)-{b}
3 A'->aA'  First(3)-{a} 
4 A'->E    Follow(4)- ??
5 B->dB'   First(5)-{d}
6 B'->cB'  First(6)-{c}
7 B'->E    Follow(7)- ??
8 C->fC'   First(8)-{f}
9 C'->eC'  First(9)-{e}
10 C'->E   Follow(10)- ??

Please help me determine the follow sets I've indicated with ??. Is there a formula I can use to determine the follow sets?

  • 1
    $\begingroup$ What is the definition of FOLLOW sets? $\endgroup$ – Raphael May 12 '14 at 8:27

The follow set of something translates to asking: what symbol can come next in the string we are trying to read with the grammar rules the machine has?

Let's say we take a string "abba". The input tape symbol will end the string with $ as the delimiter. So we can say that 'a', 'b', 'b', 'a' and '$' are the symbols that the read/write head of the parser will see while evaluating this string. I am taking the below production rules for this grammar.


The string "abba" can be evaluated in the following manner:


In the above case, Follow(A) = {b,$}.

'b' is part of the set because B's production follows A's production, S->AB, and whatever is the first letter that B produces will follow the last letter A produces.

Similarly, $ is part of the set because of B's epsilon production. When B is evaluated using rule B->E, then for Follow(A) there is no first letter produced by B.

In such a case where the Follow(A) is an epsilon production,

S->AE | using B->E

Then Follow(A) becomes Follow(S) which is $.

If you look at the string "abba", once the last a is read the only symbol that can come after the string is $.

As a generalization, if X->ABC and C->E, then Follow(B) = Follow(X).

In your question's example, evaluating Follow(A') results in only two possibilities where A' is on the RHS and can have a following symbol. Below are the two productions that can result:


Unfortunately, out of the two one is Follow(A') = Follow(A') as per the rule I have mentioned in last line of the answer.

Hence we can only consider the other follow which is

Follow(A') = Follow(A)


Follow(A) = First(B)

In a practical sense, if we have



A-> bA'

Then whenever we have an A production, it will further lead to either A -> baA' or A->b (if we take A'->E).

In both cases the only thing that can follow A' is whatever is the first of B.

In a similar manner we can compute the same for Follow(B') and Follow(C').

  • $\begingroup$ thanks Lavin, you have explained well. But can u tell me a perfect formula for this. So If I understand correctly then in above example. A'->E Follow(4)- {d,$} B'->E Follow(7)- {f,$} C'->E Follow(10)- {$} $\endgroup$ – Kunj May 12 '14 at 12:09
  • $\begingroup$ I have added an edit to the answer with points related to your question and I hope it helps. $\endgroup$ – lds May 12 '14 at 13:41

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.