# Rules of First and Follow in Predictive Parsing

# 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- First(A1) (Suppose First(A1) doesn’t contain ε)
- 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}) - 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) = { ∈ } |

**Rule****3**

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 }