How to Learn Pratt Parsing: Binding Power, Prefix/Infix Parselets, Precedence, Associativity and Expression Parsers

Wait, What?

A tiny recursive function can parse a surprisingly rich expression language if precedence is treated as binding power.

Expression parsing looks messy when every precedence level becomes a separate grammar function. Addition, multiplication, prefix minus, exponentiation, calls, indexing and postfix operators can create a staircase of parser rules. Pratt parsing turns much of that hierarchy into one general mechanism: tokens know how they behave in prefix or infix position, and numeric binding powers determine when the parser should stop or recurse.

For learners, Pratt parsing teaches recursion, syntax trees, precedence, associativity, control by invariants and the separation between lexical tokens and syntactic meaning. For professionals, it is a practical technique for hand-written parsers, DSLs, interpreters, configuration languages and expression subgrammars.

Quick Answer

Learn Pratt parsing in this order: tokens → atoms → prefix position → infix position → binding power → stopping rule → associativity → parentheses → postfix/call operators → AST construction → diagnostics → production tests. The heart of the algorithm is not the token table. It is the rule: keep consuming operators while they bind more strongly than the context that called the current expression parser.

1. Start With the Ambiguity

Consider:

1 + 2 * 3

The token sequence alone does not say whether the tree is (1+2)*3 or 1+(2*3). The language definition says multiplication binds more strongly than addition. A parser must turn that convention into tree structure.

Associativity adds a second question. a-b-c is normally (a-b)-c, while an exponentiation operator may be right-associative: a^b^c = a^(b^c).

2. Pratt’s Core Insight: Meaning Depends on Position

The same token can behave differently depending on what appears before it. A minus sign may be:

prefix: -x
infix: a-b

Classic Pratt terminology calls the prefix handler a nud (“null denotation”) and the infix/postfix handler a led (“left denotation”). Modern implementations often use clearer names such as prefix parselet and infix parselet.

3. Binding Power Replaces a Ladder of Grammar Functions

Assign stronger operators higher binding power. For example:

+  : 10
*  : 20
^  : 30

The exact numbers are arbitrary; only their ordering matters. When parsing the right operand of +, the parser may continue through * because multiplication binds more strongly. It stops when it encounters an operator whose power is too weak for the current context.

4. The Minimal Shape of a Pratt Parser

parse_expression(min_bp):
    token = advance()
    left = parse_prefix(token)

    while next_token_is_operator() and left_bp(peek()) > min_bp:
        op = advance()
        left = parse_infix(op, left)

    return left

The prefix handler builds the first expression. The loop then repeatedly extends that expression with operators that are allowed to bind at the current level.

5. Trace One Expression Before Writing Code

For 1 + 2 * 3, the outer parser begins with 1. It sees + and asks for a right-hand expression in a context strong enough to prevent another equally weak + from stealing too much. Inside that recursive call, 2 is parsed. The next token is *, whose binding power is higher, so the inner call accepts it and builds 2*3. When the inner call returns, the outer parser builds 1+(2*3).

If you can narrate that stopping behaviour, you understand the algorithm better than someone who merely remembers a 20-line implementation.

6. Associativity Comes From Asymmetric Binding Powers

A convenient modern formulation gives each infix operator a left and right binding power.

For a left-associative operator such as subtraction, choose the right side slightly stronger than the left context, so a second subtraction does not become part of the first operator’s right operand. For a right-associative operator such as exponentiation, reverse that relationship so the next exponentiation is allowed inside the right operand.

left associative + : (10, 11)
right associative ^: (30, 29)

Different implementations encode the inequality differently, so do not memorise the exact numbers independently of the loop condition. Memorise the desired tree shape and derive the pair from it.

7. Prefix Operators Are Naturally Recursive

For unary minus:

-a * b

The prefix handler for - parses an operand at a sufficiently strong binding power, then creates a unary AST node. This lets unary minus bind more tightly than multiplication but potentially less tightly than some other operator if the language specifies that.

8. Parentheses Reset the Context

When ( appears in prefix position, parse a full expression inside it, require ), and return the nested expression. Parentheses do not need a new precedence algorithm; they create a local context in which low-precedence operators are again permitted.

9. Pratt Parsing Becomes Powerful With Postfix Forms

Once an expression exists on the left, the same loop can support:

function calls: f(x)
indexing: a[i]
member access: obj.field
postfix increment or factorial in languages that have them

These forms typically bind very tightly. Their infix/postfix parselets receive the already-parsed left expression and extend it.

10. Build an AST, Do Not Hide Parsing Inside Evaluation

A teaching parser may evaluate arithmetic directly, but a professional parser usually constructs an abstract syntax tree:

Binary(
  op="+",
  left=Number(1),
  right=Binary(op="*", left=Number(2), right=Number(3))
)

Separating parsing from evaluation gives you clearer error handling, optimisation, static analysis, formatting, compilation and testing.

11. Complexity Is Usually Linear in the Token Count

For a well-formed expression grammar, each token is consumed a constant number of times, so parsing is typically O(n) in the number of tokens. Recursion depth depends on expression structure and associativity. Extremely deep or adversarial input may therefore require recursion-depth controls or an iterative design.

12. Error Reporting Is Part of the Algorithm’s Quality

A parser is not finished when valid input works. It must explain invalid input:

missing operand after an operator
unexpected token in prefix position
missing closing delimiter
operator used in a context where no parselet exists
non-associative operator repeated illegally

Preserve token locations and source spans so diagnostics can point to the actual problem. Recovery strategy depends on whether Pratt parsing is embedded inside a larger recursive-descent parser.

13. Pratt Parsing Is Usually One Part of a Parser

Pratt parsing excels at expression subgrammars. It does not imply that an entire programming language should be expressed only as Pratt rules. Statements, declarations, indentation, type syntax and context-sensitive constraints may be clearer with other recursive-descent or generated-parser techniques.

The professional question is not “Is Pratt best?” but “Which syntactic region benefits from token-centred binding-power parsing?”

14. Production Tests Should Assert Trees, Not Just Values

Two different parse trees can evaluate to the same number for some inputs. Tests should therefore compare AST structure.

Useful cases include:

a+b*c
a-b-c
a^b^c
-a*b
f(x)[i].field
nested parentheses
missing delimiters
long operator chains

15. Common Failure States

Memorising precedence numbers without understanding the stopping rule.
Confusing precedence with associativity.
Using one handler for a token that has different prefix and infix meanings.
Evaluating while parsing and making the parser hard to test or extend.
Forgetting that postfix operators participate in the same binding system.
Using the wrong inequality for the chosen left/right binding-power convention.
Assuming valid-input parsing is enough without source-aware diagnostics.

16. Practice Ladder: Beginner to Professional

Beginner: draw parse trees for mixed arithmetic expressions.
Foundation: assign binding powers and trace exactly when the loop stops.
Intermediate: implement literals, prefix minus, addition, multiplication and parentheses.
Advanced: add right-associative exponentiation, calls, indexing and member access while asserting AST shape.
Professional: add source spans, diagnostics, recovery boundaries, recursion controls and a table-driven operator definition.
Transfer: compare Pratt parsing with precedence climbing and layered recursive descent, explaining the trade-offs rather than declaring one universally superior.

17. A Better Way to Study Pratt Parsing

Start with prediction and tracing. Give the learner a token stream and the current min_bp, then ask which operator the parser will consume next and which recursive call will be made. Only after several traces should the learner modify the operator table or add a new parselet. This follows computing-education evidence that code reading, prediction and structured modification can support novices before open-ended construction.

Learning Hall Boundary

This article owns Pratt/top-down operator-precedence parsing as a focused expression-parsing technique. It complements rather than replaces the existing general parsing-algorithms article, Earley parsing, regular-expression matching, compiler instruction, MindOS learning-process material, Bolt calibration work or Student/Studying Interface jobs.

Evidence Boundary

Vaughan R. Pratt introduced Top Down Operator Precedence at POPL 1973: ACM Digital Library record. Pratt’s original paper is also available in a readable historical transcription at tdop.github.io. Modern explanations that clarify binding-power formulations include Matklad’s Simple but Powerful Pratt Parsing and Eli Bendersky’s Top-Down Operator Precedence Parsing. The learning sequence also reflects PRIMM-style programming pedagogy: predict, run, investigate, modify, then make.

Professional rule: you understand Pratt parsing when you can derive precedence and associativity from the loop’s stopping condition, predict the AST before execution, and extend the parser without turning binding-power numbers into unexplained magic constants.

Small Group Tutorials