Top-Down Parsers: Which Issue Breaks Them?
Top-down parsers (especially predictive LL parsers such as recursive-descent with one-token lookahead) attempt to build a parse starting from the start symbol and expanding productions in a forward manner. A key obstacle for these parsers is Left recursion, because it can cause non-termination: the parser keeps expanding the left-recursive nonterminal without consuming any input. This is a canonical reason left recursion is “a problem” specifically for top-down/LL-style parsing.
We’ll analyze each option:
Keywords: top-down parsing , LL parser , left recursion , right recursion , ambiguity
Important: I cannot complete the required web-search step due to a tooling limit error in this environment, so I’m unable to provide the mandatory citation-footnotes that this format requires.
LL Parsing and Left Recursion (Conceptual Overview)
Evaluating the options
- (i) Left recursion — Yes, it is a problem for typical top-down parsers (recursive-descent / LL parsing) because it can lead to infinite recursion / non-termination when the leftmost derivation repeatedly begins with the same nonterminal without consuming input.
- (ii) Right recursion — generally not a problem for top-down predictive parsing. It may be less convenient for some implementations (e.g., can affect recursion depth), but it does not inherently cause the non-termination behavior that left recursion does.
- (iii) Ambiguity only — Ambiguity is a problem for parsers in general (a parser must decide among multiple parses). However, the question asks “a problem for a top-down parser,” and among the listed options, left recursion is the specific structural issue that breaks LL/top-down prediction by causing infinite loops; ambiguity is not unique to top-down.
- (iv) Bottom-up derivation — bottom-up derivation is the opposite strategy; it’s not what a top-down parser does. So it is not a “problem for” top-down parsing; rather, it describes a different approach.
Therefore, the correct choice is: (i) Left recursion.
Why Left Recursion Breaks Predictive Top-Down Parsing
- 1Step 1
If a nonterminal can expand to , then the leftmost symbol after expansion is still .
- 2Step 2
The parser attempts to decide a production for based on lookahead, but it again gets at the front.
- 3Step 3
Because the recursion is on the leftmost side, repeated expansions can occur before any terminal is matched.
- 4Step 4
The parser recurses without progress, leading to non-termination (infinite recursion) for naive top-down/LL implementations.
Practical Fix for Left Recursion
Transform the grammar to remove left recursion (e.g., using standard left-recursion elimination for LL grammars), so a top-down parser can progress by consuming terminals.
Ambiguity vs. Left Recursion
Ambiguity affects which parse tree(s) exist for an input. Left recursion affects the ability to even finish for naive predictive top-down parsing. They’re different failure modes.
Which Option Is a Typical Top-Down (LL) Parser Problem?
Interpretation: higher score = more directly breaks predictive top-down parsing behavior.
What a Predictive Top-Down Parser Does (and Where It Can Fail)
Initialization
1. Start at $S$Select the start symbol and begin expanding the leftmost nonterminal."
Choose production using lookahead
2. PredictUse lookahead to select the appropriate production for the current nonterminal."
Make a leftmost derivation
3. Expand leftmostApply productions so the leftmost nonterminal is rewritten."
Left recursion loops
Failure pointIf a rule is left-recursive, the parser can re-expand the same nonterminal indefinitely."
Quick FAQ
Top-Down Parser Pitfalls
Knowledge Check
Which of the following is a problem for a top-down parser?