How to Build a Pratt Parser

How does a program know that 2 + 3 * 4 is 14 and not 20? Before it can compute anything, it has to read the text and turn it into a tree that says which operation goes first. That is the job of a parser.

Hi! In this post I’m going to talk about one kind of parser, the Pratt parsera.k.a. top-down operator precedence parser, and how to build one in C. I learned it to write the expression parser for OrnMy range-based systems programming language, still very much a work in progress..

The idea comes from a 1973 paper by Vaughan Pratt^[3], but I learned it through Alex Kladov’s post^[1], Bob Nystrom’s post^[6] and this video^[2]. Kladov’s post is still the one I would recommend. This one takes a different path: it starts from the grammar you see in a Compilers course, shows why it gets painful, and builds the parser in C one step at a time, tracing every call.

I had already heard a lot about Pratt parsing from other developers talking about their parsers, and it sounded really cool: a single function that parses every expression, driven only by operator precedence. Last year I took Compilers at university, but we were only taught LL and LR parsingTwo families of parsers. LL parsers work top-down: they start from the whole expression and split it into parts, usually with one function per grammar rule (recursive descent). LR parsers work bottom-up: they join tokens into bigger pieces, and are usually generated by tools like yacc (SLR, LR(1) and LALR are variants of them)..

So I knew the name, but not how it actually worked. This post is what I learned building one.

You don’t need to know any parsing theory to follow along: every term is explained when it shows up.

The problem with grammars§

A grammar describes what a valid expression looks like. It is usually written in BNFBackus–Naur form. expr = expr '+' expr reads as “an expression can be an expression, then a +, then another expression”, and | separates the alternatives. Strictly, the notation in this post is closer to EBNF (Extended BNF): classic BNF writes <expr> ::= <expr> "+" <expr>.. You would typically write the grammar for a small language that can only add, subtract and multiply numbers and variablesA variable is a terminal, imagine it as a single character, like 'x'. It cannot be expanded. like this:

expr   = expr '+' expr
       | expr '-' expr
       | expr '*' expr
       | factor

factor = number
       | variable

It is easy to read, but it is ambiguous: 1 + 2 * 3 can be parsed as:

      *                  +      
     / \                / \            
    +   3      or      1   *
   / \                    / \          
  1   2                  2   3

(1 + 2) * 3          1 + (2 * 3)

To fix it, we need one rule per precedence level, from the lowest to the highest:

expr   = term
       | expr '+' term
       | expr '-' term

term   = factor
       | term '*' factor

factor = number
       | variable

If we also had division, it would go in term:

term = factor
     | term '*' factor
     | term '/' factor

Both * and / have the same precedence, so just as + and - are together, / will go with *.

But let’s keep division out.

The grammar is now unambiguous, but it has lost its simplicity. And it is left-recursive (expr = expr '+' term), so an LL parser, like the recursive descent one I use for Orn, can’t use it as it is: to parse expr it would first call expr, forever. To make it LL, the left recursion has to be removed^[4]:

expr    = term expr'
expr'   = '+' term expr'
        | '-' term expr'
        | ε

term    = factor term'
term'   = '*' factor term'
        | ε

factor  = number
        | variable

It works, but now there are two extra rules, an εε means “nothing”: that alternative matches without reading any token., and the original expr '+' expr is hard to recognize.

EBNF makes it a bit nicer. Its { ... } means “repeat zero or more times”, so the left recursion can be written as a repetition:

expr   = term { ('+' | '-') term }
term   = factor { '*' factor }
factor = number | variable

No ε and no extra rules, and each { } becomes a while loop in a recursive descent parser. But there is still one rule per precedence level: ten levels of operators are ten rules, and ten functions calling each other.

Pratt parsing takes a different path: it keeps the short, ambiguous grammar and moves precedence out of it, into a table.

Parsing a real expression, simulating the algorithm§

Take this expression:

a + b * c - d

The parser reads sequentially, from left to right. The first token is a, and right after it comes +. So we know that a will be added to something.

What is that something?§

We keep reading and the next token is b. If we stopped here, we would think the expression is a + b. But if we peek one token further, we see *:

a + b * c - d
    ^ ^
    | +-- next operator: *
    +---- current operand: b

Now b is caught between two operators, + on its left and * on its right, and both want it. Since * has higher precedence, b belongs to *, and the something that a is added to is not b but b * c, the expression built at its right.

┌────────────────────────
│     ┌───────────┐
│ a + │   b * c   │ ...
│     └───────────┘
└────────────────────────

When does that expression end?§

From b we keep going: *, then c. Peeking past c, we find another operator, -. Since - has lower precedence than *, it can’t take c away from *, so the multiplication is complete and we wrap it as b * c.

From now on, b * c behaves as a single unit, sitting between a + on its left and a - on its right. This time both have the same precedence, so the one on the left wins: + takes it, giving a + (b * c). That whole result then becomes the left side of -, and the expression ends with d.

That’s a lot of words, so here it is step by step:

step 1   a + b * c - d        'a' waits for the right side of '+'
         ^

step 2   a + b * c - d        'b': next is '*', stronger than '+', so '*' takes 'b'
             ^

step 3   a + (b * c) - d      next is '-', weaker than '*': wrap 'b * c'
                     ^

step 4   (a + (b * c)) - d    '-' is as strong as '+', the left one wins: close '+'
                       ^

step 5   ((a + (b * c)) - d)  'd' is the last token: close '-'
                          ^

Bringing this to real code§

I’ll write this in C. To keep it short, every operand is a single character (a digit or a letter) until the last section, where tokens become words. The input is assumed to be well-formed, so there is no error handling. The complete program, with a main() that parses one expression per line, is in the repo.

First we have to think about how much precedence an operator has. We will call this binding power.

For example, our last expression could be seen as: One value for each side of every operator.

a   +   b   *   c   -   d
  1   1   2   2   1   1

In code, the operators are an enum, and the binding powers a table indexed by it: We don’t really care about the value of ADD, … They come from an enum, so we know they are all different. NOT_OP marks a terminal that is not an operator

enum op_type {
	ADD,
	SUB,
	MUL,
	NOT_OP,
};

struct binding_powers {
	int left;
	int right;
};

static const struct binding_powers binding_table[] = {
	[ADD] = { 1, 1 },
	[SUB] = { 1, 1 },
	[MUL] = { 2, 2 },
};

But having both sides with the same binding power will make us face situations like:

a   -   b   -   c
  1   1   1   1

Where when standing on b, both sides have the same binding power. The code would still pick one: an equal left binding power is enough to get in, so b would go to the second -, giving a - (b - c).

With + that wouldn’t matter, but with - it does: (a - b) - c is not a - (b - c). Which way an operator groups when it repeats is its associativity: - is left associative, because the left one goes first. To fix it we need to make one of the sides greater. But which one?

We want (a - b) - c, so b has to choose the first -. Look at what b actually compares:

a   -   b   -   c
      ^   ^
      |   +-- left side of the second '-'
      +------ right side of the first '-'

It is the right side of - against its left side. For the left side to win, the operator’s right side has to be greater than its left side.

For right associative operators like = or ^ it is the reverse: you make the left side greater.

static const struct binding_powers binding_table[] = {
	[ADD] = { 1, 2 },
	[SUB] = { 1, 2 },
	[MUL] = { 3, 4 },
};

a   -   b   -   c
  1   2   1   2

And it is clear that on b, it will be wrapped to the left. Same for our first expression:

a   +   b   *   c   -   d
  1   2   3   4   1   2

The algorithm§

With our table and everything we have talked about, we can move on to the actual algorithm. First, the helpers that we are going to need.

A node holds a character, its lexeme: the piece of the input it was read from. Operators are inner nodes: their left and right sides point to other nodes. Operands like a are leaves, with no children.

struct node {
	char lex;
	struct node *lhs;
	struct node *rhs;
};

static struct node *make_node(char lex, struct node *lhs, struct node *rhs)
{
	struct node *n = malloc(sizeof *n);
	n->lex = lex;
	n->lhs = lhs;
	n->rhs = rhs;
	return n;
}

The input is a string, and src points to the first character of that string. next() moves src to the next character, skipping spaces:

static const char *src;

static void next(void)
{
	src++;
	while (*src == ' ')
		src++;
}

And get_type() tells us which is the type of any character: For simplicity we will only differentiate between operators, while operands (including '\0') will be just labeled as NOT_OP

static enum op_type get_type(char c)
{
	switch (c) {
	case '+': return ADD;
	case '-': return SUB;
	case '*': return MUL;
	default: return NOT_OP;
	}
}

Printing the tree§

To see what the parser built, we print the tree as an S-expression The notation Lisp uses: the operator first, then its operands, all inside parentheses.. Every operation becomes (op lhs rhs) and every operand is printed as it is, so a + b * c comes out as (+ a (* b c)).

static void print_sexpr(const struct node *n)
{
	if (!n->lhs && !n->rhs) {
		putchar(n->lex);
		return;
	}
	printf("(%c ", n->lex);
	if (n->lhs) {
		print_sexpr(n->lhs);
		putchar(' ');
	}
	print_sexpr(n->rhs);
	putchar(')');
}

A node with no children is an operand. Any other node prints its operator and its children inside parentheses. The if (n->lhs) is for prefix operators, which only have a right child. We will get to them later.

Let’s break it down§

Our so-talked-about Pratt parser:

static struct node *parse_expr(int min_bp)
{
	struct node *lhs = make_node(*src, NULL, NULL);
	next();

	for (;;) {
		char c = *src;
		enum op_type op = get_type(c);
		if (op == NOT_OP)
			break;

		struct binding_powers bp = binding_table[op];
		if (bp.left < min_bp)
			break;

		next();
		struct node *rhs = parse_expr(bp.right);
		lhs = make_node(c, lhs, rhs);
	}

	return lhs;
}

Here is the whole run. Each box inside another box is a recursive call to parse_expr(), and the number in parentheses is its min_bp. On the right, the S-expression. Using the same expression from the start: a + b * c - d

┌─ parse_expr(0) ─────────────────────────────┐
│ lhs = a                                     │
│ '+' 1 >= 0, take it                         │ (+ a
│ ┌─ parse_expr(2) ─────────────────────────┐ │
│ │ lhs = b                                 │ │
│ │ '*' 3 >= 2, take it                     │ │ (+ a (* b
│ │ ┌─ parse_expr(4) ─────────────────────┐ │ │
│ │ │ lhs = c                             │ │ │
│ │ │ '-' 1 < 4, return c                 │ │ │
│ │ └─────────────────────────────────────┘ │ │
│ │ lhs = b * c                             │ │ (+ a (* b c)
│ │ '-' 1 < 2, return b * c                 │ │
│ └─────────────────────────────────────────┘ │
│ lhs = a + (b * c)                           │ (+ a (* b c))
│ '-' 1 >= 0, take it                         │ (- (+ a (* b c))
│ ┌─ parse_expr(2) ─────────────────────────┐ │
│ │ lhs = d                                 │ │
│ │ end of input, return d                  │ │
│ └─────────────────────────────────────────┘ │
│ lhs = (a + (b * c)) - d                     │ (- (+ a (* b c)) d)
│ end of input, return                        │
└─────────────────────────────────────────────┘

Every call repeats the same steps: build a left-hand side, look at the next operator, and check whether its left binding power is at least min_bp.

Put another way, parse_expr(min_bp) returns the longest expression whose operators all have a left binding power of at least min_bp. The first operator that is too weak ends it, and it is left for one of the calls above to take.

Parentheses and prefix operators§

So far parse_expr() starts by turning the current character into an operand. Parentheses and prefix operators like !x also show up where an operand is expected, so that first step needs more cases. The prefix ! also gets its own entry in the table: Plus a case '!': return NOT; in get_type().

enum op_type {
	ADD,
	SUB,
	MUL,
	NOT,
	NOT_OP,
};

static const struct binding_powers binding_table[] = {
	[ADD] = { 1, 2 },
	[SUB] = { 1, 2 },
	[MUL] = { 3, 4 },
	[NOT] = { -1, 5 },
};

The first two lines of parse_expr() become:

	struct node *lhs;
	char c = *src;

	if (c == '(') {
		next();
		lhs = parse_expr(0);
		next(); /* skip ')' */
	} else if (c == '!') {
		next();
		lhs = make_node(c, NULL, parse_expr(binding_table[NOT].right));
	} else {
		lhs = make_node(c, NULL, NULL);
		next();
	}

The loop stays the same.

Parentheses call parse_expr() with 0: inside them we start fresh, so any operator is strong enough no matter what is outside. That is all it takes for (a + b) * c to work.

A prefix operator has nothing on its left, so its node has no lhs. But get_type() now returns NOT for !, so the loop does look at its left binding power. That is why it is -1: min_bp is never below 0, so the loop always stops on ! and never takes it as if it came after an expression. With a 0 there, a ! b would sneak in as (! a b).

What matters is the right one: the operand is parsed with parse_expr(5), so only operators with a left binding power of at least 5 can get into it. For !a * b:

┌─ parse_expr(0) ─────────────────────────────┐
│ '!' is prefix, parse its operand            │
│ ┌─ parse_expr(5) ─────────────────────────┐ │
│ │ lhs = a                                 │ │
│ │ '*' 3 < 5, return a                     │ │
│ └─────────────────────────────────────────┘ │
│ lhs = !a                                    │ (! a)
│ '*' 3 >= 0, take it                         │ (* (! a)
│ ┌─ parse_expr(4) ─────────────────────────┐ │
│ │ lhs = b                                 │ │
│ │ end of input, return b                  │ │
│ └─────────────────────────────────────────┘ │
│ lhs = (!a) * b                              │ (* (! a) b)
│ end of input, return                        │
└─────────────────────────────────────────────┘

What about right associativity?§

Every operator so far has its right side higher than its left, so all of them are left associative. To make one right associative, its right side has to be lower. For example, a power operator: Plus a POW in the enum and a case '^' in get_type().

	[POW] = { 7, 6 },

In a ^ b ^ c, the first ^ parses its right side with a minimum of 6. The second ^ has a left binding power of 7, so it gets in, and the result is a ^ (b ^ c).

Since 7 is higher than the 5 of !, ^ also gets into its operand: !a ^ b is (! (^ a b)). To get (!a) ^ b instead, give NOT a right binding power higher than 7.

Beyond arithmetic, what else can we do?§

Until now, every token had one of two jobs. In the first part of parse_expr() it starts an expression: an operand, a ( or a !. In the loop it comes after an expression that is already built: +, -, *, ^. Pratt calls these two jobs nud and ledNull denotation and left denotation. The led is the one that receives the expression on its left.^[3].

Nothing says a led has to be “an operator and then an expression”. It receives the left-hand side, returns a new one, and in between it can do whatever it wants. That is what takes Pratt parsing way beyond arithmetic expressions.

Indexing and calls§

a[b] is an infix [ with a very strong left binding power. Instead of parsing its right side with a binding power, it parses a whole expression from 0, like parentheses do, and then skips the ]. A call f(a) is exactly the same with (.

	[INDEX] = { 9, 0 }, /* right side is never used */
	[CALL]  = { 9, 0 },

With case '[': return INDEX; and case '(': return CALL; in get_type(). The same goes for . and , below.

In the loop, right after next():

		if (op == INDEX || op == CALL) {
			struct node *inside = parse_expr(0);
			next(); /* skip ']' or ')' */
			lhs = make_node(c, lhs, inside);
			continue;
		}

] and ) are NOT_OP, so the inner parse_expr(0) stops right on them. An empty call like f() needs one extra check: if the next character is already ), skip it without parsing anything.

Notice that ( now lives in both places. As a nud it groups, as a led it calls. The parser never mixes them up, because it always knows where it is: if there is no expression yet, it is a nud; if there is one on its left, it is a led. The same trick separates a unary -a from a binary a - b, although then - needs two rows, one for each job, so real parsers usually keep a prefix table and an infix table^[1].

Member access§

. is a plain infix operator, the strongest of all and left associative:

	[DOT] = { 9, 10 },

a.b.c is (. (. a b) c), and since ., [ and ( share the same left binding power, they chain from left to right: a.b[c] is ([ (. a b) c). It also plays well with the prefix operators: !a.b is (! (. a b)), because 9 is higher than the 5 of !.

The right side of . should be a name, not any expression. The parser can check that the node it got back has no children, or leave it to a later pass.

The comma§

, can be an operator too, the weakest one:

	[COMMA] = { 0, 1 },

A left binding power of 0 means it is only taken where we start fresh: at the top level or inside (, [ and calls. So f(a, b, c) gives its call node (, (, a b) c) as the argument, a left-leaning list that is easy to flatten later.

C actually has a comma operator, but having it everywhere is not always what you want. The other option is to keep , out of the table and let the call led loop by itself: parse one argument with parse_expr(0), which stops on , because it is NOT_OP, and while the next character is ,, skip it and parse another one.

if, fn and friends§

Keywords like if and fn are longer than one character, so first the lexerThe part that splits the input into tokens. has to learn to read words. src still points to the current token, and a new len says how long it is:

static const char *src; /* start of the current token */
static int len;         /* length of the current token */

static void next(void)
{
	src += len;
	while (*src == ' ')
		src++;

	len = 0;
	while (isalnum((unsigned char)src[len]))
		len++;
	if (len == 0 && *src)
		len = 1;
}

next() skips the current token and the spaces after it, then measures the next one: a run of letters and digits, or a single character otherwise. That second case is what keeps +, ( and the rest working as before. Since len starts at 0, we call next() once before parsing, so it holds the first token.

Two small helpers work on that token. is() checks whether it is a given word, and take() returns it as a string and moves to the next onebool needs <stdbool.h> before C23, and strndup() is POSIX.:

static bool is(const char *word)
{
	return !strncmp(src, word, len) && word[len] == '\0';
}

static char *take(void)
{
	char *lex = strndup(src, len);
	next();
	return lex;
}

Nodes now hold a char *lex instead of a char. Wherever we used c and then called next(), we now call take(): an operand becomes make_node(take(), NULL, NULL), and in the loop next() becomes char *lex = take();, with lex going into make_node() instead of c. Careful with !: in make_node(take(), NULL, parse_expr(...)), C doesn’t say which argument is evaluated first, so take() goes on its own line:

	} else if (get_type(*src) == NOT) {
		char *lex = take();
		lhs = make_node(lex, NULL, parse_expr(binding_table[NOT].right));
	}

get_type() doesn’t change: words start with a letter or a digit, so they are NOT_OP. That is also what makes else stop the loop.

With that, if is one more nud. It reads a condition, a branch and maybe an else, which goes in a third child, elsmake_node() now uses calloc(), so els starts as NULL.:

	} else if (is("if")) {
		lhs = make_node(take(), NULL, NULL);
		lhs->lhs = parse_expr(0);
		lhs->rhs = parse_expr(0);
		if (is("else")) {
			next();
			lhs->els = parse_expr(0);
		}
	}

print_sexpr() prints the lexeme with %s and the else branch after the other two:

static void print_sexpr(const struct node *n)
{
	if (!n->lhs && !n->rhs) {
		fputs(n->lex, stdout);
		return;
	}
	printf("(%s ", n->lex);
	if (n->lhs) {
		print_sexpr(n->lhs);
		putchar(' ');
	}
	print_sexpr(n->rhs);
	if (n->els) {
		putchar(' ');
		print_sexpr(n->els);
	}
	putchar(')');
}

if x y else z + 1 gives (if x y (+ z 1)), and if a if b c else d gives (if a (if b c d)): the else goes to the closest if.

There is a catch: in if c (x), the ( is taken as a call, so the condition becomes c(x). Rust avoids this kind of problem by requiring a block { } after the condition.

A block { ... } could be another nud that parses expressions separated by ; until }. And fn(x) { ... } could be a nud that reads the parameters, parses the body and returns a function node, a function without a name. Since the loop still runs after any nud, that function can be called right where it is written: in fn(x) { x * 2 }(3), the ( after the } is just a call, so it defines a function that doubles its argument and calls it with 3. Neither is in the repo, but both are only more cases at the start of parse_expr().

This is how expression-oriented languages like Rust, Ruby or the Lisps see the world: if gives back a value, and so does a group of expressions (a block in Rust, begin ... end in Ruby, progn in Common Lisp), so they are expressions like any other.

Douglas Crockford took it further and parsed a subset of JavaScript, statements included, with nothing but TDOPa.k.a. Pratt parser, adding a third job, std, for statements like var and return^[5].

At that point the whole parser is parse_expr() and a table where every token says what it does at the start of an expression and what it does after one.

Conclusion§

At the start, every precedence level was a new grammar rule, and to make it work in a recursive descent parser we had to remove left recursion and add rules with ε. With Pratt parsing, the grammar stays the short, ambiguous one, and precedence and associativity live in a table.

yacc and Bison use the same idea: an ambiguous grammar plus %left and %right declarations to build LR parsers. Pratt does it by hand, inside a recursive descent parser. The same loop is also known as precedence climbing, which is essentially the same algorithm with a different way of writing the precedences.

The whole expression parser is one loop and one table, and adding an operator is adding a row: comparisons, && and || are only more rows. This is the approach I’m taking for the expression parser of Orn.

What this post leaves out is error handling. A real parser has to say what is wrong with a + or an unclosed (, and recover to keep going. That is another post.

So the final grammar is still the short one from the start, with a few more alternatives, plus a table:

static const struct binding_powers binding_table[] = {
	[COMMA] = { 0, 1 },
	[ADD]   = { 1, 2 },
	[SUB]   = { 1, 2 },
	[MUL]   = { 3, 4 },
	[NOT]   = { -1, 5 },
	[POW]   = { 7, 6 },
	[INDEX] = { 9, 0 },
	[CALL]  = { 9, 0 },
	[DOT]   = { 9, 10 },
};

expr  = expr binop expr
      | expr '(' expr ')'
      | expr '[' expr ']'
      | atom

atom  = number
      | name
      | '(' expr ')'
      | '!' expr
      | 'if' expr expr
      | 'if' expr expr 'else' expr

binop = ',' | '+' | '-' | '*' | '^' | '.'

On its own it is still ambiguous. The table decides how operators group, and the parser decides that an else goes to the closest if.

Chao, Pablo