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
double as follows:
double = fn x -> 2 * x end Enum.map([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
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).