[Solved]: Computing FOLLOW sets for a LL(1) grammar

Problem Detail: 

I am trying to learn compiler design. But I get confused when I have to deal with Follow set specifically for the empty word. I am trying to figure this out please help me with the same.

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

What I have

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 with the same. Also explain me if there is any formula which I could apply in such cases.

Asked By : Kunj

Answered By : Lavin Sharma

Follow Set of something translates in meaning to what symbol can come next in the string we are trying to read with the grammar rules the machine has?

Lets 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 the Follow set of A,
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)

EDIT:
In your questions 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').

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/24638