In nom, parser combinators enable the construction of sophisticated parsers by assembling simpler ones. This compositional approach supports modularity, reuse, and even recursive structures.

Core Concepts

• Primitive parsers handle basic input elements like digits, specific characters, or whitespace.
• Combinators are higher-order functions that merge multiple parsers into new ones with richer logic.
• Nested composition allows building layered parsers—combinators themselves can be inputs too other combinators.

This hierarchical design lets you start small (e.g., parsing integers) and incrementally construct parsers for complex grammars like arithmetic expressions or structured data formats.

Example: Parsing Arithmetic Expressions

Consider a parser for addition expressions supporting parentheses, such as 42 + (10 + 5).

use nom::{
    character::complete::{digit1, char, space0},
    sequence::{preceded, delimited, pair},
    combinator::map,
    branch::alt,
    multi::many1,
    IResult,
};

// Parse an integer from digit characters
fn parse_integer(input: &str) -> IResult<&str, i32> {
    map(digit1, |s| s.parse().unwrap())(input)
}

// Parse either an integer or a parenthesized expression
fn parse_term(input: &str) -> IResult<&str, i32> {
    alt((
        parse_integer,
        delimited(char('('), parse_expression, char(')'))
    ))(input)
}

// Parse a sequence of terms separated by '+' operators
fn parse_expression(input: &str) -> IResult<&str, i32> {
    let (remaining, first) = parse_term(input)?;
    let (remaining, ops) = many1(
        preceded(space0, pair(char('+'), parse_term))
    )(remaining)?;

    let total = ops.into_iter().fold(first, |acc, (_, val)| acc + val);
    Ok((remaining, total))
}

Here:

• parse_term handles atomic values (integers or sub-expressions in parentheses).
• parse_expression chains one or more terms with +, respecting operator precedence via parentheses.

Advanced Composition Techniques

Beyond sequential parsing, nom provides combinators for diverse scenarios:

• alt: Choose between alternative parsers (e.g., different literal types).
• separated_list0: Parse comma-separated values.
• terminated: Match a parser followed by a delimiter (e.g., statements ending with semicolons).

These tools facilitate building parsers for real-world formats like JSON, CSV, or domain-specific languages by layering simple rules into robust grammars.