# Rules of First and Follow in Predictive Parsing

## Rules for First in Predictive Parsing

1. Suppose X is a terminalÂ thenÂ First(X) is just X!
2. Suppose there is a Production rule of X â†’ ÎµÂ thenÂ add Îµ to first(X)
3. Suppose there is a Production rule of X â†’ A1, A2…..AkÂ then add first(A1,A2..Ak) to first(X)
4. First(A1, A2..Ak) isÂ either
1. First(A1) (Suppose First(A1) doesn’t contain Îµ)
2. OR (Suppose First(A1) does contain Îµ) then First (A1, A2..Ak) is everything in First(A1) <except for Îµ > as well as everything in First(A2..Ak)
3. Suppose First(A1) First(A2)…..First(Ak) all contain Îµ then add Îµ to First(A1, A2..Ak) as well.

### Rule 1

 Production Rule / CFG First A â†’ lmn / opq / rst First(A) = { l , o , r }

### Rule 2

 Production Rule / CFG First X â†’ âˆˆ First(X) = { âˆˆ }

### Rule3

 Production Rule / CFG First X â†’ a First(X) = { a }

### Rule 4

• Rule 4.1: If âˆˆ does not belongs to First(E), then First(EF) = First(E)
• Rule 4.2: If âˆˆ belongs to First(E), then First(EF) = { First(E) â€“ âˆˆ } âˆª First(F)

Example of Rule 4.1:

If âˆˆ does not belongs to First(E), then First(EF) = First(E)

 Production Rule / CFG First S -> E F E -> g | o F -> f | âˆˆ First(S) = { g, o } First(E) = { g,Â  o } First(F) = { f, âˆˆ }

Example of Rule 4.2:

If âˆˆ belongs to First(E), then First(EF) = { First(E) â€“ âˆˆ } âˆª First(F)

 Production Rule / CFG First S -> E F E -> g | âˆˆ F -> f | o First(S) = { g, âˆˆ } First(E) = { g,Â  âˆˆ} First(F) = { f, o }

### Rule 5

For a production rule S â†’ EFG,

• Rule 5.1: If âˆˆ does not belongs to First(E), then First(S) = First(E)
• Rule 5.2: If âˆˆ belongs to First(E), then First(S) = { First(E) â€“ âˆˆ } âˆª First(FG)

Example of Rule 5.1:

If âˆˆ does not belongs to First(E), then First(S) = First(E)

Explanation: âˆˆ does not belongs to First(E) because First(E) are only { g,Â  0 }.

 Production Rule / CFG First S -> E F G E -> g | o F -> f | âˆˆ G -> k | l First(S) = { g, o } First(E) = { g,Â  0 } First(F) = { f, âˆˆ } First(G) = { k, l }

Example of Rule 5.2:

If âˆˆ belongs to First(E), then First(S) = { First(E) â€“ âˆˆ } âˆª First(FG)

Explanation: âˆˆ belongs to First(E) because First(E) are only { g,Â  âˆˆ }.

 Production Rule / CFG First S -> E F G E -> g | âˆˆ F -> f | âˆˆ G -> k | l First(S) = { g, âˆˆ } First(E) = { g,Â  âˆˆ } First(F) = { f, âˆˆ } First(G) = { k, l }

## Rules for Follow in Predictive Parsing

1. First, put \$ (the end of input marker) in Follow(S) (S is the start symbol)
2. Suppose there is a production rule of A â†’ aBb, (where a can be a whole string)Â thenÂ everything in FIRST(b) except for Îµ is placed in FOLLOW(B).
3. Suppose there is a production rule of A â†’ aB,Â thenÂ everything in FOLLOW(A) is in FOLLOW(B)
4. Suppose there is a production rule of A â†’ aBb, where FIRST(b) contains Îµ,Â thenÂ everything in FOLLOW(A) is in FOLLOW(B)

Rule 1:

For the start symbol S, place \$ in Follow(S).

 Production Rule / CFG Follow S -> a Follow(S) = {\$}

Rule 2:

For any production rule S -> a X,

Follow(X) = Follow(S)

 Production Rule / CFG Â Follow S -> a X Â Follow(S)= {\$}

### Rule 3

For any production rule S â†’ Î±XÎ²,

• If âˆˆ âˆ‰ First(Î²), then Follow(X) = First(Î²)
• If âˆˆ âˆˆ First(Î²), then Follow(X) = { First(Î²) â€“ âˆˆ } âˆª Follow(S)

CFG

S -> E F

E -> g | âˆˆ

F -> f | âˆˆ

Symbol First Follow
E g âˆˆ f âˆˆ
F f âˆˆ \$
S g âˆˆ \$

CFG

S -> E F G
E -> g | o
F -> f | âˆˆ
G -> k | l

Symbol First Follow
E g o f âˆˆ
F f âˆˆ k l
G k l \$
S g o \$

## Example of first and follow function

How to find the first and follow functions for the given CFG?

S â†’ aXZh

X â†’ cY

Y â†’ bY / âˆˆ

Z â†’ EF

E â†’ g / âˆˆ

F â†’ f / âˆˆ

The first and follow functions are given below;

First Functions

• First(S) = { a }
• First(X) = { c }
• First(Y) = { b , âˆˆ }
• First(Z) = { First(E) â€“ âˆˆ } âˆª First(F) = { g , f , âˆˆ }
• First(E) = { g , âˆˆ }
• First(F) = { f , âˆˆ }

• Follow(S) = { \$ }
• Follow(X) = { First(Z) â€“ âˆˆ } âˆª First(h) = { g , f , h }
• Follow(Y) = Follow(X) = { g , f , h }
• Follow(Z) = First(h) = { h }
• Follow(E) = { First(F) â€“ âˆˆ } âˆª Follow(Z) = { f , h }
• Follow(F) = Follow(Z) = { h }

## Example of first and follow function with Left Recursion

How to find the first and follow functions for the given CFG with Left Recursive production rules.?

S â†’ X

X â†’ aY / Xd

Y â†’ b

C â†’ t

The given grammar is left recursive. So, we first remove the left recursion from the given grammar.

After the elimination of left recursion, we get the following grammar.

S â†’ X

Xâ†’ aYXâ€™

Xâ€™ â†’ dXâ€™ / âˆˆ

Y â†’ b

C â†’ t

The first and follow functions are described below;

First Functions

• First(S) = First(X) = { a }
• First(X) = { a }
• First(Xâ€™) = { d , âˆˆ }
• First(Y) = { b }
• First(C) = { t }

• Follow(S) = { \$ }
• Follow(X) = Follow(S) = { \$ }
• Follow(Xâ€™) = Follow(X) = { \$ }
• Follow(Y) = { First(Aâ€™) â€“ âˆˆ } âˆª Follow(A) = { d , \$ }
• Follow(C) = NA

## Example of first and follow

How to find the first and follow functions for the given grammar?

S â†’ (F) / g

F â†’ S Fâ€™

Fâ€™ â†’ ,S Fâ€™ / âˆˆ

The first and follow functions are described below;

First Functions

• First(S) = { ( , g }
• First(F) = First(S) = { ( , g }
• First(Fâ€™) = { , , âˆˆ }

• Follow(S) = { \$ } âˆª { First(Fâ€™) â€“ âˆˆ } âˆª Follow(F) âˆª Follow(Fâ€™) = { \$ , , , ) }
• Follow(F) = { ) }
• Follow(Fâ€™) = Follow(F) = { ) }

## Example of first and follow

How to find the first and follow for the given grammar?

S â†’ XaAb / YbYa

X â†’ âˆˆ

Y â†’ âˆˆ

The first and follow functions are described below;

First Functions

• First(S) = { First(X) â€“ âˆˆ } âˆª First(a) âˆª { First(Y) â€“ âˆˆ } âˆª First(b) = { a , b }
• First(X) = { âˆˆ }
• First(Y) = { âˆˆ }

• Follow(S) = { \$ }
• Follow(X) = First(a) âˆª First(b) = { a , b }
• Follow(Y) = First(b) âˆª First(a) = { a , b }

## Example of first and follow function with Left Recursion

How to find the first and follow functions for the given CFG with Left Recursive production rules.?

Xâ†’ X + Y / Y

Y â†’ Y d F / F

F â†’ (X) / id

Solution-

The given grammar is left recursive. So, we first remove the left recursion from the given grammar.

After the elimination of left recursion, we get the following grammar.

X â†’ YXâ€™

Xâ€™ â†’ + YXâ€™ / âˆˆ

Y â†’ FYâ€™

Yâ€™ â†’ d FYâ€™ / âˆˆ

F â†’ (X) / id

The first and follow functions are described below;

First Functions

• First(X) = First(Y) = First(F) = { ( , id }
• First(Xâ€™) = { + , âˆˆ }
• First(Y) = First(F) = { ( , id }
• First(Yâ€™) = { d , âˆˆ }
• First(F) = { ( , id }

• Follow(X) = { \$ , ) }
• Follow(Xâ€™) = Follow(E) = { \$ , ) }
• Follow(Y) = { First(Xâ€™) â€“ âˆˆ } âˆª Follow(X) âˆª Follow(Xâ€™) = { + , \$ , ) }
• Follow(Yâ€™) = Follow(Y) = { + , \$ , ) }
• Follow(F) = { First(Yâ€™) â€“ âˆˆ } âˆª Follow(Y) âˆª Follow(Yâ€™) = { d , + , \$ , ) }

## Example of first and follow

How to find the first and follow functions for the given grammar?

S â†’ XCY / CbY / Ya

X â†’ da / YC

Y â†’ g / âˆˆ

C â†’ h / âˆˆ

The first and follow functions are described below;

First Functions-

• First(S) = { First(X) â€“ âˆˆ } âˆª { First(C) â€“ âˆˆ } âˆª First(Y) âˆª First(b) âˆª { First(Y) â€“ âˆˆ } âˆª First(a) = { d , g , h , âˆˆ , b , a }
• First(X) = First(d) âˆª { First(Y) â€“ âˆˆ } âˆª First(C) = { d , g , h , âˆˆ }
• First(Y) = { g , âˆˆ }
• First(C) = { h , âˆˆ }