Home › GATE CSE › computerscience › Compiler Design › Recursive descent is a TOP-DOWN parsing strategy…
Recursive descent is a TOP-DOWN parsing strategy. Its main weakness is
Ait can't handle ambiguous grammars
Bleft-recursive rules cause infinite recursion
Cit requires a stack
Dit produces wrong ASTs
Answer & Solution
Correct answer: B. left-recursive rules cause infinite recursion
1. A LEFT-RECURSIVE rule like $A \to A\alpha \mid \beta$ means the parser, on entering function parseA(), would immediately call parseA() again — infinite recursion.
2. SOLUTION: rewrite as right-recursive. $A \to A\alpha \mid \beta$ becomes $A \to \beta A'$ with $A' \to \alpha A' \mid \varepsilon$.
3. Algebraically equivalent (generates the same language) but no left recursion.
4. Bottom-up parsers (LR) handle left recursion natively, but recursive descent (top-down) cannot.
5. Option A is also a problem but not unique to recursive descent. Options C, D are wrong.
_Source: Bob Nystrom, "Crafting Interpreters", Ch 6.2 (Limitations of recursive descent)._
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