Pratt parsing is a black box

Introduction

It caught my attention that most of Pratt parsing tutorials that I've stumbled on spend almost all of their time explaining Pratt's algorithm and none explaining the properties behind Pratt that actually matter. Pratt fits into just 9 lines of code if you're programming in a high-level language such as Rhombus:

And here's a secret: that's the least important thing you need to understand about Pratt's. In fact, you don't need to understand this piece at all! Imagine if you were only able to use quicksort if you understood its implementation. Imagine if you were only able to use files if you knew how to implement a filesystem from scratch. It's the same logic here. If you lack the power to abstract, you'll arrive nowhere in computer science because that's how the whole field works. In fact, I wrote the backbone of a heavily Pratt-based parsing machinery for a compiler that I've been writing since last year w/o even bothering to understand the above snippet in any detail.

Not convinced? Think for a second on how they do in traditional parsing techniques: compiler compilers! They use code generators to spit the parsing algorithm because just a minuscule crowd bothers to learn what the parsing engine is actually doing. It's no different with Pratt. However Pratt is so small that you can just copy'n'paste these 9 lines of code in your project and call it a day instead of adding a new complex dependency to your project. The algorithm hasn't changed since 1973 and it's not gonna change now.

In this article I'll go over what you actually need to keep in mind for Pratt parsing. The point won't be about memorizing any of it though. The point is about acquiring a mindset. As long as you acquire the mindset you don't need to even bother to remember even a single word of what I say here.

Nuds & leds

The only tutorial on Pratt parsing that I can firmly recommend to someone who has never been exposed to the topic is actually a talk that Douglas Crockford gave in the conference GOTO 2013¹. Douglas Crockford nailed it when he stated:

Pratt takes parsing which is a really complicated thing and reduces it to one simple question: What do we expect to see to the left of a token?

— Douglas Crockford, GOTO 2013

At first glance it may look like a mystical statement devoid of meaning, but that's the question that becomes the framework on how you face parsing problems and it'll rewire your brain to internalize the Pratt parsing mindset. That's the most important thing you need to understand. You register semantic actions for two categories: nuds and leds. A nud is a token that expects nothing to its left (nud stands for null denotation) while a led expects something (led stands for left denotation).

Traditional parsing techniques register semantic actions to production rules. Here's an example I took straight from GNU Bison's manual:

The text between the braces is code that executes when the BNF-like grammar on the left matches. I'm gonna repeat myself because that's really important: traditional parsing techniques register semantic actions to production rules (which by definition are non-terminal symbols). In contrast Pratt parsing registers semantic actions to the terminals themselves instead. That's a fundamental shift on how you face parsing problems.

Here's a stripped down version of the code for the tables that I have in my compiler right now:

All values on the left of each table are the lexer codes for terminal symbols. The values on the right depend on the table kind:

• Nud tables

• Functions matching the signature

  ExprPtr(Context&,reader,reader&)

  ExprPtr(Context&,reader,reader&)

  .
• Led tables

• Functions matching the signature

  ExprPtr(Context&,reader,reader&,ExprPtr)

  ExprPtr(Context&,reader,reader&,ExprPtr)

  .
• Binding power tables

• Positive integers.

Most of the semantic actions in these tables have code whose implementation amount to one semicolon in their body at most. Here's the code for

parse_unary_plus()

parse_unary_plus()

:

On the surface it may seem just like a different but still very similar way to organize your code, but the impact is in fact huge. Here are a few differences from traditional parsing techniques that stem from this single departure alone:

• You don't need to worry about left-recursion problems that occur in traditional parsing techniques such as LL(k). Given the dispatch to a semantic action is done with its associated token already consumed from the stream, left-recursion just doesn't happen. It's a non-issue.

• The parsing engine doesn't need to test alternatives or backtrack. The usual dichotomy between speed versus memory that is found in some parsers (e.g. PEG vs packrat) is gone. Pratt is fast, and it's not gonna starve for insane amounts of memoization. Pratt is just going to compare numbers, and iterate or recurse.

• Related to the previous point, but worth to consider on its own: semantic actions run exactly once! That means there's no need to rollback to a previous state if a match fails. In other words your actions may contain side-effects. In my parser I use this property to do name reservation/release on lexical scope through a shared context object juggled through each layer. Just be careful to not abuse side-effects and end up with spaghetti.

• Also related: your semantic action always knows it's the correct match. Therefore it may look arbitrarily far ahead if it wants to. In other words: you can further use PEG parsers (or layered Pratt parsers) in the semantic actions. While Pratt itself only eats 1 token at a time, the nuds & leds themselves may eat more tokens per round. You just unlocked the power of parser combinators.

• Most of the grammar ambiguities become table collisions so you waste less time on the simpler ambiguity cases. If you combine multiple parsers then it's still possible to have grammar ambiguities. So you still have work as a grammar designer, but in my experience it's much less work. When you combine parsers you're really combining grammars. Pratt as the parsing algorithm won't act as the all-seeing oracle and detect every possible ambiguity in the full grammar amalgamation. Pratt (just like PEG) will just return the first possible match in this case.

• Unfilled gaps in your tables become trivial extension points in your grammar. You may fill these gaps in response to the text parsed so far. In other words you can implement macros and even parse a language that extends its own operators. In contrast extending a pre-existing grammar based on production rules (the orthodox parsing school) is a job worth the complexity of PhD researches.

You may even find a few of these properties in the traditional school as well, but only to certain extents, or with a huge complexity toll.

Nonetheless I mentioned earlier that this organization is a mindset shift, but so far I've only mentioned properties that you can use from adopting Pratt, so where's the shift really? Consider the usual EBNF rule for parsing function calls:

How do you approach this problem when instead of production rules your toolbox contains only nuds & leds? The key observation is that the opening parentheses always expect something to its left, so it's a led. There you go: register a led for lparen and parse the function call from there. It's not immediately obvious, specially when you've only been exposed to the traditional parsing school. Hence why Douglas Crockford nailed it when he stated:

Pratt takes parsing which is a really complicated thing and reduces it to one simple question: What do we expect to see to the left of a token?

— Douglas Crockford, GOTO 2013

The led for array indexing is very similar to the led for function call. Here's the variation that I use in my own parser:

Pratt is not just precedence climbing. Pratt is a way to organize your code. First learning Pratt as a black box actually helps to understand this difference. If you don't have access to the black box, you won't be tempted to reduce Pratt to precedence climbing. Hopefully by the time you want to take away the abstraction and see what's inside you won't make the mistake of treating Pratt just like a mere variation of precedence climbing because by then you'll have already been exposed to all the power unlocked by Pratt parsing. Andy Chu's blog post on Pratt parsing without prototypal inheritance is worth reading as it contrasts two opposing styles of writing Pratt parsers². Here's a minimal calculator written in Rhombus that is (stylistically) closer to a version that'd use prototypal inheritance than the style that Andy Chu shows:

Algorithmic & grammar constraints

The previous section might have been the densest in this whole blog post so I want to tune it down while you incubate the Pratt mindset and go on trivial things for now:

• Pratt requires a separate lexer. Some modern parsing engines can work in a scannerless manner (e.g. PEG) or even embed the lexer definition directly in the parser itself, but Pratt requires a separate lexer. That shouldn't be a big concern, but it's something to keep in mind.

• Pratt is fast. The algorithm only compares numbers and iterate or recurse. It's only looking 1 token ahead, and not doing anything else really. It doesn't go back to test alternatives or to backtrack on failed production rules. It just doesn't go back at all. It's a full-speed locomotive only looking ahead eating 1 token at a time.

• Given Pratt itself is already fast, if you want to optimize anything, the only thing left is the dispatch code for nuds & leds. In my case I use global read-only dispatch tables, but most of the tutorials I've seen in the wild use dynamic objects in highly dynamic scripting languages.

• Pratt can't parse statements. You have to combine it with other techniques to parse languages with statements. I've already gone through this constraint in my last blog post where you can find solutions.

• Pratt is a form of recursive descent parsing meaning it's running custom user code (i.e. code in a Turing-complete language) for the semantic actions, but that's not the whole picture. The semantic actions further drive the parsing choices/direction which means that your code might look at the context (e.g. previous declarations) to decide how to parse the next piece of the input text. In summary you can have some forms of context-sensitive parsing which opens the door for more classes of languages.

• You'll have to resort to modal lexing to parse some complex languages found in the wild, but I'll reserve a later section of this blog post to touch on this topic.

• Pratt can't be used for incremental parsing as done in GLR parsing. However that's not a power found in most parsing algorithms anyway (I'm running out of algorithmic properties to talk about). Incremental parsing is used in tools such as tree-sitter.

Right-to-left associative operators

My whole argument today is that Pratt is a black box abstraction, so let's go with this argument and lay down what contracts you need to respect to use Pratt:

• Only tokens with associated leds need a value in the binding power table. Tutorials in the wild are usually written in a way where this property isn't obvious. It becomes more obvious when you write your parser using static tables rather than highly dynamic objects in scripting languages.

• Related to the previous point: You still need a value for the binding power of prefix operators, but this value isn't used in the Pratt loop at all. Therefore it's not a requirement to inflate the binding power table with a value for the prefix operators, but that's what most of the code I've seen in the wild do anyway. If you think it's easier to just stuff the binding power for prefix operators in the same table be my guest and go ahead. Just bear in mind that this popular arrangement isn't a hard requirement. Only the nud implementing the prefix operator itself needs to know the binding power for prefix operators.

• Never assign a binding power of zero to a led.

• Separators such as comma and unknown/error/EOF tokens where the parser must stop should have a binding power of zero. They don't need to exist in the binding power table.

• If you're writing in decimal like every human being, adopt increments of 10 in the binding power table. When reading these values, you may just ignore the final zero, but the extra room between operators enables some tricks.

So how do we implement right-to-left associative operators with Pratt? First let's look at a common left-to-right associative infix operator. Here's my code for the led

+

+

:

If we wanted to make the operator right-to-left associative, we'd just need to use

bp - 1

bp - 1

instead of

bp

bp

:

That's a standard trick in the field of Pratt parsing. A trick of the trade so to speak. A trick you ought to know. Why does it work? It doesn't matter. It's a black box for today. Tomorrow it might matter, but today you should only be focusing on how to use Pratt, not why it works.

Macros freely interleave between lexing & parsing

Why even write a section for macros when most language designers won't add them? Pratt macros are just nuds/leds implemented in the language that your code is parsing and interpreting. Therefore anything that your own nuds/leds can do is something that ought to be possible in a macro and vice-versa. Lessons learned from Pratt macros are lessons learned on Pratt parsing itself.

That's just a principle, and not a hard-truth. It's definitely not a truth in the Pratt macros of my own language, for instance, but the principle remains my guide (and hopefully yours as well).

The implementation of macros outside Lisp are traditionally very limited in many fronts. In languages such as C you have macros that are just textual substitution templates that work in the environment of a preprocessor doing textual expansion (therefore working on the lexing layer). It's also possible to design macros that work in the AST/parsing layer such as done in Lisp. However Pratt macros unify these two previously severed worlds. If you're implementing procedural Pratt macros then it's possible for the macro to use APIs that alternately invoke either the lexer or the parser. My own macro system doesn't yet have enough APIs so I can't showcase a real example, but here's how envision that it's gonna work:

These APIs are pretty much what's already used in the core nuds of many parsers using Pratt. A macro system only needs to expose them to the macros as well to get this far. This part is actually easy. Tasks actually challenging in macro systems reside elsewhere, not here. The hardest part of a macro system is hygiene³⁴, not parsing (well… parsing is gonna be easy if you use Pratt parsing at least). However this blog post is about (Pratt) parsing, not macro systems, so I'm not gonna delve on hygiene or other macro system challenges (problems which I've already battled with and ultimately won).

The takeaway here is that Pratt parsing enables languages with powerful macros that can implement beautiful unconst