Parsing turns unstructured input—text, symbols, numbers, or tokens—into a structured result. A parser may recognize one character, a comma-separated record, or a JSON document; parser combinators build the larger recognizers by composing small ones. This makes parsing an exercise in API design as well as input processing. section 9.0
Start from an algebra: choose operations, state laws for their behavior, and postpone the internal representation. A string parser recognizes a literal, `run` returns either a parse error or a value, and alternatives choose another parser when the first fails. Simple words such as "abra" and "cadabra" expose these decisions without hiding them behind a full document format. section 9.1
trait Parsers[ParseError, Parser[+_]]: #1 extension [A](p: Parser[A]) def run(input: String): Either[ParseError, A] def char(c: Char): Parser[Char] #2
The minimal interface separates a parser’s public operations from its eventual implementation: construct character parsers, combine them, and run them on strings. section 9.1
Core combinators express common grammar structure:
- `map` changes a successful parsed value without examining more input or changing failure into success; its identity law can be tested as a property. section 9.2
- `many` and `many1` parse zero-or-more and one-or-more repetitions. `product` sequences two parsers on remaining input, while `map2` combines their results. section 9.2.1
- `slice` returns the matched input portion, avoiding construction of values that will immediately be discarded—for example, when counting matched characters. section 9.2.1
- `flatMap` chooses the next parser from an earlier result, enabling context-sensitive formats such as a digit followed by that many `a` characters. section 9.3
From grammar to JSON
A JSON parser can be written against the abstract combinator interface before any runnable `Parser` representation exists. It recognizes arrays, objects, literals, strings, and numbers, producing a JSON syntax tree. Whitespace, separators, token parsers, scopes, and end-of-input checking emerge as reusable helpers while assembling the grammar. section 9.4 section 9.4.1 section 9.8
Errors are part of parsing semantics. `label` replaces an error message, while `scope` retains nested context in a stack of locations and messages. Branching also needs commitment: after a parser has consumed input, failure can prevent irrelevant alternatives from being explored; `attempt` deliberately restores backtracking when another branch should remain available. section 9.5.2 section 9.5.3
One implementation begins as a function from input to `Either[ParseError, A]`, then evolves into a state action from a location to a result containing both a value and consumed-character count. Tracking consumption supports sequencing; later state tracks slicing and commitment, allowing efficiency and controlled alternatives without changing client grammars. section 9.6.1 section 9.6.2
