Watch a top-down parser build its tree in pre-order, depth-first order. Every production saves the input position; a failed choice restores that position before the next production is tried.

Try your own grammar

ASCII syntax only: use ->, |, and epsilon. A name that appears on a left-hand side is a nonterminal; every other symbol is a terminal. Use id and num for token classes. Punctuation terminals are one character each.

← → step · Space play/pause Step 0 of 0
Now Ready to parse.
Ready
The rules

Grammar

Scanner output

Input tape

0 comparisons 0 rewinds 0 max depth
Built top down

Working parse tree

active matched abandoned
Slide algorithm

Parser pseudocode
  1. parse(A):
  2. for each A → X₁ … Xₖ:
  3. save ← input position
  4. for each Xᵢ in the RHS:
  5. if nonterminal: parse(Xᵢ)
  6. else if Xᵢ = lookahead:
  7. advance input
  8. else: this production fails
  9. if every Xᵢ succeeded: return 1
  10. input position ← save
  11. // try the next production
  12. return 0
Runtime state

Call stack
No active calls
Saved input positions

Backtrack checkpoints
No saved positions
Most recent first

Execution trace

Click an event to jump to it