A parser combinator library builds parsers by composing elementary parsers with other parsers and reusable combinators. A parser consumes unstructured data—such as text or a stream of symbols, numbers, or tokens—and produces a structured representation. Even a parser that recognizes one character can become part of a larger parser. section 9.0
The approach differs from a parser generator library: instead of constructing a parser from a grammar specification, it assembles one directly from primitive operations and combinators. Algebraic design guides the process: define an interface and its laws first, then choose representations that support them. Interactions among operations, sample uses, and implementation difficulties refine the API. section 9.0 section 9.8
Common combinators support progressively richer parsers:
- many parses zero or more repetitions and returns a list; many1 requires one or more repetitions. section 9.8
- The product combinator, also written as **, runs two parsers in sequence and returns their results as a tuple. section 9.8
- map, map2, and flatMap construct composite parsers; flatMap additionally supports context-sensitive parsing. section 9.8
- label and scope attach information that improves errors when parsing fails. section 9.8
From records to trees
A parser can turn a comma-separated file into a list of records and fields, or transform an XML or JSON document into a tree-like structure. The same library can begin with a single-character parser and combine it into these larger structures. section 9.0
