Lesson 4.5 — Parser combinators: backtracking, committed choice, error reporting and recovery¶

Techniques: list-of-successes and backtracking combinators (Wadler 1985; Hutton & Meijer 1996/1998; nom), committed choice with explicit try (Leijen & Meijer's Parsec 2001), furthest-failure error reporting and error recovery in combinator libraries (Ford 2002; chumsky) · Pebble implements: no combinator library; the lesson's grammar is the lab's sum subset, and the traces are checked against real runs of nom, Parsec and chumsky · Prerequisites: Lesson 2.5, Lesson 4.2 · Time: 2.5 hours

A parser combinator library turns recursive descent into a library: a parser is a value (a function from input to result), and higher-order functions build big parsers out of small ones — a.then(b), a.or(b), many(a). The grammar is written in the host language, with its types, abstractions and tests; there is no generator step. The hard questions are the ones this chapter has been asking all along, now hidden inside or: does choice backtrack, commit, or return every alternative? What does that cost? And where does the error message point?

1. Problem and motivation¶

The problem. Build parsers compositionally, as ordinary values of a host language, while controlling three properties that the composition operators decide: the language a choice accepts (all alternatives, the first success, or the first alternative that consumes input), the cost (exponential backtracking vs linear commitment), and the quality of errors (position and expected tokens, and whether parsing continues after an error).

Backtracking combinators¶

Wadler's "list of successes" [Wad85] represents a parser as a function returning every way to parse a prefix of the input, as a list of (result, remaining input) pairs; failure is the empty list and choice is list concatenation. Hutton and Meijer [HM96, HM98] packaged this as a monad (return, >>=), which made combinator parsing the standard example of monads in Haskell. Libraries used in practice mostly return one result and backtrack on failure: Rust's nom [NOM] tries the next alternative of alt whenever the previous one returns a recoverable Err::Error, wherever it failed — ordered choice as in PEGs (Lesson 4.2), without memoization.

Committed choice¶

Backtracking makes the error position meaningless (the parser has always backed out of the place where the real mistake is) and costs time. Leijen and Meijer's Parsec [LM01] made choice committed: p <|> q tries q only if p failed without consuming input. This is LL(1)-style prediction with a one-token decision, which gives linear time and errors at the first token that cannot continue. Backtracking is still available, but only where the grammar author writes try p. Megaparsec, attoparsec and many other libraries follow this design.

Error reporting and recovery in combinators¶

When all alternatives fail, which failure is reported? Ford's packrat parsers [For02] report the furthest failure: the rightmost position where any terminal test failed, together with the union of what was expected there. Parsec merges errors of empty alternatives the same way. Modern libraries add recovery: chumsky [CHUMSKY] lets a parser be wrapped with a recovery strategy (skip tokens until a delimiter, balance brackets, retry) that records an error, produces a placeholder value and continues, so one run reports many errors and still returns a partial AST — the combinator version of Lesson 4.6's resilient parsing.

2. Definitions and algorithms¶

Throughout, the input is a string \(x\) and a parser returns results about a prefix of the remaining input.

Backtracking combinators¶

Definition 4.5.1 (Parsers as functions: list of successes)

A list-of-successes parser with result type \(\tau\) is a function \(p : T^{*} \to \mathrm{List}(\tau \times T^{*})\): \(p(x)\) lists every way to parse a prefix \(u\) of \(x = u\,v\), as pairs \((\text{result}, v)\). The basic combinators are: \(\mathsf{return}\,a = \lambda x.\, [(a, x)]\); \(\mathsf{item} = \lambda x.\, [(c, x')]\) if \(x = c\,x'\), else \([]\); \(p \mathbin{>\!\!>\!\!=} f = \lambda x.\, \mathrm{concat}[\, f(a)(x') \mid (a, x') \in p(x) \,]\) (sequencing with the result of \(p\) available to the rest); \(p \mathbin{+\!\!+} q = \lambda x.\, p(x) \mathbin{+\!\!+} q(x)\) (choice: all alternatives); \(\mathsf{many}\,p = (p \mathbin{>\!\!>\!\!=} \lambda a.\, \mathsf{many}\,p \mathbin{>\!\!>\!\!=} \lambda as.\, \mathsf{return}(a{:}as)) \mathbin{+\!\!+} \mathsf{return}\,[]\).

All parses of a prefix

With \(\mathsf{digit}\) a one-digit parser and \(\mathsf{number} = \mathsf{many1}\,\mathsf{digit}\), \(\mathsf{number}(\texttt{"12+"})\) is \([(12, \texttt{"+"}), (1, \texttt{"2+"})]\): the longest match first, then the shorter one. A complete parse is a result whose remaining input is empty.

Definition 4.5.2 (Single-result backtracking parsers: nom's result type)

A backtracking parser returns \(\mathsf{Ok}(v, a)\) (remaining input \(v\), result \(a\)), \(\mathsf{Error}(e)\) (recoverable: the caller may try something else) or \(\mathsf{Failure}(e)\) (unrecoverable). Sequencing propagates the first non-\(\mathsf{Ok}\). \(\mathsf{alt}(p, q)(x) = q(x)\) if \(p(x) = \mathsf{Error}\), else \(p(x)\): ordered choice with full backtracking to the start of \(x\). \(\mathsf{many0}\,p\) applies \(p\) until it returns \(\mathsf{Error}\), then succeeds with the results so far and the input before the failed attempt. \(\mathsf{cut}\,p\) turns \(p\)'s \(\mathsf{Error}\) into \(\mathsf{Failure}\), which stops alt and many0 from backtracking.

Algorithm 4.5.3 (Backtracking combinators)

Input: parsers built from tag/satisfy with the combinators below; an input string.
Output: \(\mathsf{Ok}(v, a)\), \(\mathsf{Error}(e)\) or \(\mathsf{Failure}(e)\) for the prefix parsed.
Precondition: no left recursion in the combinator graph (a parser may not call itself before consuming input), else the recursion does not terminate.
Postcondition: equals the PEG semantics of Definition 4.2.2 when alt is /, many0 is * and \(\mathsf{Error}\) is fail (Proposition 4.5.9).
Invariant: every returned remaining input is a suffix of the input given to that parser.

function Seq(p, q)(x):     r ← p(x);  if r is Ok(v, a): r2 ← q(v); combine a with r2's result
                           return r (or r2) unchanged if it is Error/Failure
function Alt(p, q)(x):     r ← p(x);  if r = Error(e1): r2 ← q(x)      # back to the SAME x
                                        if r2 = Error(e2): return Error(Merge(e1, e2))
                                        return r2
                           return r
function Many0(p)(x):      acc ← [];  loop: r ← p(x)
                               if r = Ok(v, a) and v ≠ x: append a to acc;  x ← v
                               else if r = Failure(e): return Failure(e)
                               else return Ok(x, acc)                    # x: before the failed try
function Cut(p)(x):        r ← p(x);  return Failure(e) if r = Error(e) else r
function Merge(e1, e2):    the error of Definition 4.5.6 (furthest position wins)

nom: backtracking many0 leaves the input it could not use

Reproduce (nom 8.0.0 and chumsky 0.10.1 from crates.io, rustc/cargo 1.94.1):

cargo new -q combi && cd combi && printf 'nom = "8"\nchumsky = "0.10"\n' >> Cargo.toml
cat > src/main.rs <<'EOF'
// nom 8 and chumsky 0.10: the same tiny grammar  sum := num (('+'|'-') num)*
use chumsky::prelude::*;
use nom::{
    branch::alt, character::complete::{char, digit1, space0}, combinator::map_res,
    multi::many0, sequence::{delimited, pair}, IResult, Parser as _,
};

fn num(i: &str) -> IResult<&str, i64> {
    map_res(delimited(space0, digit1, space0), str::parse).parse(i)
}
fn sum(i: &str) -> IResult<&str, i64> {
    let (i, first) = num(i)?;
    let (i, rest) = many0(pair(alt((char('+'), char('-'))), num)).parse(i)?;
    Ok((i, rest.into_iter().fold(first, |acc, (op, v)| if op == '+' { acc + v } else { acc - v })))
}

fn chumsky_sum<'a>() -> impl Parser<'a, &'a str, i64, extra::Err<Rich<'a, char>>> {
    let num = text::int(10).from_str::<i64>().unwrapped().padded();
    let op = just('+').or(just('-'));
    num.foldl(op.then(num).repeated(), |acc, (op, v)| if op == '+' { acc + v } else { acc - v })
        .then_ignore(end())
}

fn main() {
    for input in ["10 - 3 - 2", "10 - 3 -", "10 - x"] {
        println!("nom     {input:?}: {:?}", sum(input));
        match chumsky_sum().parse(input).into_result() {
            Ok(v) => println!("chumsky {input:?}: Ok({v})"),
            Err(errs) => for e in errs {
                println!("chumsky {input:?}: error at {:?}: found {:?}, expected {:?}",
                         e.span(), e.found(), e.expected().map(|x| x.to_string()).collect::<Vec<_>>());
            },
        }
    }
}
EOF
cargo run -q

Output (complete):

nom     "10 - 3 - 2": Ok(("", 5))
chumsky "10 - 3 - 2": Ok(5)
nom     "10 - 3 -": Ok(("-", 7))
chumsky "10 - 3 -": error at 8..8: found None, expected ["any", "''0''"]
nom     "10 - x": Ok(("- x", 10))
chumsky "10 - x": error at 5..6: found Some('x'), expected ["non-zero digit", "''0''"]

What to notice: on 10 - 3 - nom's many0 tried pair(op, num) a second time, consumed -, failed on num, and backtracked to before the -: the parse "succeeds" with value 7 and leaves "-" unconsumed (Definition 4.5.2). A caller must check for leftover input (nom's all_consuming) or use cut after the operator. chumsky, with end(), rejects the input and reports the furthest failure (the end of input, position 8), not the position of the backtracked - (Definition 4.5.6). (The ''0'' spelling is chumsky 0.10.1's own quoting of the expected character.)

Committed choice¶

Definition 4.5.4 (Parsec's replies: consumed or empty)

A Parsec parser returns one of four replies: \(\mathsf{Consumed}(\mathsf{Ok}\ a\ v)\), \(\mathsf{Consumed}(\mathsf{Error}\ e)\), \(\mathsf{Empty}(\mathsf{Ok}\ a\ v)\), \(\mathsf{Empty}(\mathsf{Error}\ e)\): whether it consumed input, and whether it succeeded. Committed choice \(p \mathbin{<\!|\!>} q\) runs \(q\) only when \(p\) returns \(\mathsf{Empty}(\mathsf{Error})\); a \(\mathsf{Consumed}\) reply of \(p\) is final. \(\mathsf{try}\,p\) turns \(\mathsf{Consumed}(\mathsf{Error}\ e)\) into \(\mathsf{Empty}(\mathsf{Error}\ e)\), re-enabling backtracking for \(p\) only. many p stops successfully on \(\mathsf{Empty}(\mathsf{Error})\) and fails on \(\mathsf{Consumed}(\mathsf{Error})\).

Algorithm 4.5.5 (Committed choice and try)

Input: Parsec-style parsers; an input.
Output: one of the four replies.
Precondition: no left recursion; many is never applied to a parser that can succeed without consuming (Parsec raises an error for it).
Postcondition: without try, every token is examined by a bounded number of primitive tests before the parser commits past it (Theorem 4.5.10).
Invariant: once any parser returns \(\mathsf{Consumed}\), no enclosing <|> re-reads the consumed input unless a try encloses that parser.

function Choice(p, q)(x):
    r ← p(x)
    if r = Empty(Error e1):
        r2 ← q(x)
        if r2 = Empty(Error e2): return Empty(Error Merge(e1, e2))
        if r2 = Empty(Ok a v e2): return Empty(Ok a v Merge(e1, e2))
        return r2
    return r                                   # Consumed(...) or Empty(Ok ...): committed
function Try(p)(x):
    r ← p(x)
    return Empty(Error e) if r = Consumed(Error e) else r
function Many(p)(x):
    acc ← [];  consumedAny ← false
    loop:
        r ← p(x)
        if r = Consumed(Ok a v): append a;  x ← v;  consumedAny ← true
        else if r = Consumed(Error e): return Consumed(Error e)        # no backtracking
        else if r = Empty(Error e): return (Consumed if consumedAny else Empty)(Ok acc x)
        else: raise "many applied to a parser that accepts the empty string"

Parsec: committed choice vs try on the same grammar

Reproduce (GHC 9.4.7 with its bundled parsec 3.1.16.1):

cat > Sum.hs <<'EOF'
-- Parsec on  sum := num (op num)*  with and without try.
import Text.Parsec
import Text.Parsec.String (Parser)

num :: Parser Integer
num = read <$> many1 digit <* spaces

op :: Parser (Integer -> Integer -> Integer)
op = ((-) <$ char '-' <|> (+) <$ char '+') <* spaces

sumP, sumTry :: Parser Integer
sumP   = foldl (\acc (f, v) -> f acc v) <$> num <*> many ((,) <$> op <*> num)
sumTry = foldl (\acc (f, v) -> f acc v) <$> num <*> many (try ((,) <$> op <*> num))

main :: IO ()
main = mapM_ run ["10 - 3 - 2", "10 - 3 -", "10 - x"]
  where run s = do
          putStrLn (show s ++ " committed:  " ++ show (parse sumP "" s))
          putStrLn (show s ++ " with try:   " ++ show (parse sumTry "" s))
EOF
ghc -O0 -package parsec Sum.hs -o sum > /dev/null && ./sum

Output (complete):

"10 - 3 - 2" committed:  Right 5
"10 - 3 - 2" with try:   Right 5
"10 - 3 -" committed:  Left (line 1, column 9):
unexpected end of input
expecting white space or digit
"10 - 3 -" with try:   Right 7
"10 - x" committed:  Left (line 1, column 6):
unexpected "x"
expecting space or digit
"10 - x" with try:   Right 10

What to notice: committed: op consumed the second -, then num failed, so many fails with \(\mathsf{Consumed}(\mathsf{Error})\) and the error points exactly at the problem (column 9, end of input; column 6, x). With try around the operator–operand pair, many backs out as nom did: the parse "succeeds" with 7 and 10 and leaves input behind. The expecting white space or digit list is the merge of the empty errors of spaces and digit at that position (Definition 4.5.6).

Error reporting and recovery in combinators¶

Definition 4.5.6 (Errors with the furthest-failure merge)

An error is a pair \((f, E)\) of an input position and a set of expected items (tokens, or labels such as "digit"). The merge of \((f_1, E_1)\) and \((f_2, E_2)\) is \((f_1, E_1)\) if \(f_1 > f_2\), \((f_2, E_2)\) if \(f_2 > f_1\), and \((f_1, E_1 \cup E_2)\) if \(f_1 = f_2\). A parser's final error is the merge of all failures of terminal tests during the parse: the furthest failure and everything expected there.

Algorithm 4.5.7 (Recovery by skipping: recover_with)

Input: a parser \(p\), a recovery parser \(r\) that consumes at least one token and returns a placeholder, an input position \(i\).
Output: \(p\)'s result at \(i\) if it succeeds; otherwise \(r\)'s placeholder, with \(p\)'s error recorded (not returned), and parsing continues after \(r\).
Precondition: \(r\) always consumes input when it succeeds (else recovery could loop).
Postcondition: every recorded error is a real failure of \(p\); the output has a placeholder exactly where recovery happened.
Invariant: the list of recorded errors only grows; each recovery consumes at least one token, so a parse with recovery still terminates.

function RecoverWith(p, r)(i):
    res ← p(i)
    if res succeeds: return res
    mark ← position;  record res.error in the error list
    res2 ← r(i)                                  # e.g. skip tokens that are not ',' or ']'
    if res2 succeeds: return Ok(res2.placeholder, res2.end)
    rewind to mark;  return res                  # recovery failed: report the original error

chumsky: several errors and a partial AST from one run

Reproduce (chumsky 0.10.1, rustc/cargo 1.94.1, in the combi project of the nom box):

mkdir -p src/bin && cat > src/bin/recover.rs <<'EOF'
// chumsky 0.10: error recovery inside a combinator parser.
use chumsky::prelude::*;

fn list<'a>() -> impl Parser<'a, &'a str, Vec<Option<i64>>, extra::Err<Rich<'a, char>>> {
    let item = text::int(10)
        .from_str::<i64>()
        .unwrapped()
        .map(Some)
        .padded()
        // on a bad item: report it, skip ahead to the next ',' or ']', and yield None
        .recover_with(via_parser(none_of(",]").repeated().at_least(1).padded().to(None)));
    item.separated_by(just(','))
        .collect::<Vec<_>>()
        .delimited_by(just('['), just(']'))
        .then_ignore(end())
}

fn main() {
    for input in ["[1, 2, 3]", "[1, x, 3, y y, 5]"] {
        let (out, errs) = list().parse(input).into_output_errors();
        println!("{input:?}: output {out:?}");
        for e in errs {
            println!("  error at {:?}: found {:?}", e.span(), e.found());
        }
    }
}
EOF
cargo run -q --bin recover

Output (complete):

"[1, 2, 3]": output Some([Some(1), Some(2), Some(3)])
"[1, x, 3, y y, 5]": output Some([Some(1), None, Some(3), None, Some(5)])
  error at 4..5: found Some('x')
  error at 10..11: found Some('y')

What to notice: Algorithm 4.5.7: two independent errors, each recorded where the item parser failed, and an output list with placeholders (None) where recovery skipped x and y y. via_parser (chumsky's recovery module [CHUMSKY]) is the combinator form of panic mode with the synchronizing set \(\{\),, ]\(\}\) (Lesson 2.7).

3. Worked example¶

Grammar sum := num (op num)*, op := '+' | '-', input 1+2+ (positions 0–4, no spaces; the boxes above ran the same grammar with spaces). Each row is one primitive test; "C/E" is Parsec's consumed/empty flag.

step	parser	pos	backtracking (nom `many0`)	committed (Parsec `many`)	`many (try …)` (Parsec)
1	`num`	0	Ok, rest `+2+`	C-Ok 1	C-Ok 1
2	`op` (iteration 1)	1	Ok `+`	C-Ok	C-Ok
3	`num`	2	Ok 2, rest `+`	C-Ok 2	C-Ok 2
4	`op` (iteration 2)	3	Ok `+`	C-Ok	C-Ok
5	`num`	4	Error (end, expected digit)	E-Error at 4	E-Error at 4
6	pair `op num`	3	Error → `many0` stops, input rewinds to 3	C-Error (op consumed) → `many` fails	`try` turns it into E-Error → `many` stops at 3
7	result		Ok(value 3, rest `+`)	Error at 4: "unexpected end of input, expecting digit"	Ok(value 3, rest `+`)

With many0 or try, the error at position 4 is discarded: the caller sees a success with leftover input, and a later check (end(), eof, all_consuming) fails at position 3, one token before the real problem — unless errors are merged by the furthest-failure rule, which reports position 4 (chumsky's 8..8 in the box is exactly this).
Committed choice reports position 4 directly and never re-reads input: the price is that a grammar with a common prefix between alternatives (let vs lex) needs try or left-factoring.

Try it

./course drill packrat-memo --difficulty hard --seed 1 --solution traces ordered choice with backtracking (the prefix-capture grammar \(S \leftarrow a \,/\, a\,b\)), which is what nom's alt computes; ./course drill paradigm-accepts asks which grammars keep their meaning under ordered choice.

4. Invariants and correctness¶

Proposition 4.5.8 (List of successes computes all parses)

Build a list-of-successes parser \(\hat{X}\) for each symbol of a CFG without left recursion: \(\hat{a}\) tests terminal \(a\), \(\hat{A} = \widehat{\alpha_1} \mathbin{+\!\!+} \cdots \mathbin{+\!\!+} \widehat{\alpha_m}\) for \(A \to \alpha_1 \mid \cdots \mid \alpha_m\), sequences by \(\mathbin{>\!\!>\!\!=}\). Then for every suffix \(x_{i+1} \cdots x_n\) of the input, the remaining inputs in \(\hat{X}(x_{i+1} \cdots x_n)\) are exactly \(\{\, x_{j+1} \cdots x_n \mid j \in \mathrm{Parse}(X, i) \,\}\) of Definition 2.5.3, each listed once per parse tree.

Proof

By induction on the remaining length \(n - i\) and, at a fixed position, on the "calls before consuming" relation, which is acyclic because the grammar has no left recursion (as in Theorem 4.2.4): at a fixed position the calls form a finite tree. Terminal: \(\hat{a}\) returns the one remaining input after \(a\) iff \(x_{i+1} = a\). Sequence \(Y_1 \cdots Y_k\): \(\mathbin{>\!\!>\!\!=}\) feeds each remaining input of \(\widehat{Y_1}\) into the rest, so the remaining inputs are \(\{ x_{j+1} \cdots \mid j \in \mathrm{Seq}(Y_1 \cdots Y_k, i) \}\) by the induction hypothesis, one per combination of sub-parses. Choice concatenates the lists of the alternatives, whose union is \(\mathrm{Parse}(A, i)\) by the definition of derivation. Multiplicities multiply along sequences and add along choices, which counts parse trees.

Proposition 4.5.9 (Backtracking combinators are PEGs)

Translate a PEG to backtracking combinators: / to alt, sequence to Seq, e* to many0, &e/!e to peek/not, terminals to tag. Then the combinator parser returns \(\mathsf{Ok}\) with remaining input \(x_{j+1} \cdots x_n\) exactly when \(\mathrm{match}(e, i) = j\) (Definition 4.2.2), and \(\mathsf{Error}\) exactly when \(\mathrm{match}(e, i) = \mathsf{fail}\) (for grammars without cut).

Proof

Structural induction, case by case against Definition 4.2.2: alt returns the first alternative's \(\mathsf{Ok}\) or, on its \(\mathsf{Error}\), the second's result on the same input — the rule for \(e_1 / e_2\); Seq and the rule for \(e_1 e_2\) both fail at the first failure; many0 stops on \(\mathsf{Error}\) and returns the input before the failed attempt — the rule for \(e^{*}\), including the stop on a non-consuming success (Algorithm 4.5.3's v ≠ x test); predicates restore the input. Termination for well-formed grammars follows from Theorem 4.2.4. In particular nom's alt has PEG's prefix-capture pitfall (Lesson 4.2) and PEG's exponential worst case without memoization (Proposition 4.2.11).

Theorem 4.5.10 (Committed choice without try is predictive and linear)

For Parsec parsers built from primitives that inspect at most one token before consuming it, and without try, (a) once a primitive consumes a token, no parser re-examines that token, and (b) the parse runs in \(O(n \cdot d)\) time, where \(d\) bounds the number of alternatives examined at one position (a constant for a fixed grammar); errors are reported at the first token that no alternative can consume.

Proof sketch (full argument: [LM01, §3 and §5.1])

(a) By induction on the parser structure: sequencing passes the remaining input forward; <|> only runs \(q\) on the same input when \(p\) returned \(\mathsf{Empty}\), i.e. consumed nothing; many stops on \(\mathsf{Empty}(\mathsf{Error})\) and propagates \(\mathsf{Consumed}(\mathsf{Error})\); so input once consumed is never given to another alternative, and only try could rewind. (b) At each position the parser runs through a chain of alternatives that each fail without consuming; each such failure is a bounded number of primitive tests, and the chain length is bounded by the grammar (as in an LL(1) decision). Each token is consumed once. Leijen and Meijer also show that returning \(\mathsf{Consumed}\) lazily (before the result is known) lets the input consumed so far be garbage-collected, which is the space-leak fix their paper is named for.

Proposition 4.5.11 (What the furthest failure tells you)

Let a backtracking or committed parser reject \(x\) and report the merged error \((f, E)\) of Definition 4.5.6. Then (a) \(f\) is the largest position at which any terminal test failed during the run, (b) some partial parse consumed \(x_1 \cdots x_f\) (every position before \(f\) was passed by a successful test of some attempt), and (c) \(E\) is the set of items tested and failed at \(f\). If moreover the grammar is LL(1) and choice is committed, \(f\) is the correct-prefix error position of Definition 2.5.2.

Proof

(a) and (c) follow from the merge: it keeps the maximum position and unites the expectation sets at equal positions, and every failure of a terminal test is merged in. (b) A test at position \(f > 0\) is only performed after the preceding tests of the same attempt succeeded on \(x_1 \cdots x_f\) (sequencing reaches position \(f\) only by consuming). For an LL(1) grammar with committed choice there is only one attempt at every position, so the parser is predictive, and a predictive parser detects the error at the first token that cannot continue a prefix of the language (Theorem 2.5.9).

5. Complexity¶

Let \(n\) be the input length, \(k\) the maximum number of alternatives of a choice and \(d\) the nesting depth of the input.

Technique	Time (worst)	Time (typical)	Space	Notes
List of successes	exponential (\(\Theta(k^{d})\) on nested choices)	exponential whenever ambiguity or backtracking is deep	the lists	memoization (Frost & Hafiz) makes it polynomial
Backtracking single-result (nom)	exponential without memoization (Proposition 4.2.11 applies verbatim)	linear when alternatives fail within a token or two	\(O(d)\) stack	`cut`/`Failure` bounds backtracking
Committed (Parsec, no `try`)	\(O(k\,n)\) (Theorem 4.5.10)	linear	\(O(d)\) stack; lazy consumed flag frees consumed input	`try` reintroduces the backtracking cost where written
Furthest-failure merge / recovery	\(O(1)\) per failed test (a max and a set union)	negligible	the expected set	recovery adds at most the skipped tokens

Pathological family. The PEG of Proposition 4.2.11 written with nom's alt (alt((pair(a, tag("x")), pair(a, tag("y")), a))) makes \(2 \cdot 3^{d+1} - 2\) calls on \(d\) nested parentheses; written with Parsec's committed choice it rejects every input: the first alternative a 'x' consumes the input of a and then fails on x, a \(\mathsf{Consumed}(\mathsf{Error})\), so <|> never tries the other two. The author must add try (restoring the exponential behavior) or left-factor to a ('x' <|> 'y' <|> return ()) (linear).

At scale. Combinator parsers pay a function call (often an indirect one) per primitive; Rust libraries such as nom and chumsky are monomorphized, so the calls inline, while Parsec-style parsers in Haskell allocate a reply per primitive. None of the mainstream compilers covered in this course (Clang, GCC, rustc, swiftc, Go) uses a combinator library for its main parser.

Backtracking combinators¶

Memoized combinators (Frost & Hafiz 2006 [FH06]; Johnson 1995): tabulate (parser, position) and curtail left recursion — trade-off: polynomial time and left recursion, with memory per position (packrat's trade-off).
Applicative vs monadic interfaces (Swierstra & Duponcheel 1996 [SD96]): if the rest of the parse does not depend on earlier results, the combinators can be analyzed before running (FIRST sets, error correction) — trade-off: less expressive (no context-sensitive >>=), but static analysis becomes possible.

Committed choice¶

Megaparsec's hidden labels and observing: better control of which alternatives contribute to "expecting …" — trade-off: more annotations in the grammar.
cut in backtracking libraries (nom's cut, Prolog's cut, PEG cut operators [MMY10]): commit locally — trade-off: the grammar author must place cuts; misplaced cuts reject valid input.

Error reporting and recovery in combinators¶

Error-correcting combinators (Swierstra & Duponcheel [SD96]): compute a minimal-cost repair (insert/delete) inside the combinators — trade-off: Burke–Fisher-style repairs (Lesson 3.7) at the cost of exploring alternatives.
Strategy-based recovery (chumsky's skip_then_retry_until, nested_delimiters, via_parser [CHUMSKY]): the author picks a synchronizing strategy per construct — trade-off: resilient parsing in a library; strategies must be chosen with care to avoid cascades.

7. In real compilers¶

Combinator libraries are common in interpreters, configuration languages, DSLs, binary-format parsers and language servers written in functional languages; the large C/C++/Rust/Swift/Go compilers hand-write recursive descent. Idris 2's parser is written with its own combinator library (src/Libraries/Text/Parser/Core.idr [IDRIS2-Parser]); GHC's uses Happy (LALR).

Backtracking combinators¶

nom (Rust) is used in binary-format and protocol parsers (its README lists users; the combinators are in src/branch/mod.rs alt and src/multi/mod.rs many0 [NOM]). The box after Algorithm 4.5.3 shows its backtracking many0.

Committed choice¶

Parsec and Megaparsec (Haskell): Text/Parsec/Prim.hs defines <|>, try and the consumed/empty replies [PARSEC-Prim]. The box after Algorithm 4.5.5 shows committed choice vs try.

Error reporting and recovery in combinators¶

chumsky (Rust) is designed around recovery for compilers and language servers (its README's "error recovery" feature; the recovery module [CHUMSKY]); Parsec's mergeError implements Definition 4.5.6's merge. The box after Algorithm 4.5.7 shows chumsky recovering twice in one run.

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Backtracking combinators (list of successes; nom-style ordered choice)	All parses of any non-left-recursive CFG (list of successes); PEG semantics for single-result backtracking (Proposition 4.5.9)	Exponential worst case; linear when failures are shallow	Poor by default: leftover input instead of an error (nom box) unless errors are merged or `cut` is used	Lowest: a library, grammar in the host language	nom for binary formats, prototypes, small DSLs
Committed choice (Parsec + `try`)	LL(1)-style predictive, plus local backtracking where `try` is written	\(O(k\,n)\) without `try` (Theorem 4.5.10)	Good: the error is at the first token no alternative consumes (column 9 and 6 in the Parsec box)	Low; `try` placement needs understanding	Parsec/Megaparsec in Haskell compilers and tools
Furthest-failure reporting and recovery (chumsky)	Adds error merging and recovery to either family	\(O(1)\) per failure; recovery linear in skipped tokens	Best among combinators: several errors per run, partial ASTs with placeholders	Medium: recovery strategies per construct	chumsky-based compilers and language servers, packrat parsers

Choose backtracking combinators when the grammar is small, inputs are trusted and errors need not be precise (binary formats, config). Choose committed choice when you want predictable linear parsing and good errors from a library, and can left-factor or place try. Choose a recovering library when the parser serves an editor or must report many errors per run.

9. Assessment¶

Technique	Quiz ids	Drill	Flashcard tag	Exercises
Backtracking combinators	`nom-leftover`, `los-count`	`packrat-memo` (ordered choice with backtracking)	`combinators`	—
Committed choice	`parsec-commit`, `parsec-try-cost`	`paradigm-accepts` (LL(1) = committed choice without `try`)	`parsec`	—
Furthest-failure reporting and recovery	`furthest-failure`, `recovery-placeholders`	`packrat-memo --difficulty hard` (the furthest failed test)	`error-recovery`	E5–E6 use the same ideas in the Pebble parser

References¶

See the chapter references.

Lesson 4.5 — Parser combinators: backtracking, committed choice, error reporting and recovery¶

1. Problem and motivation¶

Backtracking combinators¶

Committed choice¶

Error reporting and recovery in combinators¶

2. Definitions and algorithms¶

Backtracking combinators¶

Committed choice¶

Error reporting and recovery in combinators¶

3. Worked example¶

4. Invariants and correctness¶

5. Complexity¶

6. Variants and refinements¶

Backtracking combinators¶

Committed choice¶

Error reporting and recovery in combinators¶

7. In real compilers¶

Backtracking combinators¶

Committed choice¶

Error reporting and recovery in combinators¶

8. Comparison¶

9. Assessment¶

References¶