Quick & Easy Parser Combinators

Parsing is a fundamental skill for any programmer. 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. There have been many times for me that knowing how to make a parser has had utility. A good example is GQLM, a macro pre-processor step for GraphQL, which addressed two annoyances I had with the language (and AWS AppSync). Another example is validating an email generator for AWS SES; since the parser code for the high level email grammar is pretty concise. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. Parser combinators are simple to implement, simple to understand, and yet more powerful than tools such as regex. 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. The formal definition of regex gives us a good starting point. You likely already know regex, but the extended regex that you're used to from your language of choice is a bit more than we need here. The formal definition is far simpler, with 3 constants:

• The empty set, ∅.
• The set containing only the empty string, ε.
• The set containing a single character.

And 3 operations:

• Concatenation, such as ab to first match a and then b.
• Alternation, such as a|b to match either a or b.
• Kleene star, to such as a to match zero or more a's sequentially.

Aside from the empty set, which we don't really need, this is also all the specification we need for parsing. In other words, the base library only has 5 functions:

• A parser that matches an empty input (such as "" or an empty list, or #EOF).
• A parser that matches a single unit of whatever it is we're parsing. This can either be a single character, or it can be a lexer token, or a struct, or object, or whatever else.
• A parser that parses a sequence (from left to right) of parsers (this is our sequence function from before).
• A parser that parses either of the parsers given to it, either.
• A parser that parses a given parser zero or more times, many.

We will then extend our library to create a bunch of shortcuts. For example, one-or-more could be implemented as a sequence of a single parser, followed by many of the same parser.

Constant Parsers

Our first parser, the empty input, is easy (I mean none of this is that complex), but it sets the structure for how we'll implement all of our parsers.

Each parser is a function which returns a function that takes a single input parameter. For our eof parser, the returned function checks if input is an empty string. If it is, we return two values: the first being the matched text (in this case an empty list, the Scheme equivalent of null), and the second being the remaining text in the string (which is an empty string, because we have nothing left over). If the input is not an empty string, we return False.

(define (eof)
  (lambda (input)
    (if (= 0 (string-length input))
        (cons '() "")
        #f)))

Note for those not familiar with Scheme, cons is just creating a pair of two values here. The function car will access the first value, and cdr will access the second value.

Simple enough, right?

Next up is the unit parser. We're doing string parsing here, so our unit is a single character. We will do this by passing the character value into the function so we can reference it in the returned closure. If the string is not empty, and the first character is the character we specified, we return the matched character and then the remaining string.

(define (char chr)
  (lambda (input)
    (if (and (< 0 (string-length input))
           (equal? (string-ref input 0) chr))
        (cons chr (substring input 1 (string-length input)))
        #f)))

And that's it for the constants. You can of course substitute char for a different parser, such as struct or token or any other unit.

Basic Combinators

Let's have a look at sequence first, which I'm going to shorten just to seq. The seq function takes a list of parsers as input. It then iterates through each parser, adding the result on to the previous result. If it ever fails to parse, then return false immediately.

Procedural programmers avert your eyes, I'm using recursion and not loops.

(define (seq . parsers)
  (define (match-next p result rest)
    (if (= p (length parsers))
      (cons result rest)
      (let* ((parser (list-ref parsers p))
             (parse-result (parser rest)))
        (if parse-result
            (match-next (+ 1 p)
                        (append result (list (car parse-result)))
                        (cdr parse-result))
            #f))))
  (lambda (input)
    (match-next 0 '() input)))

We can test this function to prove that it works, including already functioning with nested sequence parsers.

((seq (char #\f) (char #\o) (char #\o)) "foo") ((seq (char #\f) (char #\o) (char #\o)) "foodie") ((seq (char #\f) (seq (char #\o) (char #\o))) "foodie") 

either is similarly simple. It takes a list of parsers as input, and iterates through them until one of them parses, then returns the successful result. If none of the parsers match, it returns false.

(define (either . parsers)
  (define (test-parser p input)
    (if (null? p)
      #f
      (let* ((parser (car p))
             (parse-result (parser input)))
        (if parse-result
            parse-result
            (test-parser (cdr p) input)))))
  (lambda (input)
    (test-parser parsers input)))

And some simple tests (for brevity, I won't prove that it handles nesting and remainder - just take my word for it):

((either (char #\a) (char #\b)) "a") ((either (char #\a) (char #\b)) "b") 

And the last of our core functions, many. many takes a single parser and matches it against the input string until it fails. many never returns False, because technically zero matches is allowed.

(define (many parser)
  (define (match-next result rest)
    (let ((parse-result (parser rest)))
      (if parse-result
        (match-next (append result (list (car parse-result)))
                    (cdr parse-result))
        (cons result rest))))
  (lambda (input)
    (match-next '() input)))

And tests (again, made more concise for brevity):

((many (char #\a)) "a") ((many (char #\a)) "") ((many (char #\a)) "aaabbb") 

And that's finished off our core functions. Even with just this, we can already implement any parser we want, but it'll be annoying and we can make the core library a bit more useful.

Improving the Core: Parsing Arithmetic

To do that, let's define a specific parsing problem: parsing basic arithmetic expressions. We want to handle the following:

1. All the basic arithmetic operations, so addition, subtraction, multiplication and division; with the correct order of operations.
2. Whole numbers, decimal numbers, and negative numbers.
3. Brackets to change the order of operations.

We'll also ignore whitespace and strip it from the input to the parser. This is the grammar we'll write:

<expression> ::= <sum>
<sum> ::= <product> (("+" | "-") <product>)*
<product> ::= <value> (("*" | "/") <value>)*
<value> ::= <number> | <closed expression> | <negation>
<negation> ::= "-" <value>
<closed expression> ::= "(" <expression> ")"
<number> ::= <digit> <digit>* "." <digit>* | <digit> <digit>*
<digit> ::= "0" | "1" | "2" | ... | "8" | "9"

If you're not sure how to read BNF, Wikipedia has a great explanation.

One thing to note is the way we've defined our <sum> and <product> grammars is not left-recursive. This is because, like any LL parser, parser combinators will loop infinitely on a left-recursive grammar, such as the one below:

<sum> ::= <sum> ("+" | "-") <sum> | <value> 

We can expand this grammar out in our heads, but the computer will struggle with it, because it will infinitely try to parse that first <sum>.

Let's define digit first. We can do this by cheating a bit with Scheme's apply function. Basically, we just use map to build a list of char parsers from a list of characters (each digit), then pass that to either.

(define digit
  (apply either
       (map
        (lambda (x) (char x))
        (string->list "0123456789"))))

(digit "1") will return (#\1 . "").

With digit, we can define number as essentially identical to our grammar above:

(define number
  (either
   (seq digit
      (many digit)
      (char #\.)
      (many digit))
   (seq digit
      (many digit))))

There are a few improvements to be made here though. Specifically, with some BNF extensions we could shorten this grammar by making the decimal optional, and making digit "one or many" and not just many.

number ::= <digit>+ ("." <digit>*)?

We can, of course, add these two as combinators just as well.

One or many is the easiest, it's really just a sequence of one parser followed by many of the same parser:

(define (one-plus parser)
  (seq parser (many parser)))

One thing to note is that this won't return one flat list because of how the seq combinator works. Instead, we will see something like this:

((one-plus (char #\a)) "aaa") 

We can fix this behaviour with post-processing, which we'll go over soon.

Before that, let's implement our optional parser opt. opt checks a particular parser against its input. If it succeeds, then easy we just return the output of the parser. Otherwise, we want to return null and the input string; we don't return False here, because the parser did succeed.

(define (opt parser)
  (lambda (input)
    (let ((res (parser input)))
      (if res
        res
        (cons '() input)))))

With these two additional combinators, we can now implement the shorter version of the grammar!

(define number
  (seq (one-plus digit)
       (opt (seq (char #\.)
               (many digit)))))

In my opinion this is perhaps less readable, but it is nicer to make this a bit more concise.

There's just one problem: our output when parsing a number is kind of horrible:

Wouldn't it be great if this just returned us an actual number? Well, that's where post-processing comes in.

Post-Processing

Sometimes, as the output of one of our parsers, we want to do more than return just the raw list of units. This is most obvious in our number example, I would love to have that output either the string "123.4" or just the number itself 123.4. This can be done with post-processing, which is another combinator that simply runs a parser, and if it succeeds in parsing it runs a given function against the returned parse tree. Let's call this function post-process.

(define (post-process processor parser)
  (lambda (input)
    (let ((res (parser input)))
      (if res
        (cons (processor (car res))
              (cdr res))
        #f))))

Now we can adjust our number parser like so:

(define number
  (post-process
   (lambda (result)
     (string->number
      (list->string
       (flatten result))))
   (seq (one-plus digit)
      (opt (seq (char #\.)
                (many digit))))))

And now our parser outputs numbers properly:

Implementing the Rest

We now have enough to implement every single grammar rule, so here's the rest of them.

(define digit
  (apply either
       (map
        (lambda (x) (char x))
        (string->list "0123456789"))))

(define number
  (post-process
   (lambda (result)
     (string->number
      (list->string
       (flatten result))))
   (seq (one-plus digit)
      (opt (seq (char #\.)
                (many digit))))))

(define (closed-expr input)
  ((post-process
    (lambda (res)
      (list (cadr res)))
    (seq
     (char #\()
     expression
     (char #\)))) input))

(define (negation input)
  ((post-process
    (lambda (res)
      (- (cadr res)))
    (seq (char #\-)
       value)) input))

(define value
  (either number closed-expr negation))

(define product
  (seq
   value
   (many (seq (either (char #\*)
                    (char #\/))
            value))))

(define sum
  (seq
   product
   (many (seq (either (char #\+)
                    (char #\-))
            product))))

(define expression sum)

You can see that we can more or less follow the exact BNF grammar for our rules. One thing to note is that we've made closed-expr and negation functions rather than variables here. This is so when they are called, they will see the declaration of expression and value, which depend on these two. This is called lazy loading.

This grammar does parse:

(expression "2*(3+-4)*5") 

However, this can still be improved.

Cleaning Up

The first thing that comes to mind is all those empty lists hovering about. Those are the result of our use of many in the sum and product parsers, as the many can of course match nothing, in which case we get an empty list.

To fix this, we can simply add the following as a post-processor for sum and product:

(define (strip-null-cdr res)
  (if (equal? '() (last res))
      (car res)
      res))

Now we get a much more sane result.

(expression "2*(3+-4)*5") 

If you're working in a non-Scheme language, this is likely where you can get off. You may want to add a post-processor that converts this into a parser node, instead of just using a list, but essentially the next step after this is making an interpreter, which I won't be covering here.

Interpreting the Result

However, if you're using Scheme or Lisp, there is one last trick that we can do here as a shortcut to build a full interpreter: we can reorder this tree into a valid Lisp form, then pass it to eval.

This is actually fairly easy to do, all you need is one more post-processor for our two left-associative operations sum and product to reorganise the whole tree and convert the operation characters into symbols.

Our output at the moment is not really a true parse tree in the working sense. It lacks associativity, and is essentially just a list of values. What we want to do is re-orgnise it into a left-assocative tree, and we can do this with a fairly simple algorithm:

1. Start with the left-most node of the list.
2. Iterate over each node in the remaining list.
3. In each iteration, make a list with 3 elements; the operator of the current iteration's operation, the value from the previous iteration (the left-most node to start), and the remainder of the operation.
4. Save the value of that iteration and use it in the next iteration.
5. Keep going until you hit the end of the list.

In Scheme, this gives us the following code:

(define (left-associative res)
  (define (iter acc next)
    (if (null? next)
      acc
      (let ((op (car next)))
        (iter (list (string->symbol (list->string (list (car op))))
                    acc
                    (cadr op))
              (cdr next)))))
  (if (and (pair? res) (not (symbol? (car res))))
      (iter (car res) (cadr res))
      res))

You will notice we only adjust the list here if the first item in the list is not a symbol. If we don't do this, the post-processor in sum will try to reorganise the already left-associative output of product. If our expression only has product operations, then this will cause an error, so that catch prevents doubling up. It's a bit messy, but then again the better option here is to parse this into an actual tree. This is just a hack possible in Lisp.

Which we can then add as a post-processor to sum and product, and run the parser to observe the output:

(expression "1+2+3") (expression "1*2*3") (expression "1+2*3") (expression "2*3+4") (expression "2+(3+-4)*5") 

Wow! That looks a lot like Scheme, and we're maintaining the order of operations too! In fact, we can pass the first element of any output here directly to eval and it will work just fine:

(eval (car (expression "1+2+3"))) (eval (car (expression "1*2*3"))) (eval (car (expression "1+2*3"))) (eval (car (expression "2*3+4"))) (eval (car (expression "2+(3+-4)*5"))) 

Oh wait, have we screwed something up here?

Take a look at the parser output again: (3+-4) is put into double brackets ((+ 3 -4)), which means that the result of that addition is being called as a function, (-1). That ain't right.

Fortunately, it's easy to see where the problem is: in the closed-expr. This parser is currently returning whatever it parses inside a list. This is a trivial fix, we'll just remove the list from the closed-expr post-processor, and just return the cadr of it's result.

And finally:

(eval (car (expression "1+2+3"))) (eval (car (expression "1*2*3"))) (eval (car (expression "1+2*3"))) (eval (car (expression "2*3+4"))) (eval (car (expression "2+(3+-4)*5"))) 

Everything is as it should be!

Closing Up

Hopefully this has helped you learn a little bit more about parsing and the problems that good parsing can solve.

As I said at the start, the main reason I wrote this post is to accompany my own parser library implementation in Gambit. You can find that implementation here: I've called it Parque. The library is built using only base R7RS, so it should work in any Scheme that supports R7RS' define-library.

While the implementation described in this blog post is already useful, it's more of a quick method for implementing combinators. I want Parque to be better than this, so I will extend it with some other combinators and a proper parser output record instead of just pairs. This blog post will remain as a reference for quickly implementing these functions.