Rules of First and Follow in Predictive Parsing

By: Prof. Fazal Rehman Shamil
Last modified on January 26th, 2021

Rules of First and Follow in Predictive Parsing

Predictive Parsing
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…..Ak then add first(A1,A2..Ak) to first(X)
  4. First(A1, A2..Ak) is either
    1. First(A1) (Suppose First(A1) doesn’t contain ε)
    2. OR (Suppose First(A1) does contain ε) then First (A1, A2..Ak) is everything in First(A1) <except for ε > as well as everything in First(A2..Ak)
    3. Suppose First(A1) First(A2)…..First(Ak) all contain ε then add ε to First(A1, A2..Ak) 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

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

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 }