Parser combinator

A parser turns unstructured input into a structured result. A parser combinator is an operation for building larger parsers from smaller ones: a parser may recognize one character or string, then combinators assemble it into parsers for repeated sequences, alternatives, and complete documents. This makes parsing an exercise in composing explicit values rather than embedding grammar decisions in one monolithic routine. section 9.0

Useful primitives include string recognition, success without consuming input, result transformation, sequencing, and choice. `product` runs two parsers in order and retains both results; `map` transforms a successful result; `or` chooses another parser after failure. From this small vocabulary come `many`, `many1`, `listOfN`, character parsers, and higher-level combinators such as `map2`. The point is not merely shorter code: each combinator states a grammatical operation that can be reused independently. section 9.3 section 9.8

extension [A](p: Parser[A]) def flatMap[B](f: A => Parser[B]): Parser[B]

`flatMap` makes the next parser depend on a previously parsed value, rather than merely placing two fixed parsers in sequence. section 9.3

Fixed sequencing has a deliberate limit. A parser for a digit followed by that many `a` characters cannot use `product` alone, because the repetition count is learned only after the first parse succeeds. `flatMap` removes that limit by selecting the next parser from the preceding result. A regular-expression parser can recognize the numeric prefix, validation can convert it to an integer, and `listOfN` can consume the requested number of characters. section 9.3 section 9.8

Composition also raises questions that grammar recognition alone does not answer. A parser must describe failures, locations, labels, and whether an alternative should be tried after a branch has consumed input. Treating these as combinator-level choices avoids silently fixing one global error policy. A committed failure can preserve the error from the branch whose prefix has already established the intended interpretation. section 9.5 section 9.5.3

val spaces = string(" ").many
val p1 =
  (string("abra") ** spaces ** string("cadabra")).scope("magic spell")
val p2 =
  (string("abba") ** spaces ** string("babba")).scope("gibberish")
val p = p1 | p2

Two labeled alternatives show why branch control matters: after matching `abra`, a later capitalization error should identify the intended magic-spell branch rather than report an unrelated alternative. section 9.5.3

`attempt` delays commitment, allowing an alternative to run even when its first branch examined input and then failed. Without it, a parser can commit after consuming input and report that failure directly; with it, backtracking remains possible. This choice can improve diagnostics and efficiency, since committed branches need not explore every later alternative. section 9.5.3

A JSON parser demonstrates how the pieces accumulate. Whitespace can be discarded around an array-or-object document; `*>` and `<*` retain only the useful side of a sequence; `eof` rejects trailing input. Arrays use a separator combinator for comma-separated values, while objects combine keys and values. Labels and scopes give failures domain-level names such as array, object, or literal. section 9.8

A practical design sequence is:

• Start with a concrete grammar fragment, such as a literal string or comma-separated list. section 9.0
• Identify repeated grammatical structure and extract a combinator such as sequencing, repetition, or separation. section 9.8
• Introduce `flatMap` when a later parser must depend on an earlier result. section 9.3
• Specify failure, labeling, commitment, and backtracking behavior as part of the parser API. section 9.5 section 9.5.3