# Rules of First and Follow in Predictive Parsing

By Prof. Fazal Rehman Shamil

# 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 , ∈ } Prof.Fazal Rehman Shamil (Available for Professional Discussions)