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,
Comments