Home › GATE CSE › computerscience › Compiler Design › Which formalism is most commonly used to specify…
Which formalism is most commonly used to specify the LEXICAL structure of programming language tokens?
ATuring machines
BContext-free grammars
CRegular expressions
DPredicate logic
Answer & Solution
Correct answer: C. Regular expressions
1. Lexical structure is REGULAR: tokens like identifiers, numbers, keywords can be described by REGULAR EXPRESSIONS.
2. Regex → NFA → DFA. The DFA becomes the scanner table.
3. Tools like lex, flex, ANTLR use this exact pipeline.
4. Context-free grammars (option B) are used for SYNTAX (parser), not lexical analysis. Turing machines and predicate logic are far more powerful than needed for tokenisation.
_Source: Bob Nystrom, "Crafting Interpreters", Ch 4.3 (Regular Languages and Expressions)._
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