157: Choice Parser

Difficulty: ⭐⭐⭐ Level: Foundations `alt` and `choice` try parsers in order and return the first one that succeeds — branching without `if`/`else`.

The Problem This Solves

Most grammars have alternatives. A JSON value is either a string, or a number, or a boolean, or null, or an array, or an object. A language expression is either an identifier, or a literal, or a parenthesized sub-expression. You need a way to say "try A, and if A fails, try B." Without a choice combinator, you'd write this by hand every time: run parser A, check if it failed, if yes run parser B, check if that failed too, etc. This is error-prone (easy to forget to reset the input position) and repetitive. `alt` and `choice` extract that pattern. The critical property is backtracking: when parser A fails, we go back to the original input position before trying parser B. In Rust, this is free — `&str` is `Copy`, so holding the original `input` is just holding a value, no cloning required.

The Intuition

`alt(p1, p2)` is like an `||` operator for parsers: "p1 OR p2." Try p1 first; if it fails, fall back to p2. If both fail, the whole thing fails. `choice(vec![p1, p2, p3, ...])` extends this to any number of alternatives. It tries each parser left-to-right and returns the first success. Important: order matters. `choice` is ordered — it tries parsers in the order you provide. If `tag("true")` comes before `tag("trueish")`, then `"trueish"` will match `"true"` and leave `"ish"` unconsumed. For this reason, put more specific alternatives before more general ones.

How It Works in Rust

`alt` — two alternatives:

fn alt<'a, T: 'a>(p1: Parser<'a, T>, p2: Parser<'a, T>) -> Parser<'a, T> {
 Box::new(move |input: &'a str| match p1(input) {
     Ok(result) => Ok(result),  // p1 succeeded — done
     Err(_)     => p2(input),   // p1 failed — try p2 from original position
 })
}

Notice `p2(input)` — not `p2(rest)`. We try p2 from the same starting position as p1. Since `input: &'a str` is `Copy`, this costs nothing. `choice` — list of alternatives:

fn choice<'a, T: 'a>(parsers: Vec<Parser<'a, T>>) -> Parser<'a, T> {
 Box::new(move |input: &'a str| {
     for parser in &parsers {
         if let Ok(result) = parser(input) {
             return Ok(result);  // first success wins
         }
         // failure: loop continues, trying from same input
     }
     Err("No parser matched".to_string())
 })
}

All parsers receive `input` (the original position) on each iteration. The `for` loop with `return` is the imperative equivalent of recursive backtracking. `alt_err` — accumulate error messages:

fn alt_err<'a, T: 'a>(p1: Parser<'a, T>, p2: Parser<'a, T>) -> Parser<'a, T> {
 Box::new(move |input: &'a str| match p1(input) {
     Ok(result) => Ok(result),
     Err(e1) => match p2(input) {
         Ok(result) => Ok(result),
         Err(e2)    => Err(format!("{} or {}", e1, e2)),  // combine both errors
     },
 })
}

When both fail, you get a message like `"Expected digit or Expected letter"` instead of just the last error. Better diagnostic messages = easier debugging. Usage:

// Boolean literal parser
let bool_p = alt(tag("true"), tag("false"));
println!("{:?}", bool_p("true!"));  // Ok(("true", "!"))
println!("{:?}", bool_p("false!")); // Ok(("false", "!"))
println!("{:?}", bool_p("maybe"));  // Err("Expected \"false\"")

// JSON primitive parser
let json_atom = choice(vec![tag("true"), tag("false"), tag("null")]);
println!("{:?}", json_atom("null!")); // Ok(("null", "!"))

What This Unlocks

Any grammar with variants — keywords, operators, literals — all expressed as `alt` or `choice`.
Ordered PEG grammars — unlike context-free grammars where ambiguity needs resolution, parser combinators use the order you specify to resolve it deterministically.
Error reporting — `alt_err` accumulates all attempted alternatives in the error, making it clear what was expected at each position.

Key Differences

Concept	OCaml	Rust
Two-way choice	`alt p1 p2` or `p1 <\	> p2`	`alt(p1, p2)`
List of choices	Recursive over a list	`Vec<Parser<'a, T>>` with `for` loop
Backtracking cost	Free (immutable strings, GC)	Free (`&str` is `Copy` — just a pointer)
Error accumulation	String concatenation in `Err`	`format!("{} or {}", e1, e2)`
Order sensitivity	Yes — first match wins	Yes — first match wins

// Example 157: Choice Parser
// alt / choice: try parsers in order, return first success

type ParseResult<'a, T> = Result<(T, &'a str), String>;
type Parser<'a, T> = Box<dyn Fn(&'a str) -> ParseResult<'a, T> + 'a>;

fn tag<'a>(expected: &str) -> Parser<'a, &'a str> {
    let exp = expected.to_string();
    Box::new(move |input: &'a str| {
        if input.starts_with(&exp) {
            Ok((&input[..exp.len()], &input[exp.len()..]))
        } else {
            Err(format!("Expected \"{}\"", exp))
        }
    })
}

fn satisfy<'a, F>(pred: F, desc: &str) -> Parser<'a, char>
where F: Fn(char) -> bool + 'a {
    let desc = desc.to_string();
    Box::new(move |input: &'a str| match input.chars().next() {
        Some(c) if pred(c) => Ok((c, &input[c.len_utf8()..])),
        _ => Err(format!("Expected {}", desc)),
    })
}

// ============================================================
// Approach 1: alt — try two parsers
// ============================================================

fn alt<'a, T: 'a>(p1: Parser<'a, T>, p2: Parser<'a, T>) -> Parser<'a, T> {
    Box::new(move |input: &'a str| match p1(input) {
        Ok(result) => Ok(result),
        Err(_) => p2(input),
    })
}

// ============================================================
// Approach 2: choice — try a list of parsers
// ============================================================

fn choice<'a, T: 'a>(parsers: Vec<Parser<'a, T>>) -> Parser<'a, T> {
    Box::new(move |input: &'a str| {
        for parser in &parsers {
            if let Ok(result) = parser(input) {
                return Ok(result);
            }
        }
        Err("No parser matched".to_string())
    })
}

// ============================================================
// Approach 3: alt with error accumulation
// ============================================================

fn alt_err<'a, T: 'a>(p1: Parser<'a, T>, p2: Parser<'a, T>) -> Parser<'a, T> {
    Box::new(move |input: &'a str| match p1(input) {
        Ok(result) => Ok(result),
        Err(e1) => match p2(input) {
            Ok(result) => Ok(result),
            Err(e2) => Err(format!("{} or {}", e1, e2)),
        },
    })
}

fn main() {
    println!("=== alt ===");
    let p = alt(tag("true"), tag("false"));
    println!("{:?}", p("true!"));  // Ok(("true", "!"))
    println!("{:?}", p("false!")); // Ok(("false", "!"))
    println!("{:?}", p("maybe"));  // Err(...)

    println!("\n=== choice ===");
    let p = choice(vec![tag("true"), tag("false"), tag("null")]);
    println!("{:?}", p("null!"));  // Ok(("null", "!"))

    println!("\n=== alt_err ===");
    let p = alt_err(
        satisfy(|c| c.is_ascii_digit(), "digit"),
        satisfy(|c| c.is_ascii_alphabetic(), "letter"),
    );
    println!("{:?}", p("5x"));  // Ok(('5', "x"))
    println!("{:?}", p("a1"));  // Ok(('a', "1"))
    println!("{:?}", p("!x"));  // Err("Expected digit or Expected letter")

    println!("\n✓ All examples completed");
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_alt_first() {
        let p = alt(tag("true"), tag("false"));
        assert_eq!(p("true!"), Ok(("true", "!")));
    }

    #[test]
    fn test_alt_second() {
        let p = alt(tag("true"), tag("false"));
        assert_eq!(p("false!"), Ok(("false", "!")));
    }

    #[test]
    fn test_alt_neither() {
        let p = alt(tag("true"), tag("false"));
        assert!(p("maybe").is_err());
    }

    #[test]
    fn test_choice_first() {
        let p = choice(vec![tag("a"), tag("b"), tag("c")]);
        assert_eq!(p("abc"), Ok(("a", "bc")));
    }

    #[test]
    fn test_choice_last() {
        let p = choice(vec![tag("x"), tag("y"), tag("z")]);
        assert_eq!(p("zoo"), Ok(("z", "oo")));
    }

    #[test]
    fn test_choice_none() {
        let p = choice(vec![tag("x"), tag("y")]);
        assert!(p("abc").is_err());
    }

    #[test]
    fn test_choice_empty() {
        let p: Parser<&str> = choice(vec![]);
        assert!(p("abc").is_err());
    }

    #[test]
    fn test_alt_err_accumulates() {
        let p = alt_err(
            satisfy(|c| c.is_ascii_digit(), "digit"),
            satisfy(|c| c.is_ascii_alphabetic(), "letter"),
        );
        let err = p("!x").unwrap_err();
        assert!(err.contains("digit"));
        assert!(err.contains("letter"));
    }
}

(* Example 157: Choice Parser *)
(* alt / choice: try parsers in order, return first success *)

type 'a parse_result = ('a * string, string) result
type 'a parser = string -> 'a parse_result

let tag expected : string parser = fun input ->
  let len = String.length expected in
  if String.length input >= len && String.sub input 0 len = expected then
    Ok (expected, String.sub input len (String.length input - len))
  else Error (Printf.sprintf "Expected \"%s\"" expected)

let satisfy pred desc : char parser = fun input ->
  if String.length input > 0 && pred input.[0] then
    Ok (input.[0], String.sub input 1 (String.length input - 1))
  else Error (Printf.sprintf "Expected %s" desc)

(* Approach 1: alt — try two parsers *)
let alt (p1 : 'a parser) (p2 : 'a parser) : 'a parser = fun input ->
  match p1 input with
  | Ok _ as result -> result
  | Error _ -> p2 input

(* Approach 2: choice — try a list of parsers *)
let choice (parsers : 'a parser list) : 'a parser = fun input ->
  let rec try_parsers = function
    | [] -> Error "No parser matched"
    | p :: rest ->
      match p input with
      | Ok _ as result -> result
      | Error _ -> try_parsers rest
  in
  try_parsers parsers

(* Approach 3: alt with error accumulation *)
let alt_err (p1 : 'a parser) (p2 : 'a parser) : 'a parser = fun input ->
  match p1 input with
  | Ok _ as result -> result
  | Error e1 ->
    match p2 input with
    | Ok _ as result -> result
    | Error e2 -> Error (Printf.sprintf "%s or %s" e1 e2)

(* Tests *)
let () =
  let true_or_false = alt (tag "true") (tag "false") in
  assert (true_or_false "true!" = Ok ("true", "!"));
  assert (true_or_false "false!" = Ok ("false", "!"));
  assert (Result.is_error (true_or_false "maybe"));

  let bool_or_null = choice [tag "true"; tag "false"; tag "null"] in
  assert (bool_or_null "null!" = Ok ("null", "!"));
  assert (bool_or_null "true" = Ok ("true", ""));
  assert (Result.is_error (bool_or_null "xyz"));

  let digit_or_letter = alt_err
    (satisfy (fun c -> c >= '0' && c <= '9') "digit")
    (satisfy (fun c -> (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) "letter") in
  assert (digit_or_letter "5x" = Ok ('5', "x"));
  assert (digit_or_letter "a1" = Ok ('a', "1"));
  assert (Result.is_error (digit_or_letter "!x"));

  print_endline "✓ All tests passed"

📊 Detailed Comparison

Comparison: Example 157 — Choice Parser

alt

OCaml:

🐪 Show OCaml equivalent

let alt (p1 : 'a parser) (p2 : 'a parser) : 'a parser = fun input ->
match p1 input with
| Ok _ as result -> result
| Error _ -> p2 input

Rust:

fn alt<'a, T: 'a>(p1: Parser<'a, T>, p2: Parser<'a, T>) -> Parser<'a, T> {
 Box::new(move |input: &'a str| match p1(input) {
     Ok(result) => Ok(result),
     Err(_) => p2(input),
 })
}

choice