FIRST & FOLLOW Computation, Left Recursion & Factoring
“Recursive set rules, eliminating immediate and indirect left recursion, and left factoring transformations.”
1.The Grammar Mechanics of Top-Down Parsing
§ 2.1.Top-down syntax analysis attempts to find a leftmost derivation for an input string w starting from the start symbol S.
The Curse of Left Recursion: A grammar is left recursive if there exists a non-terminal A such that A \Rightarrow^+ A\alpha for some string \alpha. A recursive-descent parser attempting to expand A will repeatedly invoke the subroutine for A before consuming any input token, resulting in infinite call stack overflow.
Left Factoring: When two productions for A share a common prefix, e.g., A \to \alpha\beta_1 \mid \alpha\beta_2, a predictive parser seeing lookahead terminal in FIRST(\alpha) cannot determine which production to select without backtracking. Left factoring defers the decision until \alpha has been consumed.
FIRST and FOLLOW Mathematical Formulations:
- FIRST(\alpha) = { a \in \Sigma \mid \alpha \Rightarrow^ a\beta } \cup { \epsilon if \alpha \Rightarrow^ \epsilon }.
- FOLLOW(A) = { a \in \Sigma \cup {\} \mid S \Rightarrow^* \alpha A a \beta }$.
2. Worked Analysis: Comprehensive FIRST & FOLLOW Derivation
Notice that E' and T' are nullable non-terminals resulting from left-recursion elimination.
Consider the standard arithmetic expression grammar with left recursion eliminated:
E -> T E'
E' -> + T E' | epsilon
T -> F T'
T' -> * F T' | epsilon
F -> ( E ) | id
Step 1: Compute FIRST Sets (bottom-up from terminals):
- FIRST(F) = {(, id}
- FIRST(T') = {*, epsilon}
- FIRST(T): T -> F T', so FIRST(T) = FIRST(F) = {(, id}
- FIRST(E') = {+, epsilon}
- FIRST(E): E -> T E', so FIRST(E) = FIRST(T) = {(, id}
Step 2: Compute FOLLOW Sets:
- Start Symbol: FOLLOW(E) contains {}. In F -> ( E ), ')' follows E. Thus, FOLLOW(E) = {, )}.
- In E -> T E': E' is at the right end, so FOLLOW(E') = FOLLOW(E) = {$, )}.
- In E -> T E': symbol following T is E'. Thus, add (FIRST(E') - {epsilon}) = {+} to FOLLOW(T).
Since E' =>* epsilon, add FOLLOW(E) = {$, )} to FOLLOW(T).
Therefore: FOLLOW(T) = {+, $, )}.
- In T -> F T': T' is at the right end, so FOLLOW(T') = FOLLOW(T) = {+, $, )}.
- In T -> F T': symbol following F is T'. Thus, add (FIRST(T') - {epsilon}) = {*} to FOLLOW(F).
Since T' =>* epsilon, add FOLLOW(T) = {+, $, )} to FOLLOW(F).
Therefore: FOLLOW(F) = {*, +, $, )}.
Final Sets:
FIRST(E) = FIRST(T) = FIRST(F) = {(, id}
FIRST(E') = {+, epsilon}, FIRST(T') = {*, epsilon}
FOLLOW(E) = FOLLOW(E') = {$, )}
FOLLOW(T) = FOLLOW(T') = {+, $, )}
FOLLOW(F) = {*, +, $, )}.
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.
Curated for clarity, rigorous numerical solving, and semester excellence:
GATE-focused with worked FIRST/FOLLOW and LR parsing table numericals.
Exam-oriented explanations of ambiguous grammars and parser conflicts.
University-depth treatment of the full compiler pipeline — build a real compiler.