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.

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,