Writing a Pratt Parser

Published on July 20, 2026 · 7 min read

Technology #ast #golang #interfaces #interpreters #learning-in-public #monkey-language #parser #pratt-parsing #thorsten-ball

The lexer from last post handed back a flat stream of tokens and had no opinion about whether they meant anything. let x = ; tokenized without a single complaint. This post is where the tokens finally get read for meaning, and where that broken line gets rejected.

Same as last time, a working definition before anything else:

A parser takes a flat sequence of tokens and builds a structure that shows how they relate. For a programming language that structure is an abstract syntax tree, or AST: a tree that captures what nests inside what.

From Tokens to a Tree

The lexer turned let x = 10; into this:

LET  IDENT("x")  ASSIGN  INT("10")  SEMICOLON

That is a list. It has an order, but no shape. Nothing in it says that 10 is the value being bound to x, or that the five tokens together are one statement. The parser reads that list and builds the shape:

LetStatement
├── Name:  Identifier("x")
└── Value: IntegerLiteral(10)

Now the relationships are explicit. There is one let statement, it binds a name, and the name gets a value. That tree is the thing every later stage of the interpreter will actually walk.

Modeling the Tree

The tree is built out of nodes, and Monkey has a lot of kinds: statements like let and return, and expressions like an integer, an identifier, or a function call. They are different shapes with different fields, but every one of them has to sit in the same tree and get walked by the same code later on.

Go lets you pull that off with an interface. Rather than forcing all of these types to look the same underneath, you spell out the small set of things a node has to be able to do, and any type that can do them counts as a node. A let statement and a bare integer share nothing in their fields, yet both are nodes because both satisfy that one interface.

Here is a toy version of that:

// A node is anything that can turn itself back into text.
type Node interface {
	String() string
}

type Integer struct{ Value int }

func (i Integer) String() string { return fmt.Sprintf("%d", i.Value) }

type Identifier struct{ Name string }

func (id Identifier) String() string { return id.Name }

// The code that walks the tree only ever sees a Node.
func printAll(nodes []Node) {
	for _, n := range nodes {
		fmt.Println(n.String())
	}
}

Integer and Identifier have nothing in common in their fields, but printAll treats them the same, because both carry a String method and that is all Node asks for.

What took getting used to is that a type never announces it. Nothing declares that a let statement is a node. It becomes one the moment it has the methods a node needs, and the compiler holds it to that from there. It nudges you to design the other way around: describe the behavior first, then let the concrete types line up behind it. TGPL Chapter 7 is where to go if interfaces still feel slippery.

The temptation is to make that node interface carry more than it should. Keeping it lean, only the handful of methods every node genuinely shares, is what lets me bolt on a new kind of node a few chapters from now without disturbing the ones already in the tree. 100 Go Mistakes has a section on exactly that restraint, and a growing AST is where it pays off.

The Precedence Problem

Building the tree is easy when the input is let x = 10;. It gets hard the moment there is arithmetic. Take this:

1 + 2 * 3

You already know that is 7 and not 9, because multiplication binds tighter than addition. The token stream does not carry that knowledge. It is just INT PLUS INT ASTERISK INT, five tokens in a row. If the parser walks them left to right and builds the tree in that order, it groups the first two and gets the wrong shape:

((1 + 2) * 3)

What it needs is to nest the multiply underneath the add:

(1 + (2 * 3))

Nothing in the tokens says to do that. The rule lives in the parser, and it means every operator has to carry a rank that says how tightly it binds.

How Pratt Parsing Works

A Pratt parser hangs on two ideas: every operator has a precedence, a number that says how tightly it binds, and every token type is tied to one or two small functions that know how to parse it.

The two functions cover the two places a token can appear. A prefix function handles a token at the start of an expression, like the - in -5 or an integer on its own. An infix function handles a token sitting between two expressions, like the + in 1 + 2, and it is handed the expression already parsed on its left. Each token type registers whichever of these apply, and the parser keeps them in a table keyed by token type.

Parsing an expression is then one loop with a precedence floor:

func (p *Parser) parseExpression(precedence int) ast.Expression {
	prefix := p.prefixParseFns[p.curToken.Type]
	if prefix == nil {
		return nil
	}
	left := prefix()

	for precedence < p.peekPrecedence() {
		infix := p.infixParseFns[p.peekToken.Type]
		p.nextToken()
		left = infix(left)
	}

	return left
}

It parses a left-hand side, then keeps folding operators into it as long as they bind tighter than the floor it was given. The first operator that binds looser ends the loop, and the function returns what it has, leaving that operator for whoever called it.

The recursion is what enforces precedence. When an infix function parses its own right-hand side, it calls parseExpression again using its operator’s precedence as the new floor. Run 1 + 2 * 3: the outer call parses 1, sees +, and its infix function parses the right side with +’s precedence as the floor. That inner call parses 2, sees * binding tighter than the floor, and pulls in 2 * 3 before returning. So + ends up with 1 on its left and 2 * 3 on its right, which is the shape we wanted.

For our parser the whole expression grammar reduces to that table. Register a prefix or infix function per token, give each operator a precedence, and start by calling parseExpression with the lowest floor. Adding a new operator later is one more function and one more precedence entry, not a rewrite.

Wrap Up

The pipeline is now source, to tokens, to a tree. The parser has opinions the lexer never did. Feed it let x = ; and it stops and reports an error, because there is no expression where it expects the value. That is the reason the parser exists at all: it is the first stage that can tell you that you are wrong.

What it still cannot do is run anything. 1 + 2 parses into a tidy little tree, but a tree is not a 3. Turning the tree into an answer is the next post, the tree-walking evaluator, which is Chapter 3 of Ball’s first book.

The code for this chapter is tagged in the companion repo if you want the full parser instead of the pieces I pulled out here.