The FIRST and FOLLOW sets for the non-terminals A and B

Home » Compiler Design » Compiler design miscellaneous » Question

Direction: For the grammar below, a partial LL (1) parsing table is also presented along with the grammar. Entries that need to be filled are indicated as E₁, E₂ and E₃. ε is the empty string, $ indicates end of input and | separates alternate right hand sides of productions.
S → a A b B | b A a B | ε
A → S
B → S

The FIRST and FOLLOW sets for the non-terminals A and B are

1. FIRST (A) = {a, b, ε} = FIRST (B)
  FOLLOW (A) = {a, b}
  FOLLOW (B) = {a, b, $}
2. FIRST (A) = {a, b, $}
  FIRST (B) = {a, b, ε}
  FOLLOW (A) = {a, b}
  FOLLOW (B) = {$}
3. FIRST (A) = {a, b, ε} = FIRST (B)
  FOLLOW (A) = {a, b}
  FOLLOW (B) = ∅
4. FIRST (A) = {a, b,} = FIRST (B)
  FOLLOW (A) = {a, b}
  FOLLOW (B) = {a, b,}

Correct Option: A

First (S) = First (aAbB) ∪ First (bAaB) ∪ ∈ = {a} ∪ {b} ∪ ∈
= {a,b,∈}
First (A) = First S = {a,b,∈}
First (B) = First S = {a,b,∈}
Follow (S) = {$} ∪ follow (A) ∪ follows (B)
Follow (A) = {a, b}
Follow (B) = Follow (S) = {$, a, b}