# Computing FOLLOW sets for a LL(1) grammar

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:

S-> ABC
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?

• What is the definition of FOLLOW sets? – 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.

S->AB
A->ab|a
B->baB|E


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

S->AB
->abB
->abbaB
->abbaE


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:

A->bA'
A'->aA'


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)


i.e.

Follow(A) = First(B)


In a practical sense, if we have

S->ABC


and

A-> bA'
A'->aA'|E


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').

• 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)- {\$} – Kunj May 12 '14 at 12:09
• I have added an edit to the answer with points related to your question and I hope it helps. – lds May 12 '14 at 13:41