Intro to Parser Combinators

If you prefer to watch to a talk see Saša Jurić build up parser combinators from the ground up

The phrase parser combinator may sound confusing but is in fact deceptively simple if you already understand the notion of functions and function composition.

For example transforming [1, 2, 3, 4, 5] into [2, 4, 6, 8, 10] can be achieved through combining the functions and double as follows:

double = fn x -> 2 * x end[1, 2, 3, 4, 5], double)

If you think of a parser as being a certain kind of function that works on a textual input (in the way that double above is a kind of function that works on a number input) then you may see how we can combine parsers to do work.

For example to parse an input such as "12345" we might combine two parsers many and digit. Let's imagine digit is a parser that accepts an input character in the range of '0'..'9' and returns a number, like this:

digit("12345") = 1
digit("2345") = 2

and so on. Now lets imagine that many is a parser that accepts an input and another parser and keeps attempting to match that parser against the input until it doesn't match any further. So, for example:

many("12345", digit) = [1, 2, 3, 4, 5]

It's the "accepts another parser" concept that is key and is what makes many a combinator parser. In the same way as map calls the function double to do work, many calls the parser digit to do work.

The insight is that we can replace digit with any other parser including other combinator parsers. In this way we can combine, and recombine, simpler parsers to form more complex parsers until we have something that can parse our input.

In Ergo we distinguish between terminal parsers that only work on the input and combinator parsers that are parameterised with one or more other parsers (which may themselves be either a terminal or another combinator parser).