Rules of First and Follow in Predictive Parsing

Rules for First in Predictive Parsing

Suppose X is a terminal then First(X) is just X!
Suppose there is a Production rule of X → ε then add ε to first(X)
Suppose there is a Production rule of X → A1, A2…..A^k then add first(A1,A2..A^k) to first(X)
First(A1, A2..A^k) is either
1. First(A1) (Suppose First(A1) doesn’t contain ε)
2. OR (Suppose First(A1) does contain ε) then First (A1, A2..A^k) is everything in First(A1) <except for ε > as well as everything in First(A2..A^k)
3. Suppose First(A1) First(A2)…..First(A^k) all contain ε then add ε to First(A1, A2..A^k) as well.

Rule 1

Production Rule / CFG	First
A → lmn / opq / rst	First(A) = { l , o , r }

Rule 2

Production Rule / CFG	First
X → ∈	First(X) = { ∈ }

Rule3

Production Rule / CFG	First
X → a	First(X) = { a }

Rule 4

Rule 4.1: If ∈ does not belongs to First(E), then First(EF) = First(E)
Rule 4.2: If ∈ belongs to First(E), then First(EF) = { First(E) – ∈ } ∪ First(F)

Example of Rule 4.1:

If ∈ does not belongs to First(E), then First(EF) = First(E)

Production Rule / CFG

First

S -> E F
E -> g | o
F -> f | ∈

First(S) = { g, o }

First(E) = { g, o }

First(F) = { f, ∈ }

Example of Rule 4.2:

If ∈ belongs to First(E), then First(EF) = { First(E) – ∈ } ∪ First(F)

Production Rule / CFG

First

S -> E F
E -> g | ∈
F -> f | o

First(S) = { g, ∈ }

First(E) = { g, ∈}

First(F) = { f, o }

Rule 5

For a production rule S → EFG,

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 }.

Production Rule / CFG

First

S -> E F G
E -> g | o
F -> f | ∈
G -> k | l

First(S) = { g, o }

First(E) = { g, 0 }

First(F) = { f, ∈ }

First(G) = { k, l }

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, ∈ }.

Production Rule / CFG

First

S -> E F G
E -> g | ∈
F -> f | ∈
G -> k | l

First(S) = { g, ∈ }

First(E) = { g, ∈ }

First(F) = { f, ∈ }

First(G) = { k, l }

Rules for Follow in Predictive Parsing

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

First(S) = First(X) = { a }
First(X) = { a }
First(X’) = { d , ∈ }
First(Y) = { b }
First(C) = { t }

Follow Functions-

Follow(S) = { $ }
Follow(X) = Follow(S) = { $ }
Follow(X’) = Follow(X) = { $ }
Follow(Y) = { First(A’) – ∈ } ∪ Follow(A) = { d , $ }
Follow(C) = NA

Example of first and follow

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

First(S) = { ( , g }
First(F) = First(S) = { ( , g }

First(F’) = { , , ∈ }

Follow Functions-

Follow(S) = { $ } ∪ { First(F’) – ∈ } ∪ Follow(F) ∪ Follow(F’) = { $ , , , ) }
Follow(F) = { ) }
Follow(F’) = Follow(F) = { ) }

Example of first and follow

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

First(S) = { First(X) – ∈ } ∪ First(a) ∪ { First(Y) – ∈ } ∪ First(b) = { a , b }
First(X) = { ∈ }
First(Y) = { ∈ }

Follow Functions

Follow(S) = { $ }
Follow(X) = First(a) ∪ First(b) = { a , b }
Follow(Y) = First(b) ∪ First(a) = { a , b }

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

First(X) = First(Y) = First(F) = { ( , id }
First(X’) = { + , ∈ }
First(Y) = First(F) = { ( , id }
First(Y’) = { d , ∈ }
First(F) = { ( , id }

Follow Functions

Follow(X) = { $ , ) }
Follow(X’) = Follow(E) = { $ , ) }
Follow(Y) = { First(X’) – ∈ } ∪ Follow(X) ∪ Follow(X’) = { + , $ , ) }
Follow(Y’) = Follow(Y) = { + , $ , ) }
Follow(F) = { First(Y’) – ∈ } ∪ Follow(Y) ∪ Follow(Y’) = { d , + , $ , ) }

Example of first and follow

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 , ∈ }
First(Y) = { g , ∈ }
First(C) = { h , ∈ }

Follow Functions-

Follow(S) = { $ }
Follow(X) = { First(C) – ∈ } ∪ { First(Y) – ∈ } ∪ Follow(S) = { h , g , $ }
Follow(Y) = Follow(S) ∪ First(a) ∪ { First(C) – ∈ } ∪ Follow(X) = { $ , a , h , g }
Follow(C) = { First(Y) – ∈ } ∪ Follow(S) ∪ First(b) ∪ Follow(X) = { g , $ , b , h }

Rules of First and Follow in Predictive Parsing

Rules for First in Predictive Parsing

Rule 1

Rule 2

Rule3

Rule 4

Rule 5

Rules for Follow in Predictive Parsing

Rule 3

Example of first and follow function

Example of first and follow function with Left Recursion

Example of first and follow

Example of first and follow

Example of first and follow function with Left Recursion

Example of first and follow

Related Posts:

Contents Copyrights reserved by T4Tutorials