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:
 
Watch on YouTube: https://www.youtube.com/watch?v=rnzGbQ3VjMU 


(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:

Watch on YouTube: https://www.youtube.com/watch?v=rnzGbQ3VjMU
 

Check Other Posts on Compiler

Next: Intermediate code generation for sample language using LEX and YACC

Previous: Concurrent YACC to Parse Input Text File