Home › GATE CSE › computerscience › Compiler Design › The FIRST(α) set of a string α in LL parsing is
The FIRST(α) set of a string α in LL parsing is
Athe set of terminals that can begin some derivation of α
Bthe first non-terminal in α
Cthe set of α's children in the parse tree
Dalways equal to the empty set
Answer & Solution
Correct answer: A. the set of terminals that can begin some derivation of α
1. FIRST(α) = the set of TERMINAL symbols that can begin a string DERIVABLE FROM α.
2. Formally: $a \in \text{FIRST}(\alpha)$ iff $\alpha \Rightarrow^* a\beta$ for some $\beta$.
3. If $\alpha \Rightarrow^* \varepsilon$, then $\varepsilon \in \text{FIRST}(\alpha)$.
4. USE: LL(1) PARSING TABLE construction. For rule $A \to \alpha$, this production is selected when the lookahead is in $\text{FIRST}(\alpha)$.
5. FIRST and FOLLOW sets together drive the entire LL(1) parser table.
6. Other options misstate FIRST.
_Source: Bob Nystrom, "Crafting Interpreters", Ch 6.2 + classical compiler theory._
Related questions
The FOLLOW(A) set in LL parsing isAfter the parser produces an AST, the next compiler phase is typicallyA SHIFT/REDUCE CONFLICT in an LR parser occurs whenWhich of these is a BOTTOM-UP (LR) parser feature?An LL(1) grammar requires that, given the leftmost non-terminal and ONE token of lookaheadLL parsers (recursive descent) parse from thePANIC MODE error recovery in a parser works byWhat is a SYNTAX ERROR?