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

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.

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

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

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.

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

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

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)={$}

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)={$}

S->AB

A->ϵ

B->ϵ

FIRST(S)={ϵ}

FIRST(A)={ϵ}

FIRST(B)={ϵ}

FOLLOW(S)={$}

FOLLOW(A)={$}

FOLLOW(B)={$}

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}

S->(S)/ϵ

FIRST(S)={(,ϵ}

FOLLOW(S)={$,)}

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}

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}

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)={*,+,),$}

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

__Intermediate code generation for sample language using LEX and YACC__*Next:*__Concurrent YACC to Parse Input Text File__*Previous:*
nice :)

ReplyDeleteThank You.

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

ReplyDeleteDO someone have finding follow code in C++ or in C?

ReplyDeletePlease check this link https://www.geeksforgeeks.org/program-calculate-first-follow-sets-given-grammar/

DeleteExcellent examples!

ReplyDeleteMany thanks to the author of the note and clear position, that's cool

Just hilarious thanks a lot

ReplyDeleteVery helpful..All the examples are excellent for clearing the concept. Thanks to the writer. :)

ReplyDeleteThank You.

DeleteVery nice .thank you

ReplyDeleteThis was very helpful, thank you!

ReplyDeleteThank You.

Delete