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→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 , ∈ }
 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 }