Trait Pratt 

pub trait Pratt<'t, K: TokenKind> {
    type Output;

    // Required methods
    fn prefix(&mut self, parser: &mut Parser<'t, K>) -> Option<Self::Output>;
    fn infix_binding(&self, kind: &K) -> Option<(u8, u8)>;
    fn infix(
        &mut self,
        op: &'t Token<K>,
        left: Self::Output,
        right: Self::Output,
    ) -> Option<Self::Output>;

    // Provided methods
    fn expression(
        &mut self,
        parser: &mut Parser<'t, K>,
        min_bp: u8,
    ) -> Option<Self::Output> { ... }
    fn parse(&mut self, parser: &mut Parser<'t, K>) -> Option<Self::Output> { ... }
}

A precedence-climbing expression grammar, driven over a Parser.

Pratt parsing handles operator precedence and associativity without a separate grammar rule per level. You describe three things and the provided expression driver does the rest:

• prefix — parse an operand: a literal, a parenthesized expression, a prefix-unary operator and its operand. This is also where postfix forms (a call (), an index []) are handled, by looping on the trailing tokens after the atom.
• infix_binding — the binding power of a kind as an infix operator, as a (left, right) pair, or None if it is not one. A left power below the right ((1, 2)) is left-associative; above ((4, 3)) is right-associative.
• infix — combine a left operand, the operator token, and the right operand into one result.

The grammar returns None from any method to signal a recoverable error (after recording a diagnostic on the parser); the driver then unwinds with None.

Examples

A calculator that evaluates as it parses, so 1 + 2 * 3 is 7 — * binds tighter than +.

use parser_lang::{Parser, Pratt, Span, Token, TokenKind};

#[derive(Clone, Copy)]
enum K { Num(i64), Plus, Star, Eof }
impl TokenKind for K {
    fn is_eof(&self) -> bool { matches!(self, K::Eof) }
}

struct Calc;
impl<'t> Pratt<'t, K> for Calc {
    type Output = i64;
    fn prefix(&mut self, p: &mut Parser<'t, K>) -> Option<i64> {
        match p.bump()?.kind() {
            K::Num(n) => Some(*n),
            _ => None,
        }
    }
    fn infix_binding(&self, k: &K) -> Option<(u8, u8)> {
        match k {
            K::Plus => Some((1, 2)),
            K::Star => Some((3, 4)),
            _ => None,
        }
    }
    fn infix(&mut self, op: &'t Token<K>, left: i64, right: i64) -> Option<i64> {
        match op.kind() {
            K::Plus => Some(left + right),
            K::Star => Some(left * right),
            _ => None,
        }
    }
}

let s = |i| Span::new(i, i + 1);
let tokens = [
    Token::new(K::Num(1), s(0)),
    Token::new(K::Plus, s(1)),
    Token::new(K::Num(2), s(2)),
    Token::new(K::Star, s(3)),
    Token::new(K::Num(3), s(4)),
    Token::new(K::Eof, Span::empty(5)),
];
let mut p = Parser::new(&tokens);
let mut calc = Calc;
assert_eq!(calc.parse(&mut p), Some(7));

Required Associated Types

type Output

What the grammar builds — an AST node, a value, a string.

Required Methods

fn prefix(&mut self, parser: &mut Parser<'t, K>) -> Option<Self::Output>

Parses an operand at the cursor: a literal, a parenthesized group, or a prefix operator applied to a sub-expression (parsed by calling expression with the operator’s right binding power). Returns None after recording a diagnostic on a syntax error.

fn infix_binding(&self, kind: &K) -> Option<(u8, u8)>

Returns the (left, right) binding power of kind as an infix operator, or None if the kind does not begin an infix operator. Left below right is left-associative; left above right is right-associative.

fn infix( &mut self, op: &'t Token<K>, left: Self::Output, right: Self::Output, ) -> Option<Self::Output>

Combines left, the already-consumed operator token op, and right into one result. Returns None after recording a diagnostic on an error.

Provided Methods

fn expression( &mut self, parser: &mut Parser<'t, K>, min_bp: u8, ) -> Option<Self::Output>

Parses an expression whose operators all bind at least as tightly as min_bp — the precedence-climbing driver. Provided; do not override.

Parse a full expression with parse, which calls this with a minimum of 0. Call it directly with an operator’s right binding power from inside prefix to parse the operand of a prefix operator.

fn parse(&mut self, parser: &mut Parser<'t, K>) -> Option<Self::Output>

Parses a complete expression from the cursor (minimum binding power 0).

Dyn Compatibility

This trait is dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety".

Implementors