First and Follow | 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.

 

First Function-

 

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

 

Example-

 

Consider a production rule-

A → abc / def / ghi

Then,

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 expand the rule 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:

 

  • It is recommended to Eliminate Left Recursion from the grammar if present before calculating the first and follow functions.

 

Note-03:

 

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

 

PRACTICE PROBLEMS BASED ON CALCULATING FIRST AND FOLLOW FUNCTIONS-

 

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-

 

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-

 

  • Since 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, let us calculate the first and follow functions-

 

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-

 

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-

 

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-

 

Calculate the first and follow functions for the given grammar-

 

E → E + T / T

T → T x F / F

F → (E) / id

 

Solution-

 

  • Since 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, let us calculate the first and follow functions-

 

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-

 

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 of How to calculate First and Follow Functions,

Watch this video lecture

 

Get more notes and other study material of Compiler Design.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Summary
First and Follow | Compiler Design
Article Name
First and Follow | Compiler Design
Description
First and Follow sets are needed so that the parser can properly apply the needed production rule at the correct position. Rules for calculating First and Follow Functions.
Author
Publisher Name
Gate Vidyalay
Publisher Logo
Liked this article? Share it with your friends and classmates now-