First() & Follow()

What are FIRST and FOLLOW?

FIRST and FOLLOW are used in Top-Down Parsing, especially for constructing LL(1) Predictive Parsing Tables.

They help the parser decide which production to choose by looking at the next input symbol.

Where are FIRST and FOLLOW Used?

• Used In LL(1) Parser
• Predictive Parser
• Recursive Descent Parser (without backtracking)

FIRST and FOLLOW are used to build the parsing table.

Not Directly Used In

• LR(0): Uses LR items and automata.
• SLR(1): Uses FIRST and FOLLOW (FOLLOW is especially important for reductions).
• CLR(1)/LR(1): Uses lookaheads instead of FOLLOW.
• LALR(1): Uses LR(1) lookaheads.

---

FIRST Set

FIRST(X) = Set of terminals that can appear first in strings derived from X.

Rules for FIRST

Rule 1: Terminal

FIRST(a) = {a}
FIRST(+) = {+}

Rule 2: ε

FIRST(ε) = {ε}

Rule 3: Production starts with terminal

A → aB

• Then,

FIRST(A) = {a}

Rule 4: Production starts with non-terminal

A → BC

• Add FIRST(B) except ε.,

FIRST(A) ⊇ FIRST(B) - {ε}

Rule 5: If ε ∈ FIRST(B)

A → BC

• Then also add FIRST(C).

Rule 6: If all symbols derive ε ⭐

A → BC

• If

ε ∈ FIRST(B)
ε ∈ FIRST(C)

• Then

ε ∈ FIRST(A)

FIRST() Example

A → a | ε
B → b

S → AB

FIRST(A)

{a, ε}

FIRST(B)

{b}

FIRST(S) ⭐

• Since A can produce ε:

FIRST(S)
= FIRST(A)-{ε} ∪ FIRST(B)

= {a} ∪ {b}

= {a,b}

• Since A→ε and B cannot derive ε:

FIRST(S)={a,b}

---

FOLLOW Set

FOLLOW(A) = Set of terminals that can appear immediately after A.

Rules for FOLLOW

Rule 1: Start Symbol

• If S is start symbol:

$ ∈ FOLLOW(S)

Rule 2: A → αBβ

• Everything in

FIRST(β)-{ε}

• goes into FOLLOW(B).

Rule 3: A → αB ⭐

• If B is at end:

FOLLOW(A) ⊆ FOLLOW(B)

Rule 4: A → αBβ ⭐

• If

ε ∈ FIRST(β)

• then

FOLLOW(A) ⊆ FOLLOW(B)

FOLLOW() Example

S → AB
A → a
B → b

FOLLOW(S)

{$}

FOLLOW(A)

• A followed by B.

FIRST(B)={b}

• Therefore

FOLLOW(A)={b}

FOLLOW(B)

• B is last.

FOLLOW(B)=FOLLOW(S)
         ={$}

---

Shortcut Rules

For FIRST

FIRST(Terminal) = Terminal

FIRST(ε) = ε

A→a...
Add a

A→B...
Add FIRST(B)

If ε in FIRST(B)
Move to next symbol

If all symbols give ε
Add ε

For FOLLOW

Start Symbol gets $

A→αBβ
Add FIRST(β)-{ε}

A→αB
Add FOLLOW(A)

A→αBβ
If ε in FIRST(β)
Add FOLLOW(A)

---

Why FIRST and FOLLOW Are Needed?

Consider:

S → aA
S → bB

Input begins with:

a

Using FIRST:

FIRST(aA)={a}
FIRST(bB)={b}

Parser immediately selects:

S → aA

No backtracking required.

LL(1) Parsing Table Rule

For production:

A → α

Case 1

• For every symbol in:

FIRST(α)

• place:

A → α

• in parsing table.

Case 2

• If

ε ∈ FIRST(α)

• then for every symbol in:

FOLLOW(A)

• place:

A → α

• in parsing table.

---

Most Important Exam Points

1. FIRST = What can come first.
2. FOLLOW = What can come after.
3. $ always belongs to FOLLOW(Start Symbol).
4. ε is included in FIRST only if the non-terminal can derive ε.
5. FIRST and FOLLOW are primarily used in LL(1) parsing table construction.
6. SLR(1) also uses FOLLOW sets for reductions.
7. LR(0) does not use FIRST/FOLLOW.