The Parsers of Hanoi

There is this wonderful category of posts that go like 'we rewrote X in Y and now it is so much better', often portraying the benefit as purely the technological advantage of Y, while in fact a lot of the benefit came from the learnings from X and the chance not to repeat its mistakes.

This is one of those stories, but I'll try not to fall into the trap I laid out in the paragraph above when telling it.

Here at Axiom we maintain our own languages, APL and MPL, both taking up learnings from languages that came before them and trying to improve on them (thanks, Microsoft, for KQL).

So we rewrote something. Our X is pest, the parser generator for MPL, the Metrics Processing Language we open-sourced a while ago. Our Y is… nothing, really: we rewrote the whole parsing stack from scratch by hand. Well, there is a bit of rust-analyzer in the Y.

But let's talk about the why (not the Y, we'll talk about that later). pest is great for getting from 0 to a language quickly and simply; it takes care of a ton of groundwork, the cruft, the boilerplate, etc. And if all you need is a parser that spits out an AST you can work with, go for it! It saved us a lot of time in the beginning, made iteration easy and is honestly a pleasure to work with.

However (there is always a but, but I like however better than but), if you want more out of it, things start to get complicated. We wanted syntax highlighting, error recovery that goes beyond the first error, and eventually a code formatter. The same 'batteries included' approach that makes getting started with pest easy makes this hard to impossible.

Sure, you can write your own lexer for syntax highlighting that is tolerant of errors, but you can't feed pest the lexer's tokens, so you'll be juggling two possibly diverging implementations of the same language.

It gets worse with formatting: you need more than just the lexemes to generate well-formatted output – you need some understanding of the structure, and you need to keep things like comments – the very things you don't want the parser to have to deal with. So that's a third implementation, and at this stage possibly one with some error handling. Ugh, big ugh, now we've got three implementations of the same language, or at least two if we reuse the lexer.

No fun to be had here.

But you know what is fun? Good error handling, syntax highlighting, and code formatting! Let's goooooo!

Lex Me Baby One More Time

Okay, so where do we start? The lexer. That's mostly simple – a state machine that reads characters until a condition is hit, then emits a token. Easy! But no, because we're special snowflakes we chose to allow string interpolation (it's so much nicer than having to build strings with functions -.-), which means that tokens change based on location, so we need a state machine with a stack.

Think about it this way: in "hello! ${ "I am a nasty string" }" the different " have different meanings. The first " starts a string literal, and a second " would normally end it, but because of the interpolation marker (${) the second " is actually the start of a string literal inside the interpolation. The third " ends the string literal inside the interpolation, the } ends the interpolation itself, and the final " terminates the outer string. This can be nested again – I'll spare you the example – and if you already have a headache, you're not alone.

With the lexing done, the next thing is a lossless syntax tree – rust-analyzer has a wonderful crate for this called rowan – it's quite easy to work with and extremely powerful.

Every Byte You Take

The basic idea is that most programming languages have some form of tree-like representation, hence the AST (abstract syntax tree), but if we want formatting, the tree can't be abstract – it needs to be lossless. The main difference is that the AST holds the abstract logical structure of the code, while the LST (lossless syntax tree) is byte-for-byte identical to the input text.

An AST (or a compilation / optimisation step following it for compiled languages) could perform constant folding to turn 23 + 19 into 42, which is great for saving you one addition per invocation, but for formatting or error highlighting that's a bit nasty. The lossless tree keeps all the information: a node spanning the whole addition, one for the +, one for each number, and tokens for the spaces.

We had to build a few helper functions, but once they were in, working with rowan was extremely fun. Both the lexemes -> LST and the LST -> AST conversions were straightforward.

Another One Bites the AST

The last step of the pipeline is the transformation from LST to AST, taking the nodes we found and turning them into more abstract forms that represent execution, not human typing. As mentioned before, rowan makes this really easy once a few helpers are added. It is also the most boring of the three steps; it's fairly standard.

Oops!… I Parsed It Again

An interesting characteristic is that neither the lexing nor the LST step is fallible; they will ALWAYS return a result for the next step. The lexer includes invalid tokens and the LST includes error nodes.

Each step also catches different kinds of errors: an invalid number like 23@bc will be handled in the lexer, but an invalid rule like align to to (please add the mental image of a train here, toooot toooot) will pass the lexer as three idents – it doesn't know anything about how rules look.

The LST will complain about to to, but it would handle | align to 5m using avg | sample 0.5 perfectly fine: both are valid rules as far as the syntax is concerned.

Only at the LST -> AST step, when we start looking at the language's semantics, will we reject this, as sampling is required to come before aggregation.

This layered approach makes it a lot easier to break errors down into their classes, keep the rules tidier and keep the logic simpler.

The AST parser can expect the syntax and lexemes to be correct; it just has to validate the semantics. The LST can expect the lexemes to be correct and validates the syntax, but doesn't need to think about the semantics.

This all leads to quite a pleasant design.

However, error recovery, even though it's possible now, is still a tricky beast. It's easy to come across a case where recovery fails, leading to a trailing error – it's something we're working on improving, and the new design makes that possible!

This is the end, my only friend

So, bottom line, pest is great for getting started and iterating quickly, but when you need more control it starts to hit its limitations. To be clear, this is not a complaint about pest; it did exactly what it was meant to do and did so well – it allowed us to learn what we needed, where the rough edges and 'wants' are. The improvement isn't "it's not pest", it's "we learned what we need so we can build something better suited to our needs".

But enough of my ramblings, let's take a look at how it all works. Feel free to play around with the language; the visualiser below is running the same MPL you'd find at github.com/axiomhq/mpl.