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 }