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)
1
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.
2
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 }
3
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) = { $ }
4
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-
5
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→TxF/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 , ∈ }
6
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
