rust-peg

When choosing a parser generator, consider these characteristics of rust-peg compared to alternatives:

• Parser Type: Uses Parsing Expression Grammar (PEG).
• Action Code: Embedded directly within the grammar definition.
• Integration: Uses a procedural macro (block-based).
• Input Types: Supports &str, &[T], and custom types.
• Precedence Climbing: Supported.
• Parameterized Rules: Supported.
• Streaming Input: Not supported.

You can define a recursive descent parser using the peg::parser! procedural macro. The macro takes a grammar definition that specifies the input type (e.g., str, &[u8], or a custom type) and a set of rules. Rules can return values, accept arguments for reusability, and include embedded Rust code for semantic actions.

Key features include:

• Support for &str, &[u8], &[T], or custom types.
• Precedence climbing for expressions.
• Parameterized rules.
• Rule-level tracing for debugging.

peg::parser!{
  grammar list_parser() for str {
    rule number() -> u32
      = n:$(['0'..='9']+) {? n.parse().or(Err("u32")) }

    pub rule list() -> Vec<u32>
      = "[" l:(number() ** ",") "]" { l }
  }
}

pub fn main() {
    assert_eq!(list_parser::list("[1,1,2,3,5,8]"), Ok(vec![1, 1, 2, 3, 5, 8]));
}

While str, &[u8], and &[T] are supported out of the box, you can use custom types by implementing specific traits:

• Parse: The base trait required for all inputs.
• ParseElem: Required to use the [_] pattern operator.
• ParseLiteral: Required to match against "string" literals.
• ParseSlice: Required to use the $() slice operator.

The precedence!{ ... } macro implements the precedence climbing algorithm. Each -- separator introduces a new precedence level that binds more tightly than the previous one.

• @ or (@): Represents the operands.
• x:(@) "+" y:@: An infix operator (starts and ends with @).
• x:(@) "-": A postfix operator.
• "-" x:(@): A prefix operator.
• n:number(): An atom (no @).

Example structure:

precedence!{
  x:(@) "+" y:@ { x + y }
  --
  x:(@) "*" y:@ { x * y }
  --
  n:number() { n }
}

# peg::parser!{grammar doc() for str {
# pub rule number() -> i64 = "..." { 0 }
pub rule arithmetic() -> i64 = precedence!{
  x:(@) "+" y:@ { x + y }
  x:(@) "-" y:@ { x - y }
  --
  x:(@) "*" y:@ { x * y }
  x:(@) "/" y:@ { x / y }
  --
  x:(@) "^" y:(@) { x.pow(y as u32) }
  --
  n:number() { n }
  "(" e:arithmetic() ")" { e }
}
# }}
# fn main() {}

To improve performance for rules that are checked repeatedly at the same position, use the #[cache] attribute. This implements packrat parsing by memoizing results based on the input position.

If you need to handle left-recursive rules (which are normally an error in PEG), use the #[cache_left_rec] attribute.

To see a trace of which rules are being attempted and matched, enable the peg/trace feature when building your project:

$ cargo run --features peg/trace

This will print messages to stdout like [PEG_TRACE] Matched rule type at 8:5 or [PEG_TRACE] Attempting to match rule....

The peg::parser!{} macro is the primary way to define a parser. It uses a grammar NAME() for INPUT_TYPE { ... } syntax. Inside the grammar, you define rules using the format: rule NAME(PARAMETERS) -> RETURN_TYPE = PEG_EXPR.

When the macro expands, it creates a Rust module. For every rule marked pub, a corresponding function is generated. To parse input, call the generated function with the input data. The function returns a Result<T, ParseError>, where T is the return type of the rule.

peg::parser!{
  grammar list_parser() for str {
    rule number() -> u32
      = n:$([ '0'..='9' ]+) {? n.parse().or(Err("u32")) }

    pub rule list() -> Vec<u32>
      = "[" l:(number() ** ",") "]" { l }
  }
}

fn main() {
    assert_eq!(list_parser::list("[1,1,2,3,5,8]"), Ok(vec![1, 1, 2, 3, 5, 8]));
}

The inject name(input, lpos, rpos) -> Type { expr } syntax defines an internal function evaluated before entering action blocks. It provides access to the full input and the usize start (lpos) and end (rpos) positions of the matched sequence. The returned value is available in the action block as a variable named name.

This is useful for automatically attaching span information (like std::ops::Range<usize>) to AST nodes.

struct Identifier { span: std::ops::Range<usize>, name: String }

peg::parser!{grammar doc() for str {
  inject span(_input, lpos, rpos) -> std::ops::Range<usize> { lpos..rpos }

  rule identifier() -> Identifier
    = name:$([ 'a'..='z']+) { Identifier { span, name: name.to_owned() } }
}