Recursive-descent parsing and backtracking

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the end of this lesson.

• Remove left recursion from A → A x | y. from Lesson 2.2
• What is a leftmost derivation? from Lesson 2.1.1
• Which data structure is last-in, first-out, and where does the compiler use it? from Lesson 0.2.4

1 · The Story

📖

One clerk per category

Kabir reorganises the Sentence Desk. Every category in the rulebook gets its own clerk: a Sentence clerk, a Subject clerk, a Verb clerk. To check a Sentence, the Sentence clerk calls the Subject clerk and then the Verb clerk; each of them calls the clerks for their own parts. The work starts at the top category and moves down toward the words.

When a clerk has several rules, he tries them in order. Before trying one, he puts a bookmark in the speech. If the rule fails halfway, he goes back to the bookmark, “un-reads” the words, and tries the next rule. Patient, but slow.

Kabir’s improvement: if the clerk can tell which rule to use just by looking at the next word, he never needs the bookmark.

2 · Predict First

🤔

With S → c A d, A → a b | a, and the input c a d, trying A’s rules in the order written: how many times does the parser have to rewind? Write your guess down. The answer is in the vault.

3 · Core Concept

Top-down parsing

Top-down parsing builds the parse tree from the root (start symbol) down to the leaves, choosing a production for the leftmost nonterminal at each step. It traces out a leftmost derivation.

Recursive descent

A recursive-descent parser has one procedure per nonterminal. The procedure for A chooses a production A → X₁ … Xₖ and, for each Xᵢ in order, either matches the next input token (terminal) or calls the procedure for Xᵢ (nonterminal).

void E()  { T(); Eprime(); }
void Eprime() { if (look == '+') { match('+'); T(); Eprime(); } /* else ε: do nothing */ }
void T()  { F(); Tprime(); }
void Tprime() { if (look == '*') { match('*'); F(); Tprime(); } }
void F()  { if (look == '(') { match('('); E(); match(')'); } else match(ID); }

This is the parser for E → T E′, E′ → + T E′ | ε, T → F T′, T′ → * F T′ | ε, F → ( E ) | id: it never guesses, because the next token always decides.

Backtracking

If the procedure cannot tell which alternative to use, it tries them in order. On failure it restores the input position (and discards the partial tree) and tries the next alternative: backtracking. It works for any grammar without left recursion, but can take exponential time and makes error messages poor.

Order matters: with A → a | a b, a backtracking parser that accepts the first success inside A may need to backtrack later when the rest of the input fails.

Predictive parsing

A predictive parser is recursive descent without backtracking: the next token (the lookahead) always selects exactly one production. That needs a grammar without left recursion, left-factored, and with alternatives whose possible first tokens do not overlap. The next lesson computes those “possible first tokens” precisely.

Left recursion breaks it

For A → A α, procedure A() would call A() as its first action, without consuming input: infinite recursion. This is Chetan’s loop, and the reason for Lesson 2.2.

Story → compiler term

4 · Visual

| Backtracking trace for S → c A d, A → a b | a on input c a d | | --- | | c try S → c A d match c try A → a b match a fail: expected b, saw d backtrack: undo A → a b try A → a match a match d accept |

Computed by a backtracking parser. Indentation shows the procedure nesting.

First guess: A → a b fails at b.

After backtracking: A → a succeeds.

5 · Worked Examples

Example 1 Easy

Trace the backtracking parser for S → c A d, A → a b | a on c a d.

Solution

try S → c A d
  match c
  try A → a b
    match a
    fail: expected b, saw d
  backtrack: undo A → a b
  try A → a
    match a
  match d
accept

One backtrack: the clerk for A puts his bookmark before a, fails at b, rewinds, and succeeds with the second rule.

Example 2 Medium

Write recursive-descent procedures for S → x S y | x y. Can they decide without backtracking?

Solution

try S → x S y
  match x
  try S → x S y
    match x
    try S → x S y
      fail: expected x, saw y
    backtrack: undo S → x S y
    try S → x y
      fail: expected x, saw y
  backtrack: undo S → x S y
  try S → x y
    match x
    match y
  match y
accept

Both alternatives start with x, so one token of lookahead cannot choose: the parser backtracks. Left factoring gives S → x S′, S′ → S y | y, which a predictive parser can parse (S′ chooses S y when the next token is x, and y when it is y).

Example 3 GATE

Why does a recursive-descent parser for E → E + T | T loop forever, and what is the fix?

Solution

Procedure E() first calls E() (for the alternative E + T) without consuming any token, so it recurses forever. The fix is Lesson 2.2: E → T E′, E′ → + T E′ | ε, whose procedures are shown above.

6 · Shortcuts

⚡

Predictive = no bookmark: if for every nonterminal the alternatives start with different tokens (after removing left recursion and left factoring), recursive descent needs no backtracking. Valid when: grammars without ε-alternatives; with ε-alternatives you also need the tokens that can follow (next lesson).

⚡

Count backtracks by simulation: write the input, try alternatives in order, mark each rewind. Valid when: questions asking how many times a backtracking parser rewinds.

7 · GATE Traps

⚠️

• Recursive descent follows a leftmost derivation.
• Backtracking parsers work only without left recursion; they loop on A → Aα.
• Backtracking does not make a parser accept ambiguous-free languages faster; it can be exponential.
• The order of alternatives can change how many backtracks happen.
• A predictive parser is still recursive descent, just without backtracking.

8 · Memory Hook

🧠

Top-down = guess from the top, check against the words; backtracking = bookmark and rewind.

9 · Connect the Dots

A predictive parser picks a production by looking at the next token. To do that systematically we need, for every right side, the set of tokens it can start with, and for every nonterminal, the tokens that can follow it. Those two sets are the next lesson, and a GATE favourite.

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markTop-down

A recursive-descent parser constructs:

• (A) a rightmost derivation in reverse
• (B) a leftmost derivation
• (C) a rightmost derivation
• (D) no derivation

Q2NAT1 markBacktracking

With S → c A d, A → a | a b, trying alternatives in order and backtracking on failure, how many times does the parser backtrack on input c a b d?

Numerical answer: ________

Q3MCQ1 markLeft recursion

A recursive-descent parser for A → A b | c, given any input, will:

• (A) parse correctly
• (B) loop forever
• (C) report a lexical error
• (D) need exactly one backtrack

Q4MSQ1 markPredictive

Which properties are needed for a recursive-descent parser to work without backtracking (with one token of lookahead)?

• (A) no left recursion
• (B) alternatives of each nonterminal start with different tokens
• (C) the grammar is ambiguous
• (D) the grammar is left-factored

Q5MCQ1 markStructure

In a recursive-descent parser, a procedure is written for each:

• (A) terminal
• (B) nonterminal
• (C) token class of the lexer
• (D) state of a DFA

11 · Rule Card

• Top-down parsing: root to leaves, leftmost derivation.
• Recursive descent: one procedure per nonterminal; terminals matched with match().
• Backtracking: on failure restore input position and try the next alternative; exponential worst case.
• Predictive parsing: lookahead token selects the production; needs no left recursion, left factoring, disjoint starts.
• Left recursion → infinite recursion.

12 · Concept Ledger

top-down parsingrecursive-descent parsermatch()backtrackingpredictive parser

13 · Answer Vault