234 lines
7.2 KiB
Rust
234 lines
7.2 KiB
Rust
// pest. The Elegant Parser
|
|
// Copyright (c) 2018 Dragoș Tiselice
|
|
//
|
|
// Licensed under the Apache License, Version 2.0
|
|
// <LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0> or the MIT
|
|
// license <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
|
|
// option. All files in the project carrying such notice may not be copied,
|
|
// modified, or distributed except according to those terms.
|
|
|
|
//! Constructs useful in infix operator parsing with the precedence climbing method.
|
|
|
|
use std::collections::HashMap;
|
|
use std::iter::Peekable;
|
|
use std::ops::BitOr;
|
|
|
|
use iterators::Pair;
|
|
use RuleType;
|
|
|
|
/// Associativity of an [`Operator`].
|
|
///
|
|
/// [`Operator`]: struct.Operator.html
|
|
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
|
|
pub enum Assoc {
|
|
/// Left `Operator` associativity
|
|
Left,
|
|
/// Right `Operator` associativity
|
|
Right,
|
|
}
|
|
|
|
/// Infix operator used in [`PrecClimber`].
|
|
///
|
|
/// [`PrecClimber`]: struct.PrecClimber.html
|
|
#[derive(Debug)]
|
|
pub struct Operator<R: RuleType> {
|
|
rule: R,
|
|
assoc: Assoc,
|
|
next: Option<Box<Operator<R>>>,
|
|
}
|
|
|
|
impl<R: RuleType> Operator<R> {
|
|
/// Creates a new `Operator` from a `Rule` and `Assoc`.
|
|
///
|
|
/// # Examples
|
|
///
|
|
/// ```
|
|
/// # use pest::prec_climber::{Assoc, Operator};
|
|
/// # #[allow(non_camel_case_types)]
|
|
/// # #[allow(dead_code)]
|
|
/// # #[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
|
|
/// # enum Rule {
|
|
/// # plus,
|
|
/// # minus
|
|
/// # }
|
|
/// Operator::new(Rule::plus, Assoc::Left) | Operator::new(Rule::minus, Assoc::Right);
|
|
/// ```
|
|
pub fn new(rule: R, assoc: Assoc) -> Operator<R> {
|
|
Operator {
|
|
rule,
|
|
assoc,
|
|
next: None,
|
|
}
|
|
}
|
|
}
|
|
|
|
impl<R: RuleType> BitOr for Operator<R> {
|
|
type Output = Self;
|
|
|
|
fn bitor(mut self, rhs: Self) -> Self {
|
|
fn assign_next<R: RuleType>(op: &mut Operator<R>, next: Operator<R>) {
|
|
if let Some(ref mut child) = op.next {
|
|
assign_next(child, next);
|
|
} else {
|
|
op.next = Some(Box::new(next));
|
|
}
|
|
}
|
|
|
|
assign_next(&mut self, rhs);
|
|
self
|
|
}
|
|
}
|
|
|
|
/// List of operators and precedences, which can perform [precedence climbing][1] on infix
|
|
/// expressions contained in a [`Pairs`]. The token pairs contained in the `Pairs` should start
|
|
/// with a *primary* pair and then alternate between an *operator* and a *primary*.
|
|
///
|
|
/// [1]: https://en.wikipedia.org/wiki/Operator-precedence_parser#Precedence_climbing_method
|
|
/// [`Pairs`]: ../iterators/struct.Pairs.html
|
|
#[derive(Debug)]
|
|
pub struct PrecClimber<R: RuleType> {
|
|
ops: HashMap<R, (u32, Assoc)>,
|
|
}
|
|
|
|
impl<R: RuleType> PrecClimber<R> {
|
|
/// Creates a new `PrecClimber` from the `Operator`s contained in `ops`. Every entry in the
|
|
/// `Vec` has precedence *index + 1*. In order to have operators with same precedence, they need
|
|
/// to be chained with `|` between them.
|
|
///
|
|
/// # Examples
|
|
///
|
|
/// ```
|
|
/// # use pest::prec_climber::{Assoc, Operator, PrecClimber};
|
|
/// # #[allow(non_camel_case_types)]
|
|
/// # #[allow(dead_code)]
|
|
/// # #[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
|
|
/// # enum Rule {
|
|
/// # plus,
|
|
/// # minus,
|
|
/// # times,
|
|
/// # divide,
|
|
/// # power
|
|
/// # }
|
|
/// PrecClimber::new(vec![
|
|
/// Operator::new(Rule::plus, Assoc::Left) | Operator::new(Rule::minus, Assoc::Left),
|
|
/// Operator::new(Rule::times, Assoc::Left) | Operator::new(Rule::divide, Assoc::Left),
|
|
/// Operator::new(Rule::power, Assoc::Right)
|
|
/// ]);
|
|
/// ```
|
|
pub fn new(ops: Vec<Operator<R>>) -> PrecClimber<R> {
|
|
let ops = ops
|
|
.into_iter()
|
|
.zip(1..)
|
|
.fold(HashMap::new(), |mut map, (op, prec)| {
|
|
let mut next = Some(op);
|
|
|
|
while let Some(op) = next.take() {
|
|
match op {
|
|
Operator {
|
|
rule,
|
|
assoc,
|
|
next: op_next,
|
|
} => {
|
|
map.insert(rule, (prec, assoc));
|
|
next = op_next.map(|op| *op);
|
|
}
|
|
}
|
|
}
|
|
|
|
map
|
|
});
|
|
|
|
PrecClimber { ops }
|
|
}
|
|
|
|
/// Performs the precedence climbing algorithm on the `pairs` in a similar manner to map-reduce.
|
|
/// *Primary* pairs are mapped with `primary` and then reduced to one single result with
|
|
/// `infix`.
|
|
///
|
|
/// # Panics
|
|
///
|
|
/// Panics will occur when `pairs` is empty or when the alternating *primary*, *operator*,
|
|
/// *primary* order is not respected.
|
|
///
|
|
/// # Examples
|
|
///
|
|
/// ```ignore
|
|
/// let primary = |pair| {
|
|
/// consume(pair, climber)
|
|
/// };
|
|
/// let infix = |lhs: i32, op: Pair<Rule>, rhs: i32| {
|
|
/// match op.rule() {
|
|
/// Rule::plus => lhs + rhs,
|
|
/// Rule::minus => lhs - rhs,
|
|
/// Rule::times => lhs * rhs,
|
|
/// Rule::divide => lhs / rhs,
|
|
/// Rule::power => lhs.pow(rhs as u32),
|
|
/// _ => unreachable!()
|
|
/// }
|
|
/// };
|
|
///
|
|
/// let result = climber.climb(pairs, primary, infix);
|
|
/// ```
|
|
pub fn climb<'i, P, F, G, T>(&self, mut pairs: P, mut primary: F, mut infix: G) -> T
|
|
where
|
|
P: Iterator<Item = Pair<'i, R>>,
|
|
F: FnMut(Pair<'i, R>) -> T,
|
|
G: FnMut(T, Pair<'i, R>, T) -> T,
|
|
{
|
|
let lhs = primary(
|
|
pairs
|
|
.next()
|
|
.expect("precedence climbing requires a non-empty Pairs"),
|
|
);
|
|
self.climb_rec(lhs, 0, &mut pairs.peekable(), &mut primary, &mut infix)
|
|
}
|
|
|
|
fn climb_rec<'i, P, F, G, T>(
|
|
&self,
|
|
mut lhs: T,
|
|
min_prec: u32,
|
|
pairs: &mut Peekable<P>,
|
|
primary: &mut F,
|
|
infix: &mut G,
|
|
) -> T
|
|
where
|
|
P: Iterator<Item = Pair<'i, R>>,
|
|
F: FnMut(Pair<'i, R>) -> T,
|
|
G: FnMut(T, Pair<'i, R>, T) -> T,
|
|
{
|
|
while pairs.peek().is_some() {
|
|
let rule = pairs.peek().unwrap().as_rule();
|
|
if let Some(&(prec, _)) = self.ops.get(&rule) {
|
|
if prec >= min_prec {
|
|
let op = pairs.next().unwrap();
|
|
let mut rhs = primary(pairs.next().expect(
|
|
"infix operator must be followed by \
|
|
a primary expression",
|
|
));
|
|
|
|
while pairs.peek().is_some() {
|
|
let rule = pairs.peek().unwrap().as_rule();
|
|
if let Some(&(new_prec, assoc)) = self.ops.get(&rule) {
|
|
if new_prec > prec || assoc == Assoc::Right && new_prec == prec {
|
|
rhs = self.climb_rec(rhs, new_prec, pairs, primary, infix);
|
|
} else {
|
|
break;
|
|
}
|
|
} else {
|
|
break;
|
|
}
|
|
}
|
|
|
|
lhs = infix(lhs, op, rhs);
|
|
} else {
|
|
break;
|
|
}
|
|
} else {
|
|
break;
|
|
}
|
|
}
|
|
|
|
lhs
|
|
}
|
|
}
|