A grammar contains the rule: Expr → Expr + Term | Term. When a recursive descent parser attempts to apply this rule, what happens?
AThe parser generates an ambiguity warning and falls back to the second alternative
BThe parser correctly handles it by checking if the next token is '+' before recursing
CThe parser enters an infinite loop because it calls the Expr function without consuming any input
DThe parser fails immediately with a syntax error because '+' is not in the FIRST set of Expr
Left recursion is fatal for recursive descent (and all LL) parsers. The Expr function immediately calls Expr again before consuming any token — an infinite loop that never terminates. This happens because LL parsers build the parse tree top-down from the root: to parse Expr, they immediately try to parse Expr as the first child, which tries to parse Expr again, with no progress on the input. The fix is to rewrite the grammar: Expr → Term Expr', Expr' → + Term Expr' | ε. This eliminates left recursion by making the '+' consumption explicit, but it changes the parse tree shape compared to the original left-associative structure.
Question 2 Multiple Choice
When does an LL(1) parser fail to determine which production to apply for a given nonterminal?
AWhenever the nonterminal has more than two alternative productions
BWhen two or more alternative productions have overlapping FIRST sets — the same token could begin multiple alternatives
CWhen the lookahead token does not appear in the grammar at all
DWhenever the grammar contains epsilon (empty) productions
An LL(1) parser uses a single lookahead token to select among alternative productions. This works only when the FIRST sets of all alternatives for a nonterminal are disjoint — each possible next token uniquely identifies which rule to apply. If two alternatives can both start with the same token, the parser cannot deterministically choose, and the grammar is not LL(1). The number of alternatives (option A) is irrelevant as long as their FIRST sets don't overlap. Epsilon productions (option D) do complicate things via FOLLOW sets, but they don't by themselves make a grammar non-LL(1).
Question 3 True / False
In a recursive descent parser, the call stack implicitly serves as the parsing stack, with each grammar nonterminal implemented as a function.
TTrue
FFalse
Answer: True
This is the key insight that makes recursive descent elegant. Each nonterminal becomes a function: the function for Statement might call the function for Expression, which calls the function for Term, and so on. The program's call stack tracks the nesting of these function calls, exactly mirroring the depth of the parse tree being built. When a function returns, it 'pops' a node from the implicit stack. A table-driven LL parser does the same thing but uses an explicit stack data structure and a parsing table, making the process less natural to write by hand but easier to generate automatically.
Question 4 True / False
An LL(2) parser can handle left-recursive grammars that LL(1) can seldom, because it can 'look ahead' past the recursive call to see how the rule eventually terminates.
TTrue
FFalse
Answer: False
No amount of additional lookahead fixes left recursion in an LL parser. Left recursion causes an infinite loop not because the parser lacks information about what comes later, but because parsing the nonterminal immediately requires parsing the same nonterminal again — an infinite descent that never consumes a token. Even LL(k) for arbitrarily large k cannot resolve this structural problem. The only solution is to rewrite the grammar to eliminate left recursion. LL(2) is strictly more powerful than LL(1) for grammars that are non-left-recursive but have overlapping FIRST sets resolvable with two tokens of lookahead — but left recursion is a different kind of problem entirely.
Question 5 Short Answer
Why must LL grammars be free of left recursion, and what does the standard transformation to eliminate it cost you?
Think about your answer, then reveal below.
Model answer: Left recursion causes infinite loops in LL (top-down) parsers because the parser tries to expand a nonterminal by immediately invoking the same nonterminal again, without consuming any input. The standard fix rewrites `A → Aα | β` into `A → β A'` and `A' → α A' | ε`, replacing left recursion with right recursion. The cost is that the resulting parse tree has a different shape: the left-recursive grammar naturally produced left-associative trees (correctly grouping `a + b + c` as `(a + b) + c`), while the right-recursive rewrite produces right-leaning trees. Semantic actions (code generation steps) attached to the grammar must be adjusted to recover the intended associativity.
This is a real practical cost: parser engineers often prefer LR parsing (bottom-up) for expression-heavy languages precisely because LR parsers handle left recursion naturally and preserve the intended tree structure. LL parsing's simplicity comes at the price of requiring grammar transformations that can obscure the original language's structure.