Overview
Pratt parsing gives tokens prefix and infix parse behavior and uses binding power to decide when an expression should stop consuming operators. It is compact for expression-heavy grammars.
CoreSource checked
Pratt Parsing
Parses expressions by assigning binding powers to tokens and recursing by precedence.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Parsing
- Difficulty
- Intermediate
- Family
- Expression Parsing
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 0
- Relationships
- 5
- Code example
- Ready
- Visualization
- Ready
Core Concepts
binding powerprefix parseletinfix parseletexpression precedenceparse statestring sequencegrammar productionexpression 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 when expression precedence is the main parsing challenge.
- Use when operators can be described by prefix, infix, or postfix parse functions.
When Not to Use
- Avoid when the full grammar needs a table-driven parser or broad ambiguity handling.
- Avoid when tokenization and error recovery requirements dominate the parser design.
What It Does
- Parses prefix and infix expression forms
- Uses binding power to encode precedence and associativity
- Builds expression trees from a token stream
Use Cases
- Expression parsers in interpreters and compilers
- Calculator and query-language syntax
- Languages with many custom operators
Inputs
- Token stream
- Operator binding powers
Outputs
- Expression tree
- Syntax error
Pseudocode
- 1.Parse the current token with its prefix parse function
- 2.While the next token has binding power above the current minimum
- 3.Consume the operator token
- 4.Parse the right expression using the operator's binding power
- 5.Combine the left and right expressions
- 6.Return the expression tree
Canonical Example
- Input
- tokens = ['2', '+', '3', '*', '4']
- Output
- tree = +(2, *(3, 4))
- Explanation
- The '*' operator has higher binding power, so it groups inside the right side of '+'.
Implementation Notes
- Define left and right binding powers for each operator.
- Keep prefix and infix parselets small and separately testable.
- Test associativity with chains such as a-b-c and a^b^c.
Common Pitfalls
- Wrong binding powers create incorrect associativity.
- Missing prefix handlers make valid expressions fail at the first token.
- Poor token-position tracking makes precedence errors hard to diagnose.
Interactive Mechanism Walkthrough
Sequence Window & Automaton AlignmentShow operators grabbing operands according to binding power.
Input:ABABABCABAB
Window:ABAB
Step 1 of 6: Parse the current token with its prefix parse function
expression-bindingNotes
Pratt parsers are concise, but binding-power tables need careful tests.
Sources (2)
What each reference supports for this entry.
Top Down Operator Precedence
PaperOriginal Pratt parsing reference for binding-power driven expression parsing.
Open sourceParsing Techniques
BookParsing reference for Pratt Parsing's control flow, grammar assumptions, and parser construction tradeoffs.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Variant ofRecursive Descent Parsing
Parsing · Foundation
Pratt parsing is a recursive-descent technique specialized for expressions.
Compare with thisAlternativesDijkstra's Two-Stack Algorithm
Parsing · Core
Pratt parsing handles precedence directly, while the two-stack form assumes full parenthesization.
Compare with thisAlternativesOperator Precedence Parsing
Parsing · Core
Operator-precedence parsing and Pratt parsing are expression parsers with different control structures.
Compare with thisRelationships
View full relationship pageVariant ofRecursive Descent Parsing
Pratt parsing is a recursive-descent technique specialized for expressions.
Alternative toPrecedence Climbing
Both parse expressions by precedence, but organize the recursion differently.
Related Algorithms
Tags
ParsingStringsGrammar