Questions: Recursive Descent Parser Design

Question 1

A grammar contains the rule E → E + T | T. When you write parseExpression() for this rule in a recursive descent parser, what happens when the function is called?

• A. The function correctly parses left-associative addition expressions
• B. The function loops infinitely — it calls itself immediately before consuming any input
• C. The function fails with a syntax error on all inputs because the rule is ambiguous
• D. The function requires two tokens of lookahead to distinguish the two alternatives

Answer: (B)

E → E + T is left-recursive: the first thing parseExpression() does is call parseExpression() again — before consuming any token — creating infinite recursion. Left recursion is the core structural incompatibility between this style of grammar and recursive descent. The function never gets the chance to try the second alternative T. This is not a programming error; it is a property of the grammar that must be fixed before writing any code.

Question 2

After eliminating left recursion, the rule E → E + T | T becomes E → T (('+') T)*. How does this translate into a recursive descent parser?

• A. A recursive call to parseExpression() at the end of the function handles the repetition
• B. A while loop inside parseExpression() that parses T, then keeps consuming '+' and another T
• C. Two separate functions — one for E and one for the repetition — calling each other mutually
• D. A lookup table maps the '+' token to the correct production to avoid any looping

Answer: (B)

The right-recursive / iterative form E → T (('+') T)* maps directly to: parse one T, then enter a while loop that checks if the next token is '+'; if so, consume it and parse another T, repeating until no '+' is found. This is the standard mechanical transformation that makes left-recursive rules safe for recursive descent. The while loop replaces the left recursion without changing the language recognized or the left-associativity of the operator.

Question 3

Hand-written recursive descent parsers are rarely used in production compilers because automatically generated parsers (like YACC/Bison output) are more reliable and easier to maintain.

• T. True
• F. False

Answer: False

This is a widespread misconception. GCC (C++ frontend), Clang, the Go compiler, and the Rust compiler all use hand-written recursive descent parsers. Production-quality RDP parsers are preferred for real languages because they produce better error messages (the code knows exactly what it was trying to parse), support unlimited lookahead naturally, and are easier to customize for language-specific quirks. Parser generators are common in academic contexts and smaller tools, but hand-written RDP dominates in major production compilers.

Question 4

In a recursive descent parser, the recursive call structure of the parsing functions directly mirrors the recursive structure of the grammar rules.

• T. True
• F. False

Answer: True

This is the defining property of recursive descent: each grammar non-terminal becomes a function, and when a production's right-hand side contains a non-terminal, the corresponding function is called. The nesting of recursive calls at runtime reflects the nesting of syntactic structure in the input — parseExpression() calls parseTerm() which calls parseFactor(), mirroring the grammar hierarchy. This structural correspondence is what makes recursive descent easy to write, debug, and extend.

Question 5

Why does left recursion in a grammar cause infinite recursion in a recursive descent parser, and how is it eliminated?

Model answer: Left recursion means a non-terminal's first action is to invoke itself without consuming any input token. In code, the corresponding function calls itself immediately, causing infinite recursion before any matching occurs. It is eliminated by rewriting left-recursive rules into iterative form: E → E + T | T becomes E → T ('+' T)*, where the parser first handles the base case T, then uses a while loop to consume any number of additional '+ T' suffixes. This preserves the language and operator associativity while removing the self-referencing first step.

The transformation is mechanical: collect the base case (the alternative that doesn't start with E) and make it the seed, then wrap the recursive part in a loop. The resulting code is equivalent in the language it accepts but avoids the infinite self-call. This is why left-factoring the grammar is a prerequisite step before writing a recursive descent parser.