← ⬇️ Top-down Parsing (LL(1))
Subtopic 1 of 4

4.1Recursive descent and backtracking

One procedure per non-terminal. With ambiguity in the choice of production the parser may try one alternative, fail, backtrack and try the next. Predictive parsers avoid backtracking by looking ahead.

Input pointerc a d
S-
A-
Result-
  • Expand S → c A d and match c
  • Expand A: try the first alternative A → a b
  • Match a, then expect b but the input is d: FAIL
  • BACKTRACK: reset the input pointer to just after c
  • Try the second alternative A → a: match a
  • Match d: input consumed, parse succeeds

Grammar S → c A d, A → a b | a. Input: c a d

Previous year questions: Top-down Parsing (LL(1)) (5)

PYQs are grouped by topic, so this is the full set for Top-down Parsing (LL(1)); try the ones that match this subtopic. Open all 5 on the topic page.