## Wednesday, 5 August 2015

### How to find FIRST and FOLLOW of a grammar with examples

In this post, we will see how to find FIRST and FOLLOW of a grammar. I have also given some examples for better understanding.

What is FIRST of a Non-Terminal of a Grammar:
A Non-terminal can generate a sequence of terminals(non-empty string) or empty string. The collection of initial terminal of all these strings is called a FIRST of a Non-terminal of a Grammar.

Watch following Video:

(say, LHS stands for Left Hand Side of grammar production, RHS stands for Right Hand Side of grammar production and X is any Non-Terminal in grammar)

How to find set FIRST(X):
For all productions whose LHS is X,
1. If RHS starts with terminal, then add that terminal to the set FIRST(X).
2. If RHS is ϵ, then add ϵ to the set FIRST(X).
3. If RHS starts with Non-Terminal(say Y), then add FIRST(Y) to the set FIRST(X).  If FIRST(Y) includes ϵ, then, also add FIRST(RHS except Y) to the set FIRST(X).

What is FOLLOW of a Non-Terminal of a Grammar:
In a derivation process, the collection of initial terminal(i.e. FIRST) of a string which follows Non-terminal, is called FOLLOW of that Non-terminal.
For finding FOLLOW set of a Non-Terminal, check in RHS of all productions which consist of that Non-Terminal.

How to find set FOLLOW(X):
1. If X is "Start" symbol, then add \$ to the set FOLLOW(X). (Reason: Each string generated from grammar is assumed that it ends in \$. For e.g. abc\$ or a+b\$. As that string can be generated from the Start symbol, Start symbol is followed by \$).
2. If in any RHS, X is followed by terminal (say t), then add t to the set FOLLOW(X).
3. If in any RHS, X is followed by Non-terminal (say Y), then add FIRST(Y) except ϵ to the set FOLLOW(X). If FIRST(Y) contains ϵ, then you have to also add FIRST of remaining part of RHS after Y to the set FOLLOW(X). If remaining part of RHS after Y is empty, then add FOLLOW(LHS) to the set FOLLOW(X).
4. If X is the last symbol in any RHS (For e.g. Z->wX), then add FOLLOW(LHS) i.e. FOLLOW(Z) to the set FOLLOW(X). (Reason: RHS is derived from LHS. So whatever follows RHS, also follows LHS. As X is last symbol in RHS, FOLLOW(X) includes FOLLOW(LHS)).

Examples:

1. Grammar:

S->xyz/aBC
B->c/cd
C->eg/df

FIRST(S)={x,a}
FIRST(B)={c}
FIRST(C)={e,d}

FOLLOW(S)={\$}
FOLLOW(B)={e,d}
FOLLOW(C)={\$}

2. Grammar:

S->ABCDE
A->a/ϵ
B->b/ϵ
C->c
D->d/ϵ
E->e/ϵ

FIRST(S)={a,b,c}
FIRST(A)={a,ϵ}
FIRST(B)={b,ϵ}
FIRST(C)={c}
FIRST(D)={d,ϵ}
FIRST(E)={e,ϵ}

FOLLOW(S)={\$}
FOLLOW(A)={b,c}
FOLLOW(B)={c}
FOLLOW(C)={d,e,\$}
FOLLOW(D)={e,\$}
FOLLOW(E)={\$}

3. Grammar:

S->AB
A->ϵ
B->ϵ

FIRST(S)={ϵ
FIRST(A)={ϵ}
FIRST(B)={ϵ}

FOLLOW(S)={\$}
FOLLOW(A)={\$}
FOLLOW(B)={\$}

4. Grammar:

S->Bb/Cd
B->aB/ϵ
C->cC/ϵ

FIRST(S)={a,b,c,d}
FIRST(B)={a,ϵ}
FIRST(C)={c,ϵ}

FOLLOW(S)={\$}
FOLLOW(B)={b}
FOLLOW(C)={d}

5. Grammar:

S->(S)/ϵ

FIRST(S)={(,ϵ}

FOLLOW(S)={\$,)}

6. Grammar:

S->AB/C
A->D/a/ϵ
B->b
C->ϵ
D->d

FIRST(S)={d,a,b,ϵ}
FIRST(A)={d,a,ϵ}
FIRST(B)={b}
FIRST(C)={ϵ}
FIRST(D)={d}

FOLLOW(S)={\$}
FOLLOW(A)={b}
FOLLOW(B)={\$}
FOLLOW(C)={\$}
FOLLOW(D)={b}

7. Grammar:

S->ASB/d
A->a
B->AB/b/ϵ

FIRST(S)={a,d}
FIRST(A)={a}
FIRST(B)={a,b,ϵ}

FOLLOW(S)={\$,a,b}
FOLLOW(A)={a,d,b,\$}
FOLLOW(B)={\$,a,b}

8. Grammar:

E->TE'
E'->+TE'/ϵ
T->FT'
T'->*FT'/ϵ
F->id/(E)

FIRST(E)={id,(}
FIRST(E')={+,ϵ
FIRST(T)={id,(}
FIRST(T')={*,ϵ
FIRST(F)={id,(}

FOLLOW(E)={\$,)}
FOLLOW(E')={\$,)
FOLLOW(T)={+,),\$}
FOLLOW(T')={+,),\$
FOLLOW(F)={*,+,),\$

9. Grammar:

X->YZ
Y->m/n/ϵ
Z->m

FIRST(X)={m,n}
FIRST(Y)={m,n,ϵ}
FIRST(Z)={m}

FOLLOW(X)={\$}
FOLLOW(Y)={m}
FOLLOW(Z)={\$}

Watch following Video:

1. 1. 2. I usually don't comment but i have my exam today and found this post really helpful. Thanks :)

1. 3. DO someone have finding follow code in C++ or in C?

1. 4. Excellent examples!
Many thanks to the author of the note and clear position, that's cool

1. 5. Just hilarious thanks a lot

1. 6. Very helpful..All the examples are excellent for clearing the concept. Thanks to the writer. :)

1. 7. Very nice .thank you

1. 8. This was very helpful, thank you!

1. 