157 Advanced

Choice Parser

Functional Programming

Tutorial

The Problem

Grammars have alternatives: a value is either a number, a string, a boolean, or null. The alt (or choice) combinator tries parsers in order, returning the first success. If all fail, it returns the last error. This ordered choice is the basis for all ambiguity resolution in parsing — the order of alternatives determines precedence. Getting alternatives right (trying most specific before most general) is key to correct parsers.

🎯 Learning Outcomes

• Understand alt/choice as ordered alternative (PEG-style, not CFG-style)

• Learn why order matters: choice([tag("if"), identifier]) vs. choice([identifier, tag("if")])

• See how backtracking enables alternatives to recover from failed branches

• Practice building a boolean parser and a simple expression parser using choice

Code Example

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),
    })
}

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

Key Differences

Backtracking semantics: Rust's simple choice always backtracks fully; angstrom's <|> does not backtrack after consuming input (requires explicit option/try).

Error reporting: On total failure, Rust returns the last error; angstrom returns a custom error combining all branch messages.

Ordered vs. unordered: Both treat alternatives as ordered (PEG semantics); neither attempts all alternatives simultaneously (CFG semantics).

Precedence: Higher alternatives shadow lower ones if they match the same prefix; this is intentional in PEG parsers for disambiguating grammars.

OCaml Approach

OCaml's angstrom uses <|> as the choice operator:

let value = int_parser <|> string_parser <|> bool_parser <|> null_parser

Angstrom's choice is greedy and does not backtrack by default — if the first parser consumes input and then fails, the alternative is not tried. This is a key difference from Parsec/Rust's simple implementation. Backtracking requires wrapping the parser in try / option.

Full Source

#![allow(clippy::all)]
// 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)),
        },
    })
}

#[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"

✓ Tests Rust test suite

#[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"));
    }
}

Deep Comparison

Comparison: Example 157 — Choice Parser

alt

OCaml:

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

OCaml:

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

Rust:

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())
    })
}

Exercises

Write a json_value_parser using choice that handles null, true/false, numbers, and strings.

Demonstrate the ordering issue: show that choice([identifier, tag("true")]) treats "true" as an identifier, while choice([tag("true"), identifier]) parses it as a boolean.

Build an enum parser that maps each alternative to a Rust enum variant.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust