0
$\begingroup$

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.

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

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

$\endgroup$
  • $\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$ – Lavin Sharma 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.