Home › GATE CSE › computerscience › Compiler Design › A FINITE AUTOMATON used in the scanner is typica…
A FINITE AUTOMATON used in the scanner is typically
Aa DFA built from the regex describing each token
Ba Turing machine
Ca pushdown automaton
Dinterpreted at runtime by recursion
Answer & Solution
Correct answer: A. a DFA built from the regex describing each token
1. Scanners are typically built as DFAs (deterministic finite automata).
2. Pipeline: regex → NFA (via Thompson's construction) → DFA (via subset construction) → MINIMISED DFA.
3. The DFA is then encoded as a TABLE: current state × input character → next state. Plus an accept set.
4. Lex/flex/ANTLR all generate this kind of table-driven DFA.
5. PDA (option C) is for parsing, not scanning. Turing machines (B) are vastly overkill.
_Source: Bob Nystrom, "Crafting Interpreters", Ch 4.3 + 4.5 (Regular expressions to DFA)._
Related questions
The FOLLOW(A) set in LL parsing isThe FIRST(α) set of a string α 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 by