First and Follow

The construction of a predictive parser is aided by two functions associated with a grammar G. These functions, FIRST and FOLLOW, allow us to fill in the entries of a predictive parsing table for G, whenever possible. Sets of tokens yielded by the FOLLOW function can also be used as synchronizing tokens during panic-mode error recovery.

1. FIRST(a)

First(a) = set of terminals that start a string of terminals derived from a.

Apply following rules until no terminal or ε can be added

1. If t  ∈ T, then First( t ) = { t }.  

2. If X ∈ N and X → ε exists (nullable), then add ε to First( X ).

3. If X ∈ N and X →  Y1Y2Y3… Ym, where Y1, Y2, Y3, ... Ym are non‐terminals, then:     for each, I from 1 to m     if Y1 … Yi‐1 are all nullable (or if i = 1)      First( X ) = First( X ) ∪ First( Yi )

2. FOLLOW (a) 

Apply the following rules until no terminal or e can be added

1. $  ∈ Follow( S ), where S is the start symbol.

2. Look at the occurrence of a non‐terminal on the right-hand side of a production which is followed by something If A → a B b, then First( b ) ‐ {e} ⊆ Follow( B )

3. Look at N on the RHS that is not followed by anything, if (A → a B) or (A → a B b and ε  First( b )), then Follow( A ) ⊆  Follow( B )

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 }