Rule 5.1: If ∈ does not belongs to First(E), then First(S) = First(E)
Rule 5.2: If ∈ belongs to First(E), then First(S) = { First(E) – ∈ } ∪ First(FG)
Example of Rule 5.1:
If ∈ does not belongs to First(E), then First(S) = First(E)
Explanation: ∈ does not belongs to First(E) because First(E) are only { g, 0 }.
Example of Rule 5.2:
If ∈ belongs to First(E), then First(S) = { First(E) – ∈ } ∪ First(FG)
Explanation: ∈ belongs to First(E) because First(E) are only { g, ∈ }.
First, put $ (the end of input marker) in Follow(S) (S is the start symbol)
Suppose there is a production rule of A → aBb, (where a can be a whole string) then everything in FIRST(b) except for ε is placed in FOLLOW(B).
Suppose there is a production rule of A → aB, then everything in FOLLOW(A) is in FOLLOW(B)
Suppose there is a production rule of A → aBb, where FIRST(b) contains ε, then everything in FOLLOW(A) is in FOLLOW(B)
Rule 1:
For the start symbol S, place $ in Follow(S).
Production Rule / CFG
Follow
S -> a
Follow(S) = {$}
Rule 2:
For any production rule S -> a X,
Follow(X) = Follow(S)
Production Rule / CFG
Follow
S -> a X
Follow(S)= {$}
Rule 3
For any production rule S → αXβ,
If ∈ ∉ First(β), then Follow(X) = First(β)
If ∈ ∈ First(β), then Follow(X) = { First(β) – ∈ } ∪ Follow(S)
CFG
S -> E F
E -> g | ∈
F -> f | ∈
Symbol
First
Follow
E
g ∈
f ∈
F
f ∈
$
S
g ∈
$
CFG
S -> E F G
E -> g | o
F -> f | ∈
G -> k | l
Symbol
First
Follow
E
g o
f ∈
F
f ∈
k l
G
k l
$
S
g o
$
Example of first and follow function
How to find the first and follow functions for the given CFG?
S → aXZh
X → cY
Y → bY / ∈
Z → EF
E → g / ∈
F → f / ∈
The first and follow functions are given below;
First Functions
First(S) = { a }
First(X) = { c }
First(Y) = { b , ∈ }
First(Z) = { First(E) – ∈ } ∪ First(F) = { g , f , ∈ }
First(E) = { g , ∈ }
First(F) = { f , ∈ }
Follow Functions
Follow(S) = { $ }
Follow(X) = { First(Z) – ∈ } ∪ First(h) = { g , f , h }
Follow(Y) = Follow(X) = { g , f , h }
Follow(Z) = First(h) = { h }
Follow(E) = { First(F) – ∈ } ∪ Follow(Z) = { f , h }
Follow(F) = Follow(Z) = { h }
Example of first and follow function with Left Recursion
How to find the first and follow functions for the given CFG with Left Recursive production rules.?
S → X
X → aY / Xd
Y → b
C → t
The given grammar is left recursive. So, we first remove the left recursion from the given grammar.
After the elimination of left recursion, we get the following grammar.
S → X
X→ aYX’
X’ → dX’ / ∈
Y → b
C → t
The first and follow functions are described below;
First Functions
How to find the first and follow functions for the given grammar?
S → (F) / g
F → S F’
F’ → ,S F’ / ∈
The first and follow functions are described below;
First Functions
How to find the first and follow for the given grammar?
S → XaAb / YbYa
X → ∈
Y → ∈
The first and follow functions are described below;
First Functions
Example of first and follow function with Left Recursion
How to find the first and follow functions for the given CFG with Left Recursive production rules.?
X→ X + Y / Y
Y → Y d F / F
F → (X) / id
Solution-
The given grammar is left recursive. So, we first remove the left recursion from the given grammar.
After the elimination of left recursion, we get the following grammar.
X → YX’
X’ → + YX’ / ∈
Y → FY’
Y’ → d FY’ / ∈
F → (X) / id
The first and follow functions are described below;
First Functions
How to find the first and follow functions for the given grammar?
S → XCY / CbY / Ya
X → da / YC
Y → g / ∈
C → h / ∈
The first and follow functions are described below;
First Functions-
First(S) = { First(X) – ∈ } ∪ { First(C) – ∈ } ∪ First(Y) ∪ First(b) ∪ { First(Y) – ∈ } ∪ First(a) = { d , g , h , ∈ , b , a }
First(X) = First(d) ∪ { First(Y) – ∈ } ∪ First(C) = { d , g , h , ∈ }