Coursify

Backtracking in a Recursive-Descent Parser for Grammar (S \rightarrow cAd), (A \rightarrow ab \mid ac \mid a) on Input cad

Backtracking in a Recursive-Descent Parser for Grammar (S \rightarrow cAd), (A \rightarrow ab \mid ac \mid a) on Input cad

Verified Sources
Nov 3, 2026

Recursive-descent attempt order for nonterminal A

  1. 1
    Step 1

    Using (S \rightarrow cAd), the parser matches terminal c. The remaining input is ad and it must parse (A) starting at the leading a.

  2. 2
    Step 2

    Parser attempts ab. It matches a, then expects b but the next input symbol is d (since remaining is ad). This alternative fails, so the parser backtracks.

  3. 3
    Step 3

    Parser rewinds to retry the second alternative ac. It matches a, then expects c but the next input symbol is still d. This fails again, so the parser backtracks.

  4. 4
    Step 4

    Parser rewinds and tries a. It matches a successfully. Now the parser returns to (S \rightarrow cAd) and matches terminal d.

  5. 5
    Step 5

    "All symbols are matched with no further backtracking."

    Counting backtracks

    • Backtrack after failing A → ab : 1
    • Backtrack after failing A → ac : 2
    • A → a succeeds, so no further backtracking inside (A).

    ✅ Total backtracks on cad = 2 → choice (i).

    Why backtracking happens exactly twice

    Because (A) has three alternatives and the input beginning at the (A) position is a followed by d, the first two alternatives require a second symbol (b for ab, c for ac) but encounter d, producing failure and forcing backtracking each time.2

    Correct answer (MCQ)

    Footnotes

    1. Recursive Descent Parser - GeeksforGeeks - Provides an algorithmic description: if a mismatch occurs, backtrack and try another possibility. ↩

    2. Recursive descent, LL and predictive parsers - Eli Bendersky - Discusses predictive parsing (no backtracking) via lookahead and why ambiguity causes need for more power/backtracking. ↩

Choose the correct answer

Pro Tip

When the question asks for number of backtracks, assume the parser tests alternatives in order and counts each failed alternative attempt that triggers a rewind.

Common pitfall

"Do not count terminal mismatches inside a successful alternative as separate backtracks—only count the times the parser actually rewinds and switches to the next production alternative."

Visual summary (alternatives attempted for A)

Backtracking attempts while parsing A on 'ad'

Only alternatives of A are considered after matching 'c' in S → cAd.

Recursive Descent Parsing (backtracking concept)

Knowledge Check

Question 1 of 3
Q1Single choice

For the grammar (S \rightarrow cAd), (A \rightarrow ab \mid ac \mid a), and input cad, what is the number of backtracks in a backtracking recursive-descent parser?

Explore Related Topics

1

Finite Automata: Which Option Is NOT Accepted?

2

Handle Pruning and the Correct Parsing Method (MCQ)

3

Converting an Arbitrary CFG to an LL(1) Grammar: Correct Option and Why

Browse all research articles