pest/
pratt_parser.rs

1// pest. The Elegant Parser
2// Copyright (c) 2018 Dragoș Tiselice
3//
4// Licensed under the Apache License, Version 2.0
5// <LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0> or the MIT
6// license <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
7// option. All files in the project carrying such notice may not be copied,
8// modified, or distributed except according to those terms.
9
10//! Constructs useful in prefix, postfix, and infix operator parsing with the
11//! Pratt parsing method.
12
13use core::iter::Peekable;
14use core::marker::PhantomData;
15use core::mem::ManuallyDrop;
16use core::ops::BitOr;
17
18use alloc::boxed::Box;
19use alloc::collections::BTreeMap;
20
21use crate::iterators::Pair;
22use crate::RuleType;
23
24pub use crate::pratt_precedence;
25
26/// Associativity of an infix binary operator, used by [`Op::infix(Assoc)`].
27///
28/// [`Op::infix(Assoc)`]: struct.Op.html
29#[derive(Clone, Copy, Debug, Eq, PartialEq)]
30pub enum Assoc {
31    /// Left operator associativity. Evaluate expressions from left-to-right.
32    Left,
33    /// Right operator associativity. Evaluate expressions from right-to-left.
34    Right,
35}
36
37/// Operator precedence level.
38pub type Prec = u32;
39const PREC_STEP: Prec = 10;
40
41/// An operator that corresponds to a rule.
42pub struct Op<R: RuleType> {
43    rule: R,
44    affix: Affix,
45    next: Option<Box<Op<R>>>,
46}
47
48/// The position of an operator relative to its operand.
49///
50/// This is an implementation detail used by the Pratt parser internals.
51#[doc(hidden)]
52#[derive(Clone, Copy, Debug, Eq, PartialEq)]
53pub enum Affix {
54    /// Prefix operator, appearing before its operand.
55    Prefix,
56    /// Postfix operator, appearing after its operand.
57    Postfix,
58    /// Infix binary operator with the given associativity.
59    Infix(Assoc),
60}
61
62impl<R: RuleType> Op<R> {
63    /// Defines `rule` as a prefix unary operator.
64    pub const fn prefix(rule: R) -> Self {
65        Self {
66            rule,
67            affix: Affix::Prefix,
68            next: None,
69        }
70    }
71
72    /// Defines `rule` as a postfix unary operator.
73    pub const fn postfix(rule: R) -> Self {
74        Self {
75            rule,
76            affix: Affix::Postfix,
77            next: None,
78        }
79    }
80
81    /// Defines `rule` as an infix binary operator with associativity `assoc`.
82    pub const fn infix(rule: R, assoc: Assoc) -> Self {
83        Self {
84            rule,
85            affix: Affix::Infix(assoc),
86            next: None,
87        }
88    }
89}
90
91impl<R: RuleType> BitOr for Op<R> {
92    type Output = Self;
93
94    fn bitor(mut self, rhs: Self) -> Self {
95        fn assign_next<R: RuleType>(op: &mut Op<R>, next: Op<R>) {
96            if let Some(ref mut child) = op.next {
97                assign_next(child, next);
98            } else {
99                op.next = Some(Box::new(next));
100            }
101        }
102
103        assign_next(&mut self, rhs);
104        self
105    }
106}
107
108/// Struct containing operators and precedences, which can perform [Pratt parsing][1] on
109/// primary, prefix, postfix and infix expressions over [`Pairs`]. The tokens in [`Pairs`]
110/// should alternate in the order:
111/// `prefix* ~ primary ~ postfix* ~ (infix ~ prefix* ~ primary ~ postfix*)*`
112///
113/// # Panics
114///
115/// Panics will occur when:
116/// * `pairs` is empty
117/// * The tokens in `pairs` does not alternate in the expected order.
118/// * No `map_*` function is specified for a certain kind of operator encountered in `pairs`.
119///
120/// # Example
121///
122/// The following pest grammar defines a calculator which can be used for Pratt parsing.
123///
124/// ```pest
125/// WHITESPACE   =  _{ " " | "\t" | NEWLINE }
126///
127/// program      =   { SOI ~ expr ~ EOI }
128///   expr       =   { prefix* ~ primary ~ postfix* ~ (infix ~ prefix* ~ primary ~ postfix* )* }
129///     infix    =  _{ add | sub | mul | div | pow }
130///       add    =   { "+" } // Addition
131///       sub    =   { "-" } // Subtraction
132///       mul    =   { "*" } // Multiplication
133///       div    =   { "/" } // Division
134///       pow    =   { "^" } // Exponentiation
135///     prefix   =  _{ neg }
136///       neg    =   { "-" } // Negation
137///     postfix  =  _{ fac }
138///       fac    =   { "!" } // Factorial
139///     primary  =  _{ int | "(" ~ expr ~ ")" }
140///       int    =  @{ (ASCII_NONZERO_DIGIT ~ ASCII_DIGIT+ | ASCII_DIGIT) }
141/// ```
142///
143/// Below is a [`PrattParser`] that is able to parse an `expr` in the above grammar. The order
144/// of precedence corresponds to the order in which [`op`] is called. Thus, `mul` will
145/// have higher precedence than `add`. Operators can also be chained with `|` to give them equal
146/// precedence.
147///
148/// ```
149/// # use pest::pratt_parser::{Assoc, Op, PrattParser};
150/// # #[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
151/// # enum Rule { program, expr, int, add, mul, sub, div, pow, fac, neg }
152/// let pratt =
153///     PrattParser::new()
154///         .op(Op::infix(Rule::add, Assoc::Left) | Op::infix(Rule::sub, Assoc::Left))
155///         .op(Op::infix(Rule::mul, Assoc::Left) | Op::infix(Rule::div, Assoc::Left))
156///         .op(Op::infix(Rule::pow, Assoc::Right))
157///         .op(Op::prefix(Rule::neg))
158///         .op(Op::postfix(Rule::fac));
159/// ```
160///
161/// To parse an expression, call the [`map_primary`], [`map_prefix`], [`map_postfix`],
162/// [`map_infix`] and [`parse`] methods as follows:
163///
164/// ```
165/// # use pest::{iterators::Pairs, pratt_parser::PrattParser};
166/// # #[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
167/// # enum Rule { program, expr, int, add, mul, sub, div, pow, fac, neg }
168/// fn parse_expr(pairs: Pairs<Rule>, pratt: &PrattParser<Rule>) -> i32 {
169///     pratt
170///         .map_primary(|primary| match primary.as_rule() {
171///             Rule::int  => primary.as_str().parse().unwrap(),
172///             Rule::expr => parse_expr(primary.into_inner(), pratt), // from "(" ~ expr ~ ")"
173///             _          => unreachable!(),
174///         })
175///         .map_prefix(|op, rhs| match op.as_rule() {
176///             Rule::neg  => -rhs,
177///             _          => unreachable!(),
178///         })
179///         .map_postfix(|lhs, op| match op.as_rule() {
180///             Rule::fac  => (1..lhs+1).product(),
181///             _          => unreachable!(),
182///         })
183///         .map_infix(|lhs, op, rhs| match op.as_rule() {
184///             Rule::add  => lhs + rhs,
185///             Rule::sub  => lhs - rhs,
186///             Rule::mul  => lhs * rhs,
187///             Rule::div  => lhs / rhs,
188///             Rule::pow  => (1..rhs+1).map(|_| lhs).product(),
189///             _          => unreachable!(),
190///         })
191///         .parse(pairs)
192/// }
193/// ```
194///
195/// Note that [`map_prefix`], [`map_postfix`] and [`map_infix`] only need to be specified if the
196/// grammar contains the corresponding operators.
197///
198/// [1]: https://en.wikipedia.org/wiki/Pratt_parser
199/// [`Pairs`]: ../iterators/struct.Pairs.html
200/// [`PrattParser`]: struct.PrattParser.html
201/// [`map_primary`]: struct.PrattParser.html#method.map_primary
202/// [`map_prefix`]: struct.PrattParserMap.html#method.map_prefix
203/// [`map_postfix`]: struct.PrattParserMap.html#method.map_postfix
204/// [`map_infix`]: struct.PrattParserMap.html#method.map_infix
205/// [`parse`]: struct.PrattParserMap.html#method.parse
206/// [`op`]: struct.PrattParserMap.html#method.op
207pub struct PrattParser<R: RuleType> {
208    prec: Prec,
209    ops: BTreeMap<R, (Affix, Prec)>,
210    has_prefix: bool,
211    has_postfix: bool,
212    has_infix: bool,
213}
214
215impl<R: RuleType> Default for PrattParser<R> {
216    fn default() -> Self {
217        Self::new()
218    }
219}
220
221impl<R: RuleType> PrattParser<R> {
222    /// Instantiate a new `PrattParser`.
223    pub fn new() -> Self {
224        Self {
225            prec: PREC_STEP,
226            ops: BTreeMap::new(),
227            has_prefix: false,
228            has_postfix: false,
229            has_infix: false,
230        }
231    }
232
233    /// Add `op` to `PrattParser`.
234    pub fn op(mut self, op: Op<R>) -> Self {
235        self.prec += PREC_STEP;
236        let mut iter = Some(op);
237        while let Some(Op { rule, affix, next }) = iter.take() {
238            match affix {
239                Affix::Prefix => self.has_prefix = true,
240                Affix::Postfix => self.has_postfix = true,
241                Affix::Infix(_) => self.has_infix = true,
242            }
243            self.ops.insert(rule, (affix, self.prec));
244            iter = next.map(|op| *op);
245        }
246        self
247    }
248
249    /// Maps primary expressions with a closure `primary`.
250    pub fn map_primary<'pratt, 'a, 'i, X, T>(
251        &'pratt self,
252        primary: X,
253    ) -> PrattParserMap<'pratt, 'a, 'i, R, X, T>
254    where
255        X: FnMut(Pair<'i, R>) -> T,
256        R: 'pratt,
257    {
258        PrattParserMap {
259            pratt: self,
260            primary,
261            prefix: None,
262            postfix: None,
263            infix: None,
264            phantom: PhantomData,
265        }
266    }
267
268    fn get(&self, rule: &R) -> Option<(Affix, Prec)> {
269        self.ops.get(rule).copied()
270    }
271}
272
273/// Internal trait for types that provide operator metadata to [`PrattParserMap`].
274///
275/// This trait is an implementation detail and not intended to be implemented
276/// by downstream code.
277///
278/// [`PrattParserMap`]: struct.PrattParserMap.html
279#[doc(hidden)]
280pub trait PrattParserOps<R: RuleType> {
281    /// Look up the affix and precedence of `rule`.
282    fn get(&self, rule: &R) -> Option<(Affix, Prec)>;
283}
284
285impl<R: RuleType> PrattParserOps<R> for PrattParser<R> {
286    fn get(&self, rule: &R) -> Option<(Affix, Prec)> {
287        PrattParser::get(self, rule)
288    }
289}
290
291/// A Pratt parser that can be built in a `const` context and stored in static
292/// memory.
293///
294/// It is functionally equivalent to [`PrattParser`], but it is constructed from
295/// a static array of [`Op`]s rather than the chained `.op(...)` builder.
296///
297/// [`PrattParser`]: struct.PrattParser.html
298pub struct ConstPrattParser<R: RuleType + 'static, const N: usize> {
299    ops: [(R, Affix, Prec); N],
300}
301
302impl<R: RuleType + 'static, const N: usize> ConstPrattParser<R, N> {
303    /// Create a `ConstPrattParser` from a static array of (`[`Op`]`, `bool`)
304    /// pairs.
305    ///
306    /// Just like [`PrattParser::op`], but for use in a `const` context. The
307    /// `bool` in each pair tells whether the operator starts a new precedence
308    /// level (`true`) or shares the previous operator's level (`false`).
309    /// Levels are ordered from lowest to highest precedence; the first
310    /// operator must start a new level (`true`).
311    ///
312    /// # Example
313    ///
314    /// ```
315    /// # use pest::pratt_parser::{Assoc, ConstPrattParser, Op};
316    /// # #[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
317    /// # enum Rule { expr, int, add, sub, mul, div, pow, neg, fac }
318    /// static PRATT: ConstPrattParser<Rule, 7> = ConstPrattParser::new_const([
319    ///     (Op::infix(Rule::add, Assoc::Left), true), // lowest precedence
320    ///     (Op::infix(Rule::sub, Assoc::Left), false), // same precedence as add
321    ///     (Op::infix(Rule::mul, Assoc::Left), true), // next precedence level
322    ///     (Op::infix(Rule::div, Assoc::Left), false), // same precedence as mul
323    ///     (Op::infix(Rule::pow, Assoc::Right), true),
324    ///     (Op::prefix(Rule::neg), true),
325    ///     (Op::postfix(Rule::fac), true), // highest precedence
326    /// ]);
327    /// ```
328    pub const fn new_const(ops: [(Op<R>, bool); N]) -> Self {
329        const {
330            assert!(N > 0, "ConstPrattParser requires at least one operator");
331        }
332        assert!(
333            ops[0].1,
334            "the first operator must start a new precedence level (`true`)"
335        );
336
337        // The initial values are dummies; every entry is overwritten below.
338        let mut internal_ops: [(R, Affix, Prec); N] = [(ops[0].0.rule, Affix::Prefix, 0); N];
339        let mut prec = 0;
340        let mut index = 0;
341        while index < N {
342            let (op, new_level) = &ops[index];
343            assert!(
344                op.next.is_none(),
345                "chained operators (created with `|`) are not supported in ConstPrattParser"
346            );
347            if *new_level {
348                prec += PREC_STEP;
349            }
350            internal_ops[index] = (op.rule, op.affix, prec);
351            index += 1;
352        }
353        let _ = ManuallyDrop::new(ops);
354        Self { ops: internal_ops }
355    }
356
357    /// Maps primary expressions with a closure `primary`.
358    pub fn map_primary<'pratt, 'a, 'i, X, T>(
359        &'pratt self,
360        primary: X,
361    ) -> PrattParserMap<'pratt, 'a, 'i, R, X, T, Self>
362    where
363        X: FnMut(Pair<'i, R>) -> T,
364        R: 'pratt,
365    {
366        PrattParserMap {
367            pratt: self,
368            primary,
369            prefix: None,
370            postfix: None,
371            infix: None,
372            phantom: PhantomData,
373        }
374    }
375
376    #[inline]
377    fn get(&self, rule: &R) -> Option<(Affix, Prec)> {
378        let mut i = N;
379        while i > 0 {
380            i -= 1;
381            if self.ops[i].0 == *rule {
382                return Some((self.ops[i].1, self.ops[i].2));
383            }
384        }
385        None
386    }
387}
388
389impl<R: RuleType + 'static, const N: usize> PrattParserOps<R> for ConstPrattParser<R, N> {
390    fn get(&self, rule: &R) -> Option<(Affix, Prec)> {
391        ConstPrattParser::get(self, rule)
392    }
393}
394
395type PrefixFn<'a, 'i, R, T> = Box<dyn FnMut(Pair<'i, R>, T) -> T + 'a>;
396type PostfixFn<'a, 'i, R, T> = Box<dyn FnMut(T, Pair<'i, R>) -> T + 'a>;
397type InfixFn<'a, 'i, R, T> = Box<dyn FnMut(T, Pair<'i, R>, T) -> T + 'a>;
398
399/// Product of calling [`map_primary`] on a [`PrattParser`] or [`ConstPrattParser`],
400/// defines how expressions should be mapped.
401///
402/// [`map_primary`]: struct.PrattParser.html#method.map_primary
403/// [`PrattParser`]: struct.PrattParser.html
404/// [`ConstPrattParser`]: struct.ConstPrattParser.html
405pub struct PrattParserMap<'pratt, 'a, 'i, R, F, T, P = PrattParser<R>>
406where
407    R: RuleType,
408    F: FnMut(Pair<'i, R>) -> T,
409    P: PrattParserOps<R>,
410{
411    pratt: &'pratt P,
412    primary: F,
413    prefix: Option<PrefixFn<'a, 'i, R, T>>,
414    postfix: Option<PostfixFn<'a, 'i, R, T>>,
415    infix: Option<InfixFn<'a, 'i, R, T>>,
416    phantom: PhantomData<T>,
417}
418
419impl<'pratt, 'a, 'i, R, F, T, P> PrattParserMap<'pratt, 'a, 'i, R, F, T, P>
420where
421    R: RuleType + 'pratt,
422    F: FnMut(Pair<'i, R>) -> T,
423    P: PrattParserOps<R> + 'pratt,
424{
425    /// Maps prefix operators with closure `prefix`.
426    pub fn map_prefix<X>(mut self, prefix: X) -> Self
427    where
428        X: FnMut(Pair<'i, R>, T) -> T + 'a,
429    {
430        self.prefix = Some(Box::new(prefix));
431        self
432    }
433
434    /// Maps postfix operators with closure `postfix`.
435    pub fn map_postfix<X>(mut self, postfix: X) -> Self
436    where
437        X: FnMut(T, Pair<'i, R>) -> T + 'a,
438    {
439        self.postfix = Some(Box::new(postfix));
440        self
441    }
442
443    /// Maps infix operators with a closure `infix`.
444    pub fn map_infix<X>(mut self, infix: X) -> Self
445    where
446        X: FnMut(T, Pair<'i, R>, T) -> T + 'a,
447    {
448        self.infix = Some(Box::new(infix));
449        self
450    }
451
452    /// The last method to call on the provided pairs to execute the Pratt
453    /// parser (previously defined using [`map_primary`], [`map_prefix`], [`map_postfix`],
454    /// and [`map_infix`] methods).
455    ///
456    /// # Panics
457    ///
458    /// Panics if the input pairs contain a prefix operator with no [`map_prefix`],
459    /// an infix operator with no [`map_infix`], a postfix operator with no [`map_postfix`],
460    /// or an unexpected token that is not a valid prefix, primary, infix, or postfix expression.
461    ///
462    /// [`map_primary`]: struct.PrattParser.html#method.map_primary
463    /// [`map_prefix`]: struct.PrattParserMap.html#method.map_prefix
464    /// [`map_postfix`]: struct.PrattParserMap.html#method.map_postfix
465    /// [`map_infix`]: struct.PrattParserMap.html#method.map_infix
466    pub fn parse<I: Iterator<Item = Pair<'i, R>>>(&mut self, pairs: I) -> T {
467        self.expr(&mut pairs.peekable(), 0)
468    }
469
470    fn expr<I: Iterator<Item = Pair<'i, R>>>(&mut self, pairs: &mut Peekable<I>, rbp: Prec) -> T {
471        let mut lhs = self.nud(pairs);
472        while rbp < self.lbp(pairs) {
473            lhs = self.led(pairs, lhs);
474        }
475        lhs
476    }
477
478    /// Null-Denotation
479    ///
480    /// "the action that should happen when the symbol is encountered
481    ///  as start of an expression (most notably, prefix operators)
482    fn nud<I: Iterator<Item = Pair<'i, R>>>(&mut self, pairs: &mut Peekable<I>) -> T {
483        let pair = pairs.next().expect("Pratt parsing expects non-empty Pairs");
484        match self.pratt.get(&pair.as_rule()) {
485            Some((Affix::Prefix, prec)) => {
486                let rhs = self.expr(pairs, prec - 1);
487                match self.prefix.as_mut() {
488                    Some(prefix) => prefix(pair, rhs),
489                    None => panic!("Could not map {}, no `.map_prefix(...)` specified", pair),
490                }
491            }
492            None => (self.primary)(pair),
493            _ => panic!("Expected prefix or primary expression, found {}", pair),
494        }
495    }
496
497    /// Left-Denotation
498    ///
499    /// "the action that should happen when the symbol is encountered
500    /// after the start of an expression (most notably, infix and postfix operators)"
501    fn led<I: Iterator<Item = Pair<'i, R>>>(&mut self, pairs: &mut Peekable<I>, lhs: T) -> T {
502        let pair = pairs.next().unwrap();
503        match self.pratt.get(&pair.as_rule()) {
504            Some((Affix::Infix(assoc), prec)) => {
505                let rhs = match assoc {
506                    Assoc::Left => self.expr(pairs, prec),
507                    Assoc::Right => self.expr(pairs, prec - 1),
508                };
509                match self.infix.as_mut() {
510                    Some(infix) => infix(lhs, pair, rhs),
511                    None => panic!("Could not map {}, no `.map_infix(...)` specified", pair),
512                }
513            }
514            Some((Affix::Postfix, _)) => match self.postfix.as_mut() {
515                Some(postfix) => postfix(lhs, pair),
516                None => panic!("Could not map {}, no `.map_postfix(...)` specified", pair),
517            },
518            _ => panic!("Expected postfix or infix expression, found {}", pair),
519        }
520    }
521
522    /// Left-Binding-Power
523    ///
524    /// "describes the symbol's precedence in infix form (most notably, operator precedence)"
525    fn lbp<I: Iterator<Item = Pair<'i, R>>>(&mut self, pairs: &mut Peekable<I>) -> Prec {
526        match pairs.peek() {
527            Some(pair) => match self.pratt.get(&pair.as_rule()) {
528                Some((_, prec)) => prec,
529                None => panic!("Expected operator, found {}", pair),
530            },
531            None => 0,
532        }
533    }
534}
535
536/// Convenience macro for building a const Pratt parser precedence table.
537///
538/// Each argument is a precedence level: a list of [`Op`] constructors sharing
539/// the same precedence, separated by `|`. Levels are separated by `,`; later
540/// levels bind more tightly than earlier ones.
541///
542/// Each operator must be written as a two-segment call, for example
543/// `Op::infix(Rule::add, Assoc::Left)`. Fully qualified paths and turbofish
544/// forms are not accepted, because a macro matcher cannot follow an
545/// expression fragment with `|`. Import `Op` and use the short form.
546///
547/// # Example
548///
549/// ```
550/// # use pest::pratt_parser::{Assoc, ConstPrattParser, Op, pratt_precedence};
551/// # #[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
552/// # enum Rule { expr, int, add, sub, mul, div, pow, neg, fac }
553/// static PRATT: ConstPrattParser<Rule, 7> = ConstPrattParser::new_const(pratt_precedence![
554///     Op::infix(Rule::add, Assoc::Left) | Op::infix(Rule::sub, Assoc::Left),
555///     Op::infix(Rule::mul, Assoc::Left) | Op::infix(Rule::div, Assoc::Left),
556///     Op::infix(Rule::pow, Assoc::Right),
557///     Op::prefix(Rule::neg),
558///     Op::postfix(Rule::fac),
559/// ]);
560/// ```
561///
562/// Fully qualified paths are rejected with a compile error:
563///
564/// ```compile_fail
565/// # use pest::pratt_parser::{Assoc, ConstPrattParser, pratt_precedence};
566/// # #[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
567/// # enum Rule { expr, int, add, sub }
568/// static PRATT: ConstPrattParser<Rule, 2> = ConstPrattParser::new_const(pratt_precedence![
569///     pest::pratt_parser::Op::infix(Rule::add, Assoc::Left)
570///         | pest::pratt_parser::Op::infix(Rule::sub, Assoc::Left),
571/// ]);
572/// ```
573#[macro_export]
574macro_rules! pratt_precedence {
575    // Operators must use a two-segment path: `Op::infix(args)`.
576    (
577        $(
578            $first_head:ident :: $first_tail:ident $first_args:tt
579            $( | $head:ident :: $tail:ident $args:tt )*
580        ),* $(,)?
581    ) => {
582        [$(
583            ( $first_head :: $first_tail $first_args, true )
584            $(, ( $head :: $tail $args, false ) )*
585        ),*]
586    };
587    ($($t:tt)*) => {
588        compile_error!(
589            "unsupported operator syntax in `pratt_precedence!`: \
590             each operator must be a two-segment call like `Op::infix(Rule::add, Assoc::Left)`; \
591             fully qualified paths and turbofish forms are not accepted"
592        )
593    };
594}
pest/pratt_parser.rs

pest/
pratt_parser.rs
