Parser Combinator

A parser combinator is a higher-order function that takes parsers as arguments and returns a new parser. Originating in functional programming languages, parser combinators make recursive descent parsing composable: simple parsers for tokens and atomic constructs are combined using combinators for sequencing, alternation, repetition, and mapping to build parsers for complex grammars. The approach unifies the grammar and the parser implementation into a single executable specification.

Unlike parser generators such as Yacc or Bison, which require a separate grammar file and generate imperative code, parser combinator libraries embed the grammar directly in the host language. This embedding enables parsers to use the full power of the host language — variables, functions, data structures, and even effects — at the cost of losing static grammar analysis. A parser combinator library cannot warn you about left recursion or ambiguity because it sees the grammar only at runtime.

The most influential parser combinator library is Parsec, developed by Daan Leijen and Erik Meijer in Haskell. Its descendants (Megaparsec, Attoparsec) and ports to other languages (Rust's nom, Scala's fastparse) have made parser combinators the dominant approach for writing small to medium parsers in modern functional and systems programming. The technique represents a wager: that the expressiveness of embedding outweighs the safety of separation.