Project ForgeSign up free
Compiler Design
Lexical Analysis & Parsing
GATE 2012
Expert

For the grammar S → aAbB | bAaB | ε, A → S, B → S, the FIRST and FOLLOW sets for the non-terminals A and B are

  • FIRST(A) = {a, b, ε} = FIRST(B); FOLLOW(A) = {a, b}; FOLLOW(B) = {a, b, $}
  • BFIRST(A) = {a, b, $}; FIRST(B) = {a, b, ε}; FOLLOW(A) = {a, b}; FOLLOW(B) = {$}
  • CFIRST(A) = {a, b, ε} = FIRST(B); FOLLOW(A) = {a, b}; FOLLOW(B) = ∅
  • DFIRST(A) = {a, b} = FIRST(B); FOLLOW(A) = {a, b}; FOLLOW(B) = {a, b}

Explanation

Since A → S and B → S, FIRST(A) = FIRST(B) = FIRST(S) = {a, b, ε} (from S's three productions). A appears only in tail positions followed immediately by a terminal (aAbB gives 'b' after A, bAaB gives 'a' after A), so FOLLOW(A) = {a, b} directly, with no dependency on FOLLOW(S). B appears at the very end of both of S's non-empty productions, so FOLLOW(B) must include FOLLOW(S); and FOLLOW(S) = {$} ∪ FOLLOW(A) ∪ FOLLOW(B) (since S is the RHS of A→S and B→S). Solving this fixed point gives FOLLOW(S) = FOLLOW(B) = {a, b, $}.

Source: GATE CS 2012 (2012)

This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.

Start revising free