Tutorial: Quick & Easy Parser Combinators | cyan.sh

Navigation

Tutorial: Quick & Easy Parser Combinators

Parsing is a fundamental skill for any programmer.<br>Understanding how text is read by the computer, and better yet knowing how to tell the computer to read text in a robust manner, opens the door to solving problems in completely new ways.<br>There have been many times for me that knowing how to make a parser has had utility.<br>A good example is GQLM, a macro pre-processor step for GraphQL, which addressed two annoyances I had with the language (and AWS AppSync).<br>Another example is validating an email generator for AWS SES; since the parser code for the high level email grammar is pretty concise.<br>And of course, making your own programming languages (which I would call a personal hobby) requires understanding parsing to some degree as well.

Recently, I've wanted to rewrite an old project of mine, a simple dice roller, in Gambit.<br>I have a lot of more complex functionality I've been wanting to add and experiment with, particularly the ability to roll against hex-flower tables or use Markov chains to model NPC emotions and other stateful things.<br>I also want to give the tool a proper "language" for rolling dice, which is where parsing comes in.

Unfortunately, Gambit doesn't have any nice (or at least, easy to find) libraries for writing parsers, so I need to make my own.<br>And because this is my tenth time doing this at this point, I thought I would run through the basic structure both for my own future reference and so you-who-reads-this-blog can also quickly write your own parsing toolkit.<br>The approach I'll use is called "parser combinators", which are particularly popular in Haskell (and other functional languages) but are generally good for building parsers quickly.

Parser combinators have the advantage of being extremely quick to work with and build, and produce very readable code.<br>In the example implementation in this tutorial, you will see that our parser code ends up looking remarkably close to the grammar we're trying to parse.<br>This comes with the downside of parser combinators being slow compared to well-made LL or LR parsers (which is why tools like Bison exist); though in practice I still prefer working with them for the readability benefits.<br>Another hitch, which I'll explain when it comes up, is shared with other LL parsers: that being that left-recursive grammars can and will cause infinite loops.<br>This part always trips me up when I need to write a parser again for whatever reason, but I'll explain how to work around it both in the grammar and parser code itself.

This blog will show an implementation in Scheme, however the principles here are the same in any language, however your language must support first-class functions and closures to use this approach.<br>Thankfully, most modern languages do, and so you should be able to use this tutorial to implement your own parsing library in any of JavaScript, Python, Rust, or whatever your favourite language is.

What are Parser Combinators? Actually, what are Combinators?

Simply put, a combinator is just a function that takes some number of other functions and returns a function that combines or modifies their functionality in some way.<br>Some examples:

g = identity(f) where calling g(1) is the same as calling f(1).

g = complement(f) where calling g(1) is the same as calling not f(1).

g = flip(f) where calling g(1, 2) is the same as calling f(2, 1).

g = compose(f, h) where calling g(1) is the same as calling f(h(1)).

And the list goes on.

Parser combinators work the same way.<br>We have a one or a few basic functions that check if the first "unit" of the list we give them matches their parameter, and if it does we return true along with the matched value and remainder of the list.<br>In the implementation shown here, I'm going to work with characters and strings, but this same approach works with lexer tokens, numbers, or whatever else you want to use.

Then, we have some functions that order those unit matchers into larger structures that are more useful to us.<br>Let's go over a really simple pseudocode example:

char(x) produces a function (parser) that returns true if the first character of the given string is "x".

sequence(parser...) produces a parser that returns true if the string matches, in order, all parsers given to it.

So we can make a parser g = sequence(char("a"), char("b"), char("c")).

g("abc") returns true.

g("def") returns false.

g("abcdef") returns true as well as the remainder of the input string, "def".

If this seems simple, that's because it is.<br>Parser combinators are simple to implement, simple to understand, and yet more powerful than tools such as regex.<br>It's a wonder that more languages don't implement them as core functionality.

What Combinators Do We Need?

Before we get started actually writing the code, we first need to understand what it is we need to implement.<br>The formal definition of regex gives us a good starting...