**First and Follow-**

First and Follow sets are needed so that the parser can properly apply the needed production rule at the correct position. |

In this article, we will learn how to calculate first and follow functions.

**First Function-**

First(α) is a set of terminal symbols that begin in strings derived from α. |

**Example-**

Consider the production rule-

A → abc / def / ghi

Then, we have-

First(A) = { a , d , g }

**Rules For Calculating First Function-**

**Rule-01:**

For a production rule X → ∈,

First(X) = { ∈ }

**Rule-02:**

For any terminal symbol ‘a’,

First(a) = { a }

**Rule-03:**

For a production rule X → Y_{1}Y_{2}Y_{3},

**Calculating First(X)**

- If ∈ ∉ First(Y
_{1}), then First(X) = First(Y_{1}) - If ∈ ∈ First(Y
_{1}), then First(X) = { First(Y_{1}) – ∈ } ∪ First(Y_{2}Y_{3})

**Calculating First(Y**_{2}Y_{3})

_{2}Y

_{3})

- If ∈ ∉ First(Y
_{2}), then First(Y_{2}Y_{3}) = First(Y_{2}) - If ∈ ∈ First(Y
_{2}), then First(Y_{2}Y_{3}) = { First(Y_{2}) – ∈ } ∪ First(Y_{3})

Similarly, we can make expansion for any production rule X → Y_{1}Y_{2}Y_{3}…..Y_{n}.

**Follow Function-**

Follow(α) is a set of terminal symbols that appear immediately to the right of α. |

**Rules For Calculating Follow Function-**

**Rule-01:**

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

**Rule-02:**

For any production rule A → αB,

Follow(B) = Follow(A)

**Rule-03:**

For any production rule A → αBβ,

- If ∈ ∉ First(β), then Follow(B) = First(β)
- If ∈ ∈ First(β), then Follow(B) = { First(β) – ∈ } ∪ Follow(A)

**Important Notes-**

**Note-01:**

- ∈ may appear in the first function of a non-terminal.
- ∈ will never appear in the follow function of a non-terminal.

**Note-02:**

- Before calculating the first and follow functions, eliminate
**Left Recursion**from the grammar, if present.

**Note-03:**

- We calculate the follow function of a non-terminal by looking where it is present on the RHS of a production rule.

**Also Read-** **Left Factoring**

**PRACTICE PROBLEMS BASED ON CALCULATING FIRST AND FOLLOW-**

**Problem-01:**

Calculate the first and follow functions for the given grammar-

S → aBDh

B → cC

C → bC / ∈

D → EF

E → g / ∈

F → f / ∈

**Solution-**

The first and follow functions are as follows-

**First Functions-**

- First(S) = { a }
- First(B) = { c }
- First(C) = { b , ∈ }
- First(D) = { First(E) – ∈ } ∪ First(F) = { g , f , ∈ }
- First(E) = { g , ∈ }
- First(F) = { f , ∈ }

**Follow Functions-**

- Follow(S) = { $ }
- Follow(B) = { First(D) – ∈ } ∪ First(h) = { g , f , h }
- Follow(C) = Follow(B) = { g , f , h }
- Follow(D) = First(h) = { h }
- Follow(E) = { First(F) – ∈ } ∪ Follow(D) = { f , h }
- Follow(F) = Follow(D) = { h }

**Problem-02:**

Calculate the first and follow functions for the given grammar-

S → A

A → aB / Ad

B → b

C → g

**Solution-**

We have-

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

After eliminating left recursion, we get the following grammar-

S → A

A → aBA’

A’ → dA’ / ∈

B → b

C → g

Now, the first and follow functions are as follows-

**First Functions-**

- First(S) = First(A) = { a }
- First(A) = { a }
- First(A’) = { d , ∈ }
- First(B) = { b }
- First(C) = { g }

**Follow Functions-**

- Follow(S) = { $ }
- Follow(A) = Follow(S) = { $ }
- Follow(A’) = Follow(A) = { $ }
- Follow(B) = { First(A’) – ∈ } ∪ Follow(A) = { d , $ }
- Follow(C) = NA

**Problem-03:**

Calculate the first and follow functions for the given grammar-

S → (L) / a

L → SL’

L’ → ,SL’ / ∈

**Solution-**

The first and follow functions are as follows-

**First Functions-**

- First(S) = { ( , a }
- First(L) = First(S) = { ( , a }
- First(L’) = { , , ∈ }

**Follow Functions-**

- Follow(S) = { $ } ∪ { First(L’) – ∈ } ∪ Follow(L) ∪ Follow(L’) = { $ , , , ) }
- Follow(L) = { ) }
- Follow(L’) = Follow(L) = { ) }

**Problem-04:**

Calculate the first and follow functions for the given grammar-

S → AaAb / BbBa

A → ∈

B → ∈

**Solution-**

The first and follow functions are as follows-

**First Functions-**

- First(S) = { First(A) – ∈ } ∪ First(a) ∪ { First(B) – ∈ } ∪ First(b) = { a , b }
- First(A) = { ∈ }
- First(B) = { ∈ }

**Follow Functions-**

- Follow(S) = { $ }
- Follow(A) = First(a) ∪ First(b) = { a , b }
- Follow(B) = First(b) ∪ First(a) = { a , b }

**Problem-05:**

Calculate the first and follow functions for the given grammar-

E → E + T / T

T → T x F / F

F → (E) / id

**Solution-**

We have-

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

After eliminating left recursion, we get the following grammar-

E → TE’

E’ → + TE’ / ∈

T → FT’

T’ → x FT’ / ∈

F → (E) / id

Now, the first and follow functions are as follows-

**First Functions-**

- First(E) = First(T) = First(F) = { ( , id }
- First(E’) = { + , ∈ }
- First(T) = First(F) = { ( , id }
- First(T’) = { x , ∈ }
- First(F) = { ( , id }

**Follow Functions-**

- Follow(E) = { $ , ) }
- Follow(E’) = Follow(E) = { $ , ) }
- Follow(T) = { First(E’) – ∈ } ∪ Follow(E) ∪ Follow(E’) = { + , $ , ) }
- Follow(T’) = Follow(T) = { + , $ , ) }
- Follow(F) = { First(T’) – ∈ } ∪ Follow(T) ∪ Follow(T’) = { x , + , $ , ) }

**Problem-06:**

Calculate the first and follow functions for the given grammar-

S → ACB / CbB / Ba

A → da / BC

B → g / ∈

C → h / ∈

**Solution-**

The first and follow functions are as follows-

**First Functions-**

- First(S) = { First(A) – ∈ } ∪ { First(C) – ∈ } ∪ First(B) ∪ First(b) ∪ { First(B) – ∈ } ∪ First(a) = { d , g , h , ∈ , b , a }
- First(A) = First(d) ∪ { First(B) – ∈ } ∪ First(C) = { d , g , h , ∈ }
- First(B) = { g , ∈ }
- First(C) = { h , ∈ }

**Follow Functions-**

- Follow(S) = { $ }
- Follow(A) = { First(C) – ∈ } ∪ { First(B) – ∈ } ∪ Follow(S) = { h , g , $ }
- Follow(B) = Follow(S) ∪ First(a) ∪ { First(C) – ∈ } ∪ Follow(A) = { $ , a , h , g }
- Follow(C) = { First(B) – ∈ } ∪ Follow(S) ∪ First(b) ∪ Follow(A) = { g , $ , b , h }

To gain better understanding about calculating first and follow functions,

**Next Article-** **Syntax Trees**

Get more notes and other study material of **Compiler Design**.

Watch video lectures by visiting our YouTube channel **LearnVidFun.**