Generalizing Pratt Parsers, Part 1

Sam Vervaeck — Sat, 11 Jul 2026 18:08:38 +0000

During the design of my parser generator Mage, I encountered a problem with correctly generating parsers for expressions.

Let's say we have this definition for an expression in BNF:

expr ::= int_expr
       | ref_expr
       | add_expr
       | sub_expr
       | mul_expr
       | div_expr

It should parse things like 1 + 2, 1 + 2 * 3 and 1 / 2 * 3 - 4 + 5.

The closest equivalent grammar in Mage would be:

pub expr
  = try add_expr
  | try sub_expr
  | try mul_expr
  | try div_expr
  | int_expr
  | ref_expr

Note that the try keyword in this example attempts to parse whatever comes next to it, and cleanly resets the stream to right before the try-expression was executed. Without it, add_expr might parse a single int_expr and advance the stream, but when it fails to parse the + the stream may remain after the int_expr.

Going further, here are some sample implementations of int_expr and ref_expr. We don't need them to be complete; we want them to be just useful enough to experiment with them.

pub int_expr
  = [0-9]+

pub ref_expr
  = [a-z]+

Finishing off our tiny grammar, we define four binary expressions:

pub add_expr
  = expr '+' expr

pub sub_expr
  = expr '-' expr

pub mul_expr
  = expr '*' expr

pub div_expr
  = expr '/' expr

Two Problems

We can immediately experience a first problem. This grammar appears to be a valid Mage grammar, but it wil execute forever. Say we give it simply foo as input. It will attempt to parse expr, then try add_expr, followed by expr and add_expr, going deeper and deeper and never coming to a halt.

Moreover, given the input 1 + 2 * 3, this grammar doesn't inform Mage whether we prefer (1 + 2) * 3 or 1 + (2 * 3). Which one is correct?

A Textbook Solution

We always need to parse something, right? Even if it is a small, tiny little atom. Let's therefore first define what can be safely parsed without any ugly infinite loops:

pub atom
  = int_expr
  | ref_expr

Parsing atom should never result in the infinite loop we saw earlier. Indeed, it can correctly parse 12345 and foobar.

Next, the textbook approach to avoid this infinite loop is to narrow down the possibilities that can be consumed while it descends into expr.

We define factor as the thing that is parsed within a multiplication, and term the thing that is parsed within addition or subtraction. After all choices have been exhausted, we delegate term to factor, which in turn delegates to atom.

pub term
  | try add_expr
  | try sub_expr
  | factor

pub add_expr
  = factor '+' term

pub sub_expr
  = factor '-' term

pub factor
  = try mul_expr
  | try div_expr
  | atom

pub mul_expr
  = atom '*' factor

pub div_expr
  = atom '/' factor

pub expr
  = term

Note that a factor is closer to the 'ground' than a term, in the sense that it is closer to atomic formulae. This gives it a higher binding power than term.

When we e.g. parse 1 + 2 * 3, we first parse add_expr, which succeeds parsing a 1 and a +. We then continue parsing a term that delegates to factor, which in turn succeeds parsing mul_expr.

Pratt Parsing

We could abstract the previous technique to automatically transform Mage grammars so that they once again become executable, but this transformation is far from trivial. There's also the concern for speed: these try expressions can become overly expensive.

The question is: how do we generalize this approach and make it efficient? That's where Pratt parsing comes in.

The most popular article about Pratt parsing seems to be the one by Bob Nystrom, the guy who wrote the famous book Crafting Interpreters. I personally prefer the article by Alex Kladov, one of the maintainers of rust-analyzer.

A Pratt parser is more of a technique than an algorithm. The defining ingredient of a Pratt parser is precedence, or as Kladov calls it, binding power. Sub-expressions with a higher precedence appear deeper in the AST than sub-expressions with a lower precedence.

This code comes straight from Kladov's article:

fn expr_bp(lexer: &mut Lexer, min_bp: u8) -> S {
    let mut lhs = match lexer.next() {
        Token::Atom(it) => S::Atom(it),
        Token::Op('(') => {
            let lhs = expr_bp(lexer, 0);
            assert_eq!(lexer.next(), Token::Op(')'));
            lhs
        }
        Token::Op(op) => {
            let ((), r_bp) = prefix_binding_power(op);
            let rhs = expr_bp(lexer, r_bp);
            S::Cons(op, vec![rhs])
        }
        t => panic!("bad token: {:?}", t),
    };
    loop {
        let op = match lexer.peek() {
            Token::Eof => break,
            Token::Op(op) => op,
            t => panic!("bad token: {:?}", t),
        };
        if let Some((l_bp, ())) = postfix_binding_power(op) {
            if l_bp < min_bp {
                break;
            }
            lexer.next();
            lhs = if op == '[' {
                let rhs = expr_bp(lexer, 0);
                assert_eq!(lexer.next(), Token::Op(']'));
                S::Cons(op, vec![lhs, rhs])
            } else {
                S::Cons(op, vec![lhs])
            };
            continue;
        }
        if let Some((l_bp, r_bp)) = infix_binding_power(op) {
            if l_bp < min_bp {
                break;
            }
            lexer.next();
            lhs = if op == '?' {
                let mhs = expr_bp(lexer, 0);
                assert_eq!(lexer.next(), Token::Op(':'));
                let rhs = expr_bp(lexer, r_bp);
                S::Cons(op, vec![lhs, mhs, rhs])
            } else {
                let rhs = expr_bp(lexer, r_bp);
                S::Cons(op, vec![lhs, rhs])
            };
            continue;
        }
        break;
    }
    lhs
}

In this Gist, I re-implement the algorithm in Python with a few changes.

First, my implementation uses .tell() and .seek() to save and restore the position of the stream right before an operator is going to be parsed. That way, functions like parse_postfix_operator can become as complex as needed without being required to 'clean up'.

Second, the functions parse_prefix_operator, parse_infix_operator and parse_postfix_operator return an anonymous function that builds the actual AST node from information they get from the main loop in parse_expr_bp. This way they aren't limited in what they can parse. Indeed: the entire ternary operator block, a special case in Kladov's code, becomes just another operator in my code. It just so happens to parse more than only the operator, namely an expression and a colon, as if the ? and : were two parentheses.

The above two adjustments allow us to write any expression as an operator, just like our Mage metagrammar allows.

The next challenge therefore isn't with our operators, but with which expressions are allowed.

Detecting Pratt Expressions

A point I made in the previous section gives us a powerful hint: anything between 'parentheses' (whatever they may be) can be plainly parsed as a top-level expression. See for yourself:

pub index_expr
  = expr '[' expr ']'

The precedence of [ matters, but whatever comes after the [ is just part of the operator and doesn't influence precedence at all.

This means that the only place where precedence matters is at the beginning and end of an expression of a Mage rule. We get in Mage pseudo-code:

pub prefix_expr
  = operator expr

pub postfix_expr
  = expr operator

pub infix_expr
  = expr operator expr

pub atom_expr
  = any_non_expr

Remember, however, that a Mage grammar may contain any valid rule and that the developer might not have declared their Pratt-compatible rules as expr. Therefore we need to find some algorithm to scan the grammar for these rules. Luckily for us, Mage already has some machinery in place that will help us.

Mage can produce a call graph of an entire grammar, making it easy to spot those rules that indirectly call themselves. Those rules will form a cycle, and so we are tempted to perform a topological sort on this call graph.

One component coming out of this topological sort will look like this:

As expected from a single component, every rule is reachable by every other rule.

But hold on, what if we have a grammar like this:

pub one
  = '1' two | 'x'

pub two
  = '2' three | 'x'

pub three
  = '3' four | 'x'

pub four
  = '4' one | 'x'

The only component will look like this:

But this example isn't a Pratt expression! Clearly, a Pratt expression is more than a recursive call. A Pratt expression demands choice. Moreover, as we've seen, prefix and postfix require one recursive call at the respective edges while infix requires exactly two.

We come to the following definition:

A Pratt expression is an expression where at least one of the edges of the expression recursively call themselves, and during that call there is a possible choice to at least one other Pratt expression.

If we didn't have a choice somewhere, there is no need for a Pratt parser.

This detection mechanism will be implemented in an upcoming version of Mage. I will write a follow-up on the actual implementation of the parser, so stay tuned!

Migrating The Bolt Programming Language To Rust

Sam Vervaeck — Mon, 22 Jun 2026 19:07:58 +0000

From today and onward I can quite confidently say that Rust is the final implementation language of the Bolt programming language.

After years of trying out different programming languages (from Haskell and OCaml to TypeScript) and ideas (do I want an ML-style syntax or C-like?), I am very happy with how these experiments are converging. In this search Rust plays a pivotal role.

Curious? Here's why.

Losless syntax trees using Rowan

Real editors not only type-check your code; they also might analyse and transform whitespace, formatting your code according to a certain set of rules.

Above that, designing syntax trees in Rust can be quite a pain due to the way borrowing and ownership works. For one, it is very difficult to get a simple and safe pointer to the parent node in Rust.

As opposed to abstract syntax trees, losless syntax trees keep track of this whitespace for you. The Rowan libary provides a means for defining such syntax trees. It takes care of ownership and even thread-safety for you, so you can focus on things like type-checking.

Rowan is based off the concept of red-green trees, where the green nodes contain the data and the red nodes are simple 'views' on this data. The red nodes are constructed whenever the program needs a node of a certain type, while the green nodes are usually constructed during parsing.

Robust query engine with Salsa

Another Rust crate that makes your life as a compiler writer that much easier is Salsa. It is difficult to work with at first, but once you get the hang of it, it will speed up the development of your compiler tremendously.

Salsa is a tool to build an incremental query-based compiler. With Salsa, there are a few top-level queries one can make about the inputs (such as some programming code written in your language), which get split up in smaller queries. These queries trigger even more queries, all the way down until an answer is formed. The answer then is cached, so that if only a single bit of your inputs change, not everything has to be re-computed from scratch.

The amazing thing is that you as a compiler designer need not to take into account the million ways of which an input might be changed. Salsa takes care of it. Brilliant!

I highly recommend to read this article from Olle Fredriksson and the official Salsa documentation to learn more!

Beautiful error messages with Ariadne

Ariadne is a Rust crate that does all of the dirty work for you when all you want is print a diagnostic message to the terminal. It creates beautiful and very readable error messages, pointing exactly to the location in your source file where the error occurred.

Conclusion

Thanks to the useful Rust libraries out there, writing a compiler has never been so easy. I will continue to work on my programming language called Bolt using this blueprint. I hope that you might consider it, too!

DEV Community: Sam Vervaeck