https://louis.co.nz/2026/03/26/pratt-parsing.html

back

2026-03-26

Intuiting Pratt parsing

You already know that a + b * c + d is calculated as a + (b * c) + d.
But how do you encode that knowledge precisely enough for a machine
to act on it?

The most common solution employed by compilers is to make use of a
tree known as an abstract syntax tree. In an AST, each operator sits
above its operands, and evaluation works bottom-up: resolve the
children, then apply the operation.

     +
    / \
   +   d
  / \
 a   *
    / \
   b   c

This tree encodes the desired ordering (a + (b * c)) + d in a format
that is very convenient to work with programmatically.

But of course, people (for the most part) don't write programs as
trees. This means we face the problem of deriving this structure from
flat text.

This is known as parsing. It has been the focus of decades of
computer science research. It has also, in many cases, been wildly
overcomplicated.

Simplifying

The difficulty in parsing lies with mixed precedence. To be precise,
cases where precedence changes direction. Let's imagine our users
only ever wrote programs of either increasing or decreasing
precedence. What would that mean for our tree representation?

In the case of decreasing precedence, we repeatedly evaluate the
leftmost operator as it is higher precedence - multiplication before
addition, addition before comparison, and so on. The first operator
sits deepest in the tree, the last the shallowest. The resulting tree
is left-leaning.

Decreasing

       <
      / \
     +   d
    / \
   *   c
  / \
 a   b

You can imagine what happens when precedence is increasing. It's the
exact opposite: the leftmost operator is now the shallowest and the
rightmost the deepest, as each operator depends on the result to its
right. The tree is right-leaning.

Increasing

   >
  / \
 a   +
    / \
   b   *
      / \
     c   d

Now, what is the most reasonable encoding of equal precedence?

It depends on the operation. Convention favours a left-to-right
evaluation for arithmetic, known as left associativity. Some language
features favour the opposite: assignment in C, for instance, is right
associative.

Let's suppose (for now) that all operators are left associative. This
is represented by a left-leaning tree, as the leftmost operator must
be evaluated earlier and therefore rests deeper in the tree.

We should refine our definitions accordingly. Given a sequence of
operators, let x_i be the precedence of the ith operator:

  * Decreasing: weakly decreasing - x_i >= x_{i+1}. This now includes
    the case of equal precedence.
  * Increasing: strictly increasing - x_i < x_{i+1}.

This means any two equal-precedence operators are encoded exactly
like two decreasing ones.

Extending

A natural continuation is to consider expressions with exactly one
change in direction. We'll focus on the more interesting of the two
resulting cases: a transition from increasing to decreasing
precedence. The reverse simply continues a right-leaning tree from
the tip of the existing left-leaning.

Consider the expression I = (a > b + c * d), given by the tree below.

   >
  / \
 a   +
    / \
   b   *
      / \
     c   d

The tree is right-leaning, as expected for increasing precedence.
Now, suppose we extend I with a new operator whose precedence is
equal to or less than *. This would mean the increasing property no
longer holds, and so continuing a right-leaning tree would produce an
incorrect encoding.

We need a left-leaning tree somewhere, but where? The visualisation
of each possible precedence level for the new operator begins to
reveal a pattern:

[I] * e:

   >
  / \
 a   +
    / \
   b   *
      / \
     *   e
    / \
   c   d

[I] + e:

   >
  / \
 a   +
    / \
   +   e
  / \
 b   *
    / \
   c   d

[I] == e:

     ==
    /  \
   >    e
  / \
 a   +
    / \
   b   *
      / \
     c   d

The left-leaning tree starts at the first place it can: at an
operator of equal or lesser precedence. This lower precedence
operator must evaluate later than at least the current one, but there
could be several prior operators that also must evaluate first. Those
operators are found along the spine of the right-leaning tree.

    The == case is the clearest example. All previous operators are
    higher precedence than ==, so the entire spine of the tree must
    evaluate first, and therefore must be its left child.

The observation is as follows: when we encounter a transition
operator, we must walk back up the spine, collecting every operator
that evaluates first. That collected chain - a right-leaning subtree
- becomes the left child of the new operator, which starts a
left-leaning tree of its own.

Since any expression is just a sequence of these transitions, this is
all we need. This walk-back procedure is Pratt parsing.

Parsing

We can hopefully make things a little more concrete with some
pseudocode, extending the right-leaning case to handle a transition
as we did earlier.

Right Leaning

A right-leaning tree can be built by recursing onto ourselves and
then building the tree bottom up.

def parse():
    left = leaf()

    if peek() is not None:
        op = advance()
        right = parse()
        return Node(op, left, right)

    return left

parse() first defers to leaf() to handle a literal such as a,
consuming it from the token stream before checking the next token
with peek(). The next token (an operator for a valid program) is
consumed by advance() which moves the parser to the next token. parse
() finally calls itself for the right-hand side.

The parser advances through the tokens as it recurses, and constructs
the tree as it returns. For our earlier tree [I]:

-- Down: advance

(1) parse(0)
    a [>] b  +  c  *  d

(2) parse(prec(>))
    a  >  b [+] c  *  d

(3) parse(prec(+))
    a  >  b  +  c [*] d

(4) parse(prec(*))
    a  >  b  +  c  *  d [None]


-- Up: build

(4)  d

(3) [*]
    / \
   c   d

(2) [+]
    / \
   b   *
      / \
     c   d

(1) [>]
    / \
   a   +
      / \
     b   *
        / \
       c   d

The use of recursion is how we will backtrack to find a continuation
point.

Until then, our parser produces incorrect trees for decreasing
precedence. To prevent parsing tokens we shouldn't, we can forward
the current precedence to the recursive child call:

def parse(prev_prec=0):
    left = leaf()

    if peek() is not None and prec(peek()) > prev_prec:
        op = advance()
        right = parse(prec(op))
        return Node(op, left, right)

    return left

This works, but we can simplify by giving end-of-file its own token
with the lowest precedence - peek() would cause the condition to fail
naturally, letting us drop the null check:

def parse(prev_prec=0):
    left = leaf()

    if prec(peek()) > prev_prec:
        op = advance()
        right = parse(prec(op))
        return Node(op, left, right)

    return left

Left Leaning

As parse() recurses, it pushes a frame onto the call stack with the
left child and minimum precedence. The call stack, representing the
yet-to-be-built spine, is always of increasing precedence.

This means that when unwinding, we visit each level in decreasing
order. So, the first level where peek() can bind is also the correct
level: every level above is strictly lower in precedence, and we
already know it can't go deeper because parse() wouldn't have
returned. The greedy choice is the only correct choice.

But if is only capable of taking that greedy choice once - we need to
take it every time, because anything else is incorrect. So, we
replace if with while:

def parse(prev_prec=0):
    left = leaf()

    while prec(peek()) > prev_prec:
        op = advance()
        right = parse(prec(op))
        left = Node(op, left, right)

    return left

This is the complete Pratt parser. The while loop is the walkback
procedure we described earlier: when a transition operator appears,
parse() returns up the call stack until it finds the right level,
then the loop consumes it and continues with the left-leaning
subtree.

Here's the trace [I] * e, where I = a > b + c * d:

-- Down: advance
(1) a [>] b  +  c  *  d  *  e
(2) a  >  b [+] c  *  d  *  e
(3) a  >  b  +  c [*] d  *  e
(4) a  >  b  +  c  *  d [*] e  FAIL

-- Up: build

(4)  d

(3)  iteration 1:
     [*]
     / \
    c   d

     iteration 2:
     [*]
     / \
    *   e
   / \
  c   d

(2) [+]
    / \
   b   *
      / \
     *   e
    / \
   c   d

(1) [>]
    / \
   a   +
      / \
     b   *
        / \
       *   e
      / \
     c   d

The left-leaning subtree (c * d) * e is built entirely within frame
3's while loop.

Right Associativity

In practice every operator has two types of precedence: left and
right. Pratt refers to this as left and right binding power, or LBP
and RBP. All of our operators so far have an equal LBP and RBP.

An operator's LBP determines how strongly it attracts the expression
to its left - this is what peek() checks in the while condition. Its
RBP determines how strongly it attracts the expression to its right -
this is what gets passed as prev_prec to the recursive call.

For left-associative operators, LBP and RBP are equal. When two *
operators meet, the second *'s LBP is not greater than the first *'s
RBP, so parse() does not recurse but instead loops at the same level
to build left.

We want the opposite for right-associative operators. a = b = c
should parse as a = (b = c). The second = should be consumed by the
recursive call, not by the loop. We can achieve this by setting RBP
lower than LBP - the recursive child's precedence threshold is low
enough that a consecutive operator still passes the > check and gets
consumed deeper.

def parse(prev_prec=0):
    left = leaf()

    while lbp(peek()) > prev_prec:
        op = advance()
        right = parse(rbp(op))
        left = Node(op, left, right)

    return left

To ensure this, we set rbp = lbp for left-associative operators, and
rbp = lbp - 1 for right-associative.

Summary

I've often found Pratt parsing to be presented as if it were a clever
trick. Well, it is, but with a very simple geometric intuition: trees
are either left-leaning or right-leaning depending on precedence.
When precedence drops, walk back up the spine until you find where
the new operator belongs.

I've read many articles on the same topic but never found it
presented this way - hopefully N + 1 is of help to someone.

[test-img]