The first thing I thought was that this looks a lot like parsing expression grammars (PEG). But a little Internet searching tells me they’re apparently unrelated, though I’d be hard pressed to explain the difference. In practice, the PEG code I’ve written looked very similar.
As I understand it, a parser combinator is simply notation for a PEG defined by and written in actual code, where the code itself generates a recursive descent parser.
I think that’s a pretty good first-order approximation.
One difference is that PEGs only have “exactly one valid parse tree” (to borrow a phrase from Wikipedia) whereas parser combinators understand ambiguity: if we are trying to recognize the strings ab and ac and we come across the token a, we might traditionally rewrite our rules – left factoring. Whereas in the world of parser combinators you could use the alternation combinator to visit both. (Usually implemented with backtracking.)
By design, parser combinators also are monads and thus applicative functors, which enables a lot of the machinery in Haskell’s parsec and attoparsec. FParsec, which I wrote a little thing about, tries to aim for something similar in F#. But, as a non-academic, I believe that this is just a Nice Coincidence — the real power of parser combinators lies in its choice of a function as the abstraction, and not a production rule and definitely not a preprocessed language. Functions are composable and refactorable. It turns out that most parsers do the same things and so you can provide a large library of combinators; most parsers then turn out to be only a handful of lines of code while still giving a hand-written C parser a run for its money.
The first thing I thought was that this looks a lot like parsing expression grammars (PEG). But a little Internet searching tells me they’re apparently unrelated, though I’d be hard pressed to explain the difference. In practice, the PEG code I’ve written looked very similar.
As I understand it, a parser combinator is simply notation for a PEG defined by and written in actual code, where the code itself generates a recursive descent parser.
I think that’s a pretty good first-order approximation.
One difference is that PEGs only have “exactly one valid parse tree” (to borrow a phrase from Wikipedia) whereas parser combinators understand ambiguity: if we are trying to recognize the strings
abandacand we come across the tokena, we might traditionally rewrite our rules – left factoring. Whereas in the world of parser combinators you could use the alternation combinator to visit both. (Usually implemented with backtracking.)By design, parser combinators also are monads and thus applicative functors, which enables a lot of the machinery in Haskell’s
parsecandattoparsec. FParsec, which I wrote a little thing about, tries to aim for something similar in F#. But, as a non-academic, I believe that this is just a Nice Coincidence — the real power of parser combinators lies in its choice of a function as the abstraction, and not a production rule and definitely not a preprocessed language. Functions are composable and refactorable. It turns out that most parsers do the same things and so you can provide a large library of combinators; most parsers then turn out to be only a handful of lines of code while still giving a hand-written C parser a run for its money.I recently wrote a little intro to parser combinators in Haskell. It may be of interest to readers here, too: https://gist.github.com/tel/df3fa3df530f593646a0
In particular I exploit the structure of a parser combinator type as a monad transformer.