pratt/
lib.rs

1use std::fmt;
2use std::iter::Peekable;
3use std::result;
4
5#[derive(Copy, Clone)]
6pub enum Associativity {
7    Left,
8    Right,
9    Neither,
10}
11
12#[derive(PartialEq, Eq, PartialOrd, Copy, Clone)]
13pub struct Precedence(pub u32);
14
15impl Precedence {
16    const fn raise(mut self) -> Precedence {
17        self.0 += 1;
18        self
19    }
20    const fn lower(mut self) -> Precedence {
21        self.0 -= 1;
22        self
23    }
24    const fn normalize(mut self) -> Precedence {
25        self.0 *= 10;
26        self
27    }
28    const fn min() -> Precedence {
29        Precedence(std::u32::MIN)
30    }
31    const fn max() -> Precedence {
32        Precedence(std::u32::MAX)
33    }
34}
35
36#[derive(Copy, Clone)]
37pub enum Affix {
38    Nilfix,
39    Infix(Precedence, Associativity),
40    Prefix(Precedence),
41    Postfix(Precedence),
42}
43
44#[derive(Debug)]
45pub enum PrattError<I: fmt::Debug, E: fmt::Display> {
46    UserError(E),
47    EmptyInput,
48    UnexpectedNilfix(I),
49    UnexpectedPrefix(I),
50    UnexpectedInfix(I),
51    UnexpectedPostfix(I),
52}
53
54impl<I: fmt::Debug, E: fmt::Display> fmt::Display for PrattError<I, E> {
55    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
56        match self {
57            PrattError::UserError(e) => write!(f, "{}", e),
58            PrattError::EmptyInput => write!(f, "Pratt parser was called with empty input."),
59            PrattError::UnexpectedNilfix(t) => {
60                write!(f, "Expected Infix or Postfix, found Nilfix {:?}", t)
61            }
62            PrattError::UnexpectedPrefix(t) => {
63                write!(f, "Expected Infix or Postfix, found Prefix {:?}", t)
64            }
65            PrattError::UnexpectedInfix(t) => {
66                write!(f, "Expected Nilfix or Prefix, found Infix {:?}", t)
67            }
68            PrattError::UnexpectedPostfix(t) => {
69                write!(f, "Expected Nilfix or Prefix, found Postfix {:?}", t)
70            }
71        }
72    }
73}
74
75#[derive(Debug)]
76pub struct NoError;
77
78impl fmt::Display for NoError {
79    fn fmt(&self, _: &mut std::fmt::Formatter) -> std::fmt::Result {
80        Ok(())
81    }
82}
83
84pub type Result<T> = result::Result<T, NoError>;
85
86pub trait PrattParser<Inputs>
87where
88    Inputs: Iterator<Item = Self::Input>,
89{
90    type Error: fmt::Display;
91    type Input: fmt::Debug;
92    type Output: Sized;
93
94    fn query(&mut self, input: &Self::Input) -> result::Result<Affix, Self::Error>;
95
96    fn primary(&mut self, input: Self::Input) -> result::Result<Self::Output, Self::Error>;
97
98    fn infix(
99        &mut self,
100        lhs: Self::Output,
101        op: Self::Input,
102        rhs: Self::Output,
103    ) -> result::Result<Self::Output, Self::Error>;
104
105    fn prefix(
106        &mut self,
107        op: Self::Input,
108        rhs: Self::Output,
109    ) -> result::Result<Self::Output, Self::Error>;
110
111    fn postfix(
112        &mut self,
113        lhs: Self::Output,
114        op: Self::Input,
115    ) -> result::Result<Self::Output, Self::Error>;
116
117    fn parse(
118        &mut self,
119        inputs: Inputs,
120    ) -> result::Result<Self::Output, PrattError<Self::Input, Self::Error>> {
121        self.parse_input(&mut inputs.peekable(), Precedence::min())
122    }
123
124    fn parse_peekable(
125        &mut self,
126        inputs: &mut Peekable<Inputs>,
127    ) -> result::Result<Self::Output, PrattError<Self::Input, Self::Error>> {
128        self.parse_input(inputs, Precedence::min())
129    }
130
131    fn parse_input(
132        &mut self,
133        tail: &mut Peekable<Inputs>,
134        rbp: Precedence,
135    ) -> result::Result<Self::Output, PrattError<Self::Input, Self::Error>> {
136        if let Some(head) = tail.next() {
137            let info = self.query(&head).map_err(PrattError::UserError)?;
138            let mut nbp = self.nbp(info);
139            let mut node = self.nud(head, tail, info);
140            while let Some(head) = tail.peek() {
141                let info = self.query(head).map_err(PrattError::UserError)?;
142                let lbp = self.lbp(info);
143                if rbp < lbp && lbp < nbp {
144                    let head = tail.next().unwrap();
145                    nbp = self.nbp(info);
146                    node = self.led(head, tail, info, node?);
147                } else {
148                    break;
149                }
150            }
151            node
152        } else {
153            Err(PrattError::EmptyInput)
154        }
155    }
156
157    /// Null-Denotation
158    fn nud(
159        &mut self,
160        head: Self::Input,
161        tail: &mut Peekable<Inputs>,
162        info: Affix,
163    ) -> result::Result<Self::Output, PrattError<Self::Input, Self::Error>> {
164        match info {
165            Affix::Prefix(precedence) => {
166                let rhs = self.parse_input(tail, precedence.normalize().lower());
167                self.prefix(head, rhs?).map_err(PrattError::UserError)
168            }
169            Affix::Nilfix => self.primary(head).map_err(PrattError::UserError),
170            Affix::Postfix(_) => Err(PrattError::UnexpectedPostfix(head)),
171            Affix::Infix(_, _) => Err(PrattError::UnexpectedInfix(head)),
172        }
173    }
174
175    /// Left-Denotation
176    fn led(
177        &mut self,
178        head: Self::Input,
179        tail: &mut Peekable<Inputs>,
180        info: Affix,
181        lhs: Self::Output,
182    ) -> result::Result<Self::Output, PrattError<Self::Input, Self::Error>> {
183        match info {
184            Affix::Infix(precedence, associativity) => {
185                let precedence = precedence.normalize();
186                let rhs = match associativity {
187                    Associativity::Left => self.parse_input(tail, precedence),
188                    Associativity::Right => self.parse_input(tail, precedence.lower()),
189                    Associativity::Neither => self.parse_input(tail, precedence.raise()),
190                };
191                self.infix(lhs, head, rhs?).map_err(PrattError::UserError)
192            }
193            Affix::Postfix(_) => self.postfix(lhs, head).map_err(PrattError::UserError),
194            Affix::Nilfix => Err(PrattError::UnexpectedNilfix(head)),
195            Affix::Prefix(_) => Err(PrattError::UnexpectedPrefix(head)),
196        }
197    }
198
199    //         <lbp>  <rbp>  <nbp> <kind>
200    // Nilfix:  MIN |  MIN |  MAX | nud
201    // Prefix:  MIN |   bp |  MAX | nud
202    // Postfix:  bp |  MIN |  MAX | led
203    // InfixL:   bp |   bp | bp+1 | led
204    // InfixR:   bp | bp-1 | bp+1 | led
205    // InfixN:   bp |   bp |   bp | led
206
207    /// Left-Binding-Power
208    fn lbp(&mut self, info: Affix) -> Precedence {
209        match info {
210            Affix::Nilfix => Precedence::min(),
211            Affix::Prefix(_) => Precedence::min(),
212            Affix::Postfix(precedence) => precedence.normalize(),
213            Affix::Infix(precedence, _) => precedence.normalize(),
214        }
215    }
216
217    /// Next-Binding-Power
218    fn nbp(&mut self, info: Affix) -> Precedence {
219        match info {
220            Affix::Nilfix => Precedence::max(),
221            Affix::Prefix(_) => Precedence::max(),
222            Affix::Postfix(_) => Precedence::max(),
223            Affix::Infix(precedence, Associativity::Left) => precedence.normalize().raise(),
224            Affix::Infix(precedence, Associativity::Right) => precedence.normalize().raise(),
225            Affix::Infix(precedence, Associativity::Neither) => precedence.normalize(),
226        }
227    }
228}
pratt/lib.rs

pratt/
lib.rs
