Overview
Recursive Descent Parsing mirrors the grammar in code, calling rule functions as the input structure is recognized.
FoundationSource checked
Recursive Descent Parsing
Parses input with one function per grammar rule.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Parsing
- Difficulty
- Intermediate
- Family
- Top-Down Parsing
- Tier
- Foundation
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 0
- Relationships
- 20
- Code example
- Ready
- Visualization
- Ready
Core Concepts
grammar functiontoken streamrecursive callparse treeparse staterecursive decompositiongrammar productiontop-down parsing
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(d)
When to Use
- Use it when a grammar is simple enough to encode directly as parser functions.
- Use it for hand-written parsers where readable error handling matters.
- Use it for expression languages after handling precedence and left recursion.
When Not to Use
- Avoid it for left-recursive grammars unless the grammar is rewritten or the parser supports it.
- Avoid it when ambiguous grammar behavior should be resolved by a parser generator.
- Avoid deep recursion without stack-depth safeguards.
What It Does
- Consumes tokens according to grammar rules
- Builds parse structure with recursive functions
Use Cases
- Small programming languages
- Configuration formats
- Expression parsing with clear grammar
Inputs
- Token stream
- Grammar encoded as parser functions
Outputs
- Parse tree
- Syntax error
Pseudocode
- 1.Create a function for each grammar rule
- 2.Start with the top-level rule
- 3.Each function checks expected tokens or calls other rule functions
- 4.Advance the token stream when tokens match
- 5.Return syntax errors when no rule matches
Canonical Example
- Input
- tokens = ['2', '+', '3', '*', '4']
- Output
- an expression tree with multiplication nested under addition
- Explanation
- Parser functions enforce precedence so 3 * 4 becomes the right-hand term of the addition.
Implementation Notes
- Write one function per grammar rule.
- Keep tokenization separate from parsing unless the language is tiny.
- Use lookahead and backtracking deliberately rather than accidentally.
Common Pitfalls
- Leaving left-recursive grammar rules unchanged.
- Consuming tokens before confirming a rule can succeed.
- Producing errors that do not identify the expected token or rule.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow parser functions calling each other to build a parse tree.
Step 1 of 5: Create a function for each grammar rule
parse-call-treeNotes
Recursive descent is easiest to maintain when the grammar shape is visible in the function structure.
Sources (1)
What each reference supports for this entry.
Compilers: Principles, Techniques, and Tools
BookCompiler textbook support for Recursive Descent Parsing's grammar analysis, parser construction, and implementation constraints.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Has variantsPratt Parsing
Parsing · Core
Pratt parsing is a recursive-descent technique specialized for expressions.
Compare with thisAlternativesLL Parsing
Parsing · Core
LL Parsing is an alternative to Recursive Descent Parsing within the Top-Down Parsing family.
Compare with thisAlternative toLR Parsing
Parsing · Core
Recursive descent is hand-written top-down parsing, while LR parsing is table-driven bottom-up parsing.
Compare with thisUsesTokenization
Parsing · Foundation
Recursive descent parsers consume token streams produced by tokenization.
Compare with thisRelationships
View full relationship pageAlternative toLR Parsing
Recursive descent is hand-written top-down parsing, while LR parsing is table-driven bottom-up parsing.
UsesTokenization
Recursive descent parsers consume token streams produced by tokenization.
Related Algorithms
Tags
ParsingRecursionGrammar