Tag: How to Calculate First and Follow in Compiler Design

First and Follow | Solved Examples

Compiler Design

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 → Y1Y2Y3,

 

Calculating First(X)

 

  • If ∈ ∉ First(Y1), then First(X) = First(Y1)
  • If ∈ ∈ First(Y1), then First(X) = { First(Y1) – ∈ } ∪ First(Y2Y3)

 

Calculating First(Y2Y3)

 

  • If ∈ ∉ First(Y2), then First(Y2Y3) = First(Y2)
  • If ∈ ∈ First(Y2), then First(Y2Y3) = { First(Y2) – ∈ } ∪ First(Y3)

 

Similarly, we can make expansion for any production rule X → Y1Y2Y3…..Yn.

 

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,

Watch this Video Lecture

 

Next Article- Syntax Trees

 

Get more notes and other study material of Compiler Design.

Watch video lectures by visiting our YouTube channel LearnVidFun.