parcours 0.3.0

Parser Combinators for Unique Results
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

//! Precedence climbing for parsing expressions with binary operators.
//!
//! This allows you to parse expressions that are
//! separated by binary operators with precedence and associativity.
//! For example, in the expression `1 + 2 * 3`, we usually want to
//! parse this into `1 + (2 * 3)`, not `(1 + 2) * 3`.
//! This is handled by saying that `*` has higher *precedence* than `+`.
//! Also, when we have a power operator `^`, we want
//! `2 ^ 3 ^ 4` to mean `(2 ^ 3) ^ 4`, not `2 ^ (3 ^ 4)`.
//! This is handled by saying that `^` is *left-associative*.
//!
//! This was adapted from
//! <https://ycpcs.github.io/cs340-fall2017/lectures/lecture06.html#implementation>.
//!
//! An example for simple arithmetic expressions follows:
//!
//! ~~~
//! use parcours::prec_climb::{self, Associativity};
//!
//! enum Op {
//!     Add,
//!     Sub,
//!     Mul,
//!     Div,
//! }
//!
//! impl prec_climb::Op for Op {
//!     fn precedence(&self) -> usize {
//!         match self {
//!             Op::Add | Op::Sub => 0,
//!             Op::Mul | Op::Div => 1,
//!         }
//!     }
//!
//!     fn associativity(&self) -> Associativity {
//!         Associativity::Right
//!     }
//! }
//!
//! impl prec_climb::Expr<Op> for isize {
//!     fn from_op(lhs: Self, op: Op, rhs: Self) -> Self {
//!         match op {
//!             Op::Add => lhs + rhs,
//!             Op::Sub => lhs - rhs,
//!             Op::Mul => lhs * rhs,
//!             Op::Div => lhs / rhs,
//!         }
//!     }
//! }
//!
//! # fn test() {
//! use Op::{Add, Div, Mul, Sub};
//! // 1 + 2 * 3 - 6 / 2 =
//! // 1 +   6   -   3   = 4
//! let head: isize = 1;
//! let tail = [(Add, 2), (Mul, 3), (Sub, 6), (Div, 2)];
//! let out = prec_climb::climb(head, tail);
//! assert_eq!(out, 4);
//! # }
//! ~~~

use core::iter::Peekable;

/// Associativity of an operator.
pub enum Associativity {
    /// `(x + y) + z`
    Left,
    /// `x + (y + z)`
    Right,
}

/// Binary operator.
pub trait Op {
    /// "Stickiness" of the operator
    fn precedence(&self) -> usize;
    /// Is the operator left- or right-associative?
    fn associativity(&self) -> Associativity;
}

/// An expression that can be built from other expressions with some operator.
pub trait Expr<O: Op> {
    /// Combine two expressions with an operator.
    fn from_op(lhs: Self, op: O, rhs: Self) -> Self;
}

/// Perform precedence climbing.
pub fn climb<O: Op, T: Expr<O>>(head: T, iter: impl IntoIterator<Item = (O, T)>) -> T {
    climb1(head, &mut iter.into_iter().peekable(), 0)
}

fn climb1<O: Op, T: Expr<O>, I>(mut x: T, iter: &mut Peekable<I>, min_prec: usize) -> T
where
    I: Iterator<Item = (O, T)>,
{
    while let Some((op, mut rhs)) = iter.next_if(|(op, _)| op.precedence() >= min_prec) {
        let right_assoc = matches!(op.associativity(), Associativity::Right);
        let this_prec = op.precedence();

        while let Some(next) = iter.peek() {
            let next_prec = next.0.precedence();

            if next_prec > this_prec || (right_assoc && next_prec == this_prec) {
                rhs = climb1(rhs, iter, next_prec)
            } else {
                break;
            }
        }
        x = T::from_op(x, op, rhs);
    }
    x
}