Rules of First and Follow in Predictive Parsing

Rules for First in Predictive Parsing

1. Suppose X is a terminal then First(X) is just X!
2. Suppose there is a Production rule of X → ε then add ε to first(X)
3. Suppose there is a Production rule of X → A1, A2…..A^k then add first(A1,A2..A^k) to first(X)
4. 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

Rule 2

Rule3

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)

Example of Rule 4.2:

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

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

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

 

Rules for Follow in Predictive Parsing

1. First, put $ (the end of input marker) in Follow(S) (S is the start symbol)
2. 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).
3. Suppose there is a production rule of A → aB, then everything in FOLLOW(A) is in FOLLOW(B)
4. 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).

Rule 2:

For any production rule S -> a X,

Follow(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 | ∈

---

CFG

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

---

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 }