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 }
0 Comments