Home › GATE CSE › computerscience › Compiler Design › Which of these is a BOTTOM-UP (LR) parser feature?
Which of these is a BOTTOM-UP (LR) parser feature?
AExpands non-terminals starting from the start symbol
BRequires only one token of lookahead always
CCannot handle left-recursive grammars
DBuilds the parse tree from leaves to root by SHIFT/REDUCE
Answer & Solution
Correct answer: D. Builds the parse tree from leaves to root by SHIFT/REDUCE
1. LR (bottom-up) parsers operate via SHIFT and REDUCE actions:
- SHIFT: push next input token onto the parse stack
- REDUCE: pop a sequence matching a grammar rule's RHS, replace with the LHS non-terminal
2. The PARSE TREE is built FROM LEAVES UP — opposite of top-down.
3. ADVANTAGE: can handle LEFT-RECURSIVE grammars (option C is wrong for LR).
4. LALR(1), SLR(1), LR(1), LR(k) are progressively more powerful subclasses.
5. Tools: yacc/bison generate LR parsers.
6. Option A describes top-down (LL). Option D is wrong for general LR.
_Source: Bob Nystrom, "Crafting Interpreters", Ch 6.1 + Logic Versus History (LL vs LR)._
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 whenAn 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?