pest::pratt_parser

Struct PrattParser

Source
pub struct PrattParser<R: RuleType> { /* private fields */ }
Expand description

Struct containing operators and precedences, which can perform Pratt parsing on primary, prefix, postfix and infix expressions over Pairs. The tokens in Pairs should alternate in the order: prefix* ~ primary ~ postfix* ~ (infix ~ prefix* ~ primary ~ postfix*)*

§Panics

Panics will occur when:

  • pairs is empty
  • The tokens in pairs does not alternate in the expected order.
  • No map_* function is specified for a certain kind of operator encountered in pairs.

§Example

The following pest grammar defines a calculator which can be used for Pratt parsing.

WHITESPACE   =  _{ " " | "\t" | NEWLINE }
  
program      =   { SOI ~ expr ~ EOI }
  expr       =   { prefix* ~ primary ~ postfix* ~ (infix ~ prefix* ~ primary ~ postfix* )* }
    infix    =  _{ add | sub | mul | div | pow }
      add    =   { "+" } // Addition
      sub    =   { "-" } // Subtraction
      mul    =   { "*" } // Multiplication
      div    =   { "/" } // Division
      pow    =   { "^" } // Exponentiation
    prefix   =  _{ neg }
      neg    =   { "-" } // Negation
    postfix  =  _{ fac }
      fac    =   { "!" } // Factorial
    primary  =  _{ int | "(" ~ expr ~ ")" }
      int    =  @{ (ASCII_NONZERO_DIGIT ~ ASCII_DIGIT+ | ASCII_DIGIT) }

Below is a PrattParser that is able to parse an expr in the above grammar. The order of precedence corresponds to the order in which op is called. Thus, mul will have higher precedence than add. Operators can also be chained with | to give them equal precedence.

let pratt =
    PrattParser::new()
        .op(Op::infix(Rule::add, Assoc::Left) | Op::infix(Rule::sub, Assoc::Left))
        .op(Op::infix(Rule::mul, Assoc::Left) | Op::infix(Rule::div, Assoc::Left))
        .op(Op::infix(Rule::pow, Assoc::Right))
        .op(Op::prefix(Rule::neg))
        .op(Op::postfix(Rule::fac));

To parse an expression, call the map_primary, map_prefix, map_postfix, map_infix and parse methods as follows:

fn parse_expr(pairs: Pairs<Rule>, pratt: &PrattParser<Rule>) -> i32 {
    pratt
        .map_primary(|primary| match primary.as_rule() {
            Rule::int  => primary.as_str().parse().unwrap(),
            Rule::expr => parse_expr(primary.into_inner(), pratt), // from "(" ~ expr ~ ")"
            _          => unreachable!(),
        })
        .map_prefix(|op, rhs| match op.as_rule() {
            Rule::neg  => -rhs,
            _          => unreachable!(),
        })
        .map_postfix(|lhs, op| match op.as_rule() {
            Rule::fac  => (1..lhs+1).product(),
            _          => unreachable!(),
        })
        .map_infix(|lhs, op, rhs| match op.as_rule() {
            Rule::add  => lhs + rhs,
            Rule::sub  => lhs - rhs,
            Rule::mul  => lhs * rhs,
            Rule::div  => lhs / rhs,
            Rule::pow  => (1..rhs+1).map(|_| lhs).product(),
            _          => unreachable!(),
        })
        .parse(pairs)
}

Note that map_prefix, map_postfix and map_infix only need to be specified if the grammar contains the corresponding operators.

Implementations§

Source§

impl<R: RuleType> PrattParser<R>

Source

pub fn new() -> Self

Instantiate a new PrattParser.

Source

pub fn op(self, op: Op<R>) -> Self

Add op to PrattParser.

Source

pub fn map_primary<'pratt, 'a, 'i, X, T>( &'pratt self, primary: X, ) -> PrattParserMap<'pratt, 'a, 'i, R, X, T>
where X: FnMut(Pair<'i, R>) -> T, R: 'pratt,

Maps primary expressions with a closure primary.

Trait Implementations§

Source§

impl<R: RuleType> Default for PrattParser<R>

Source§

fn default() -> Self

Returns the “default value” for a type. Read more

Auto Trait Implementations§

§

impl<R> Freeze for PrattParser<R>

§

impl<R> RefUnwindSafe for PrattParser<R>
where R: RefUnwindSafe,

§

impl<R> Send for PrattParser<R>
where R: Send,

§

impl<R> Sync for PrattParser<R>
where R: Sync,

§

impl<R> Unpin for PrattParser<R>

§

impl<R> UnwindSafe for PrattParser<R>
where R: RefUnwindSafe,

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.