158 Advanced

Sequence Parser

Functional Programming

Tutorial

The Problem

Most grammar rules require multiple things in order: a key-value pair is identifier "=" value, a function call is identifier "(" args ")". Sequence combinators run two or more parsers in order, combining their results. pair keeps both results. preceded discards the first (e.g., parse "(" then value — keep value). terminated discards the second. delimited discards both ends and keeps the middle — the most common case for parenthesized expressions.

🎯 Learning Outcomes

• Implement pair, preceded, terminated, and delimited sequence combinators

• Understand how sequence combinators propagate failures: if any parser fails, the whole sequence fails

• Learn the "discard wrapper, keep content" idiom (delimited, preceded, terminated)

• Practice building compound parsers: parenthesized expressions, key-value pairs

Code Example

fn pair<'a, A: 'a, B: 'a>(p1: Parser<'a, A>, p2: Parser<'a, B>) -> Parser<'a, (A, B)> {
    Box::new(move |input: &'a str| {
        let (v1, rest) = p1(input)?;
        let (v2, remaining) = p2(rest)?;
        Ok(((v1, v2), remaining))
    })
}

let pair (p1 : 'a parser) (p2 : 'b parser) : ('a * 'b) parser = fun input ->
  match p1 input with
  | Error e -> Error e
  | Ok (v1, rest) ->
    match p2 rest with
    | Error e -> Error e
    | Ok (v2, remaining) -> Ok ((v1, v2), remaining)

Key Differences

Operator syntax: OCaml's *> and <* operators make sequence parsing compact and directional; Rust uses named combinators (preceded, terminated) which are more explicit.

Error propagation: Both short-circuit on failure and return the failing parser's error; the sequence is always left-to-right.

Tuple results: Rust's pair returns (A, B); OCaml's both returns (a * b) — structurally the same.

Arity: Both languages' sequence combinators are binary; for more than two, nesting or tuple3/tuple4 variants are used.

OCaml Approach

Angstrom provides both : 'a t -> 'b t -> ('a * 'b) t, preceded, terminated, delimited directly. The infix *> (sequence, keep right) and <* (sequence, keep left) operators give the most concise syntax:

let delimited open_ p close = open_ *> p <* close

OCaml's operator syntax makes sequence parsing arguably the most readable of all combinator styles.

Full Source

#![allow(clippy::all)]
// Example 158: Sequence Parser
// pair, preceded, terminated, delimited: sequence combinators

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

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

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

// ============================================================
// Approach 1: pair — run two parsers, return both results
// ============================================================

fn pair<'a, A: 'a, B: 'a>(p1: Parser<'a, A>, p2: Parser<'a, B>) -> Parser<'a, (A, B)> {
    Box::new(move |input: &'a str| {
        let (v1, rest) = p1(input)?;
        let (v2, remaining) = p2(rest)?;
        Ok(((v1, v2), remaining))
    })
}

// ============================================================
// Approach 2: preceded, terminated — discard one side
// ============================================================

fn preceded<'a, A: 'a, B: 'a>(prefix: Parser<'a, A>, p: Parser<'a, B>) -> Parser<'a, B> {
    Box::new(move |input: &'a str| {
        let (_, rest) = prefix(input)?;
        p(rest)
    })
}

fn terminated<'a, A: 'a, B: 'a>(p: Parser<'a, A>, suffix: Parser<'a, B>) -> Parser<'a, A> {
    Box::new(move |input: &'a str| {
        let (value, rest) = p(input)?;
        let (_, remaining) = suffix(rest)?;
        Ok((value, remaining))
    })
}

// ============================================================
// Approach 3: delimited — discard both sides, keep middle
// ============================================================

fn delimited<'a, A: 'a, B: 'a, C: 'a>(
    open: Parser<'a, A>,
    p: Parser<'a, B>,
    close: Parser<'a, C>,
) -> Parser<'a, B> {
    Box::new(move |input: &'a str| {
        let (_, r1) = open(input)?;
        let (value, r2) = p(r1)?;
        let (_, r3) = close(r2)?;
        Ok((value, r3))
    })
}

/// Triple — three parsers in sequence
fn triple<'a, A: 'a, B: 'a, C: 'a>(
    p1: Parser<'a, A>,
    p2: Parser<'a, B>,
    p3: Parser<'a, C>,
) -> Parser<'a, (A, B, C)> {
    Box::new(move |input: &'a str| {
        let (v1, r1) = p1(input)?;
        let (v2, r2) = p2(r1)?;
        let (v3, r3) = p3(r2)?;
        Ok(((v1, v2, v3), r3))
    })
}

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

    #[test]
    fn test_pair() {
        let p = pair(
            satisfy(|c| c.is_ascii_lowercase(), "letter"),
            satisfy(|c| c.is_ascii_digit(), "digit"),
        );
        assert_eq!(p("a1"), Ok((('a', '1'), "")));
    }

    #[test]
    fn test_pair_fail_first() {
        let p = pair(
            satisfy(|c| c.is_ascii_lowercase(), "letter"),
            satisfy(|c| c.is_ascii_digit(), "digit"),
        );
        assert!(p("1a").is_err());
    }

    #[test]
    fn test_preceded() {
        let p = preceded(tag("("), satisfy(|c| c.is_ascii_lowercase(), "letter"));
        assert_eq!(p("(a)"), Ok(('a', ")")));
    }

    #[test]
    fn test_terminated() {
        let p = terminated(satisfy(|c| c.is_ascii_lowercase(), "letter"), tag(";"));
        assert_eq!(p("a;rest"), Ok(('a', "rest")));
    }

    #[test]
    fn test_delimited() {
        let p = delimited(
            tag("("),
            satisfy(|c| c.is_ascii_lowercase(), "letter"),
            tag(")"),
        );
        assert_eq!(p("(x)rest"), Ok(('x', "rest")));
    }

    #[test]
    fn test_delimited_fail_close() {
        let p = delimited(
            tag("("),
            satisfy(|c| c.is_ascii_lowercase(), "letter"),
            tag(")"),
        );
        assert!(p("(x]").is_err());
    }

    #[test]
    fn test_triple() {
        let p = triple(
            satisfy(|c| c.is_ascii_lowercase(), "letter"),
            satisfy(|c| c.is_ascii_digit(), "digit"),
            satisfy(|c| c.is_ascii_lowercase(), "letter"),
        );
        assert_eq!(p("a1b"), Ok((('a', '1', 'b'), "")));
    }
}

(* Example 158: Sequence Parser *)
(* pair, preceded, terminated, delimited: sequence combinators *)

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

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)

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)

(* Approach 1: pair — run two parsers in sequence, return both results *)
let pair (p1 : 'a parser) (p2 : 'b parser) : ('a * 'b) parser = fun input ->
  match p1 input with
  | Error e -> Error e
  | Ok (v1, rest) ->
    match p2 rest with
    | Error e -> Error e
    | Ok (v2, remaining) -> Ok ((v1, v2), remaining)

(* Approach 2: preceded, terminated — discard one side *)
let preceded (prefix : 'a parser) (p : 'b parser) : 'b parser = fun input ->
  match prefix input with
  | Error e -> Error e
  | Ok (_, rest) -> p rest

let terminated (p : 'a parser) (suffix : 'b parser) : 'a parser = fun input ->
  match p input with
  | Error e -> Error e
  | Ok (v, rest) ->
    match suffix rest with
    | Error e -> Error e
    | Ok (_, remaining) -> Ok (v, remaining)

(* Approach 3: delimited — discard both sides *)
let delimited (open_p : 'a parser) (p : 'b parser) (close_p : 'c parser) : 'b parser =
  fun input ->
    preceded open_p (terminated p close_p) input

(* triple — three in sequence *)
let triple (p1 : 'a parser) (p2 : 'b parser) (p3 : 'c parser) : ('a * 'b * 'c) parser =
  fun input ->
    match p1 input with
    | Error e -> Error e
    | Ok (v1, r1) ->
      match p2 r1 with
      | Error e -> Error e
      | Ok (v2, r2) ->
        match p3 r2 with
        | Error e -> Error e
        | Ok (v3, r3) -> Ok ((v1, v2, v3), r3)

(* Tests *)
let () =
  let letter = satisfy (fun c -> (c >= 'a' && c <= 'z')) "letter" in
  let digit = satisfy (fun c -> c >= '0' && c <= '9') "digit" in

  (* pair *)
  assert (pair letter digit "a1" = Ok (('a', '1'), ""));
  assert (Result.is_error (pair letter digit "1a"));

  (* preceded: skip prefix *)
  assert (preceded (tag "(") letter "(a)" = Ok ('a', ")"));

  (* terminated: skip suffix *)
  assert (terminated letter (tag ";") "a;rest" = Ok ('a', "rest"));

  (* delimited: extract middle *)
  assert (delimited (tag "(") letter (tag ")") "(x)rest" = Ok ('x', "rest"));

  (* triple *)
  assert (triple letter digit letter "a1b" = Ok (('a', '1', 'b'), ""));

  print_endline "✓ All tests passed"

✓ Tests Rust test suite

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

    #[test]
    fn test_pair() {
        let p = pair(
            satisfy(|c| c.is_ascii_lowercase(), "letter"),
            satisfy(|c| c.is_ascii_digit(), "digit"),
        );
        assert_eq!(p("a1"), Ok((('a', '1'), "")));
    }

    #[test]
    fn test_pair_fail_first() {
        let p = pair(
            satisfy(|c| c.is_ascii_lowercase(), "letter"),
            satisfy(|c| c.is_ascii_digit(), "digit"),
        );
        assert!(p("1a").is_err());
    }

    #[test]
    fn test_preceded() {
        let p = preceded(tag("("), satisfy(|c| c.is_ascii_lowercase(), "letter"));
        assert_eq!(p("(a)"), Ok(('a', ")")));
    }

    #[test]
    fn test_terminated() {
        let p = terminated(satisfy(|c| c.is_ascii_lowercase(), "letter"), tag(";"));
        assert_eq!(p("a;rest"), Ok(('a', "rest")));
    }

    #[test]
    fn test_delimited() {
        let p = delimited(
            tag("("),
            satisfy(|c| c.is_ascii_lowercase(), "letter"),
            tag(")"),
        );
        assert_eq!(p("(x)rest"), Ok(('x', "rest")));
    }

    #[test]
    fn test_delimited_fail_close() {
        let p = delimited(
            tag("("),
            satisfy(|c| c.is_ascii_lowercase(), "letter"),
            tag(")"),
        );
        assert!(p("(x]").is_err());
    }

    #[test]
    fn test_triple() {
        let p = triple(
            satisfy(|c| c.is_ascii_lowercase(), "letter"),
            satisfy(|c| c.is_ascii_digit(), "digit"),
            satisfy(|c| c.is_ascii_lowercase(), "letter"),
        );
        assert_eq!(p("a1b"), Ok((('a', '1', 'b'), "")));
    }
}

Deep Comparison

Comparison: Example 158 — Sequence Parser

pair

OCaml:

let pair (p1 : 'a parser) (p2 : 'b parser) : ('a * 'b) parser = fun input ->
  match p1 input with
  | Error e -> Error e
  | Ok (v1, rest) ->
    match p2 rest with
    | Error e -> Error e
    | Ok (v2, remaining) -> Ok ((v1, v2), remaining)

Rust:

fn pair<'a, A: 'a, B: 'a>(p1: Parser<'a, A>, p2: Parser<'a, B>) -> Parser<'a, (A, B)> {
    Box::new(move |input: &'a str| {
        let (v1, rest) = p1(input)?;
        let (v2, remaining) = p2(rest)?;
        Ok(((v1, v2), remaining))
    })
}

preceded / terminated

OCaml:

let preceded (prefix : 'a parser) (p : 'b parser) : 'b parser = fun input ->
  match prefix input with
  | Error e -> Error e
  | Ok (_, rest) -> p rest

Rust:

fn preceded<'a, A: 'a, B: 'a>(prefix: Parser<'a, A>, p: Parser<'a, B>) -> Parser<'a, B> {
    Box::new(move |input: &'a str| {
        let (_, rest) = prefix(input)?;
        p(rest)
    })
}

delimited

OCaml:

let delimited open_p p close_p = fun input ->
  preceded open_p (terminated p close_p) input

Rust:

fn delimited<'a, A: 'a, B: 'a, C: 'a>(
    open: Parser<'a, A>, p: Parser<'a, B>, close: Parser<'a, C>,
) -> Parser<'a, B> {
    Box::new(move |input: &'a str| {
        let (_, r1) = open(input)?;
        let (value, r2) = p(r1)?;
        let (_, r3) = close(r2)?;
        Ok((value, r3))
    })
}

Exercises

Parse a key-value pair "name: Alice" using pair(identifier_parser(), preceded(tag(": "), identifier_parser())).

Write a parenthesized expression parser using delimited(char_parser('('), expr_parser(), char_parser(')')).

Implement sequence_all<T>(parsers: Vec<Parser<T>>) -> Parser<Vec<T>> that runs all parsers in order.

Open Source Repos

functional-rust

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

Rust