Parser combinators

Parser combinators are a compositional approach for defining parsers in the style of the embedded DSLs, which we covered in the previous chapter. In this section, we will cover basic combinators and the essence of their implementation.

A parser for sums

A parser is a kind of data structure that is assembled from combinators. The (abstract) type of the parser is Parser a; this type denotes a parser that processes a string and produces a result of the a type. For example, to parse sum expressions, we want a parser, exprP, of the Parser Expr type.

Once we have a parser, we can apply it to an input string using the following interpretation function:

parse :: Parser a -> String -> Maybe a

Because the input string may not be in the expected format, the parser can fail; this is modeled with the Maybe a result type.

We expect the following behavior:

*Main> parse exprP "1+2"
Just (Plus (Lit 1) (Lit 2))
*Main> parse exprP "1+...