parser_lang/pratt.rs
1//! Pratt (precedence-climbing) expression parsing.
2
3use token_lang::{Token, TokenKind};
4
5use crate::Parser;
6
7/// A precedence-climbing expression grammar, driven over a [`Parser`].
8///
9/// Pratt parsing handles operator precedence and associativity without a separate
10/// grammar rule per level. You describe three things and the provided
11/// [`expression`](Pratt::expression) driver does the rest:
12///
13/// - [`prefix`](Pratt::prefix) — parse an operand: a literal, a parenthesized
14/// expression, a prefix-unary operator and its operand. This is also where
15/// *postfix* forms (a call `()`, an index `[]`) are handled, by looping on the
16/// trailing tokens after the atom.
17/// - [`infix_binding`](Pratt::infix_binding) — the *binding power* of a kind as an
18/// infix operator, as a `(left, right)` pair, or `None` if it is not one. A left
19/// power below the right (`(1, 2)`) is left-associative; above (`(4, 3)`) is
20/// right-associative.
21/// - [`infix`](Pratt::infix) — combine a left operand, the operator token, and the
22/// right operand into one result.
23///
24/// The grammar returns `None` from any method to signal a recoverable error (after
25/// recording a diagnostic on the parser); the driver then unwinds with `None`.
26///
27/// # Examples
28///
29/// A calculator that evaluates as it parses, so `1 + 2 * 3` is `7` — `*` binds
30/// tighter than `+`.
31///
32/// ```
33/// use parser_lang::{Parser, Pratt, Span, Token, TokenKind};
34///
35/// #[derive(Clone, Copy)]
36/// enum K { Num(i64), Plus, Star, Eof }
37/// impl TokenKind for K {
38/// fn is_eof(&self) -> bool { matches!(self, K::Eof) }
39/// }
40///
41/// struct Calc;
42/// impl<'t> Pratt<'t, K> for Calc {
43/// type Output = i64;
44/// fn prefix(&mut self, p: &mut Parser<'t, K>) -> Option<i64> {
45/// match p.bump()?.kind() {
46/// K::Num(n) => Some(*n),
47/// _ => None,
48/// }
49/// }
50/// fn infix_binding(&self, k: &K) -> Option<(u8, u8)> {
51/// match k {
52/// K::Plus => Some((1, 2)),
53/// K::Star => Some((3, 4)),
54/// _ => None,
55/// }
56/// }
57/// fn infix(&mut self, op: &'t Token<K>, left: i64, right: i64) -> Option<i64> {
58/// match op.kind() {
59/// K::Plus => Some(left + right),
60/// K::Star => Some(left * right),
61/// _ => None,
62/// }
63/// }
64/// }
65///
66/// let s = |i| Span::new(i, i + 1);
67/// let tokens = [
68/// Token::new(K::Num(1), s(0)),
69/// Token::new(K::Plus, s(1)),
70/// Token::new(K::Num(2), s(2)),
71/// Token::new(K::Star, s(3)),
72/// Token::new(K::Num(3), s(4)),
73/// Token::new(K::Eof, Span::empty(5)),
74/// ];
75/// let mut p = Parser::new(&tokens);
76/// let mut calc = Calc;
77/// assert_eq!(calc.parse(&mut p), Some(7));
78/// ```
79pub trait Pratt<'t, K: TokenKind> {
80 /// What the grammar builds — an AST node, a value, a string.
81 type Output;
82
83 /// Parses an operand at the cursor: a literal, a parenthesized group, or a
84 /// prefix operator applied to a sub-expression (parsed by calling
85 /// [`expression`](Pratt::expression) with the operator's right binding power).
86 /// Returns `None` after recording a diagnostic on a syntax error.
87 fn prefix(&mut self, parser: &mut Parser<'t, K>) -> Option<Self::Output>;
88
89 /// Returns the `(left, right)` binding power of `kind` as an infix operator, or
90 /// `None` if the kind does not begin an infix operator. Left below right is
91 /// left-associative; left above right is right-associative.
92 fn infix_binding(&self, kind: &K) -> Option<(u8, u8)>;
93
94 /// Combines `left`, the already-consumed operator token `op`, and `right` into
95 /// one result. Returns `None` after recording a diagnostic on an error.
96 fn infix(
97 &mut self,
98 op: &'t Token<K>,
99 left: Self::Output,
100 right: Self::Output,
101 ) -> Option<Self::Output>;
102
103 /// Parses an expression whose operators all bind at least as tightly as
104 /// `min_bp` — the precedence-climbing driver. Provided; do not override.
105 ///
106 /// Parse a full expression with [`parse`](Pratt::parse), which calls this with
107 /// a minimum of `0`. Call it directly with an operator's right binding power
108 /// from inside [`prefix`](Pratt::prefix) to parse the operand of a prefix
109 /// operator.
110 fn expression(&mut self, parser: &mut Parser<'t, K>, min_bp: u8) -> Option<Self::Output> {
111 let mut left = self.prefix(parser)?;
112 while let Some(kind) = parser.peek_kind() {
113 let Some((left_bp, right_bp)) = self.infix_binding(kind) else {
114 break;
115 };
116 if left_bp < min_bp {
117 break;
118 }
119 // Consume the operator, then its right operand at the operator's right
120 // binding power — higher right power groups more to the right.
121 let op = parser.bump()?;
122 let right = self.expression(parser, right_bp)?;
123 left = self.infix(op, left, right)?;
124 }
125 Some(left)
126 }
127
128 /// Parses a complete expression from the cursor (minimum binding power `0`).
129 fn parse(&mut self, parser: &mut Parser<'t, K>) -> Option<Self::Output> {
130 self.expression(parser, 0)
131 }
132}
133
134#[cfg(test)]
135mod tests {
136 use token_lang::Span;
137
138 use super::*;
139
140 #[derive(Clone, Copy, Debug)]
141 enum K {
142 Num(i64),
143 Plus,
144 Minus,
145 Star,
146 Caret,
147 Eof,
148 }
149 impl TokenKind for K {
150 fn is_eof(&self) -> bool {
151 matches!(self, K::Eof)
152 }
153 }
154
155 /// Builds an `S`-expression string so associativity and precedence are visible
156 /// in the output: `(+ 1 (* 2 3))`.
157 struct Sexpr;
158 impl<'t> Pratt<'t, K> for Sexpr {
159 type Output = alloc::string::String;
160 fn prefix(&mut self, p: &mut Parser<'t, K>) -> Option<Self::Output> {
161 use alloc::string::ToString;
162 match p.bump()?.kind() {
163 K::Num(n) => Some(n.to_string()),
164 K::Minus => {
165 // Prefix negation binds tighter than any infix operator here.
166 let operand = self.expression(p, 100)?;
167 Some(alloc::format!("(neg {operand})"))
168 }
169 _ => None,
170 }
171 }
172 fn infix_binding(&self, k: &K) -> Option<(u8, u8)> {
173 match k {
174 K::Plus | K::Minus => Some((1, 2)),
175 K::Star => Some((3, 4)),
176 K::Caret => Some((6, 5)), // right-associative
177 _ => None,
178 }
179 }
180 fn infix(
181 &mut self,
182 op: &'t Token<K>,
183 left: Self::Output,
184 right: Self::Output,
185 ) -> Option<Self::Output> {
186 let sym = match op.kind() {
187 K::Plus => "+",
188 K::Minus => "-",
189 K::Star => "*",
190 K::Caret => "^",
191 _ => return None,
192 };
193 Some(alloc::format!("({sym} {left} {right})"))
194 }
195 }
196
197 fn lex(kinds: &[K]) -> alloc::vec::Vec<Token<K>> {
198 kinds
199 .iter()
200 .enumerate()
201 .map(|(i, k)| Token::new(*k, Span::new(i as u32, i as u32 + 1)))
202 .collect()
203 }
204
205 fn parse(kinds: &[K]) -> Option<alloc::string::String> {
206 let tokens = lex(kinds);
207 let mut p = Parser::new(&tokens);
208 Sexpr.parse(&mut p)
209 }
210
211 #[test]
212 fn test_precedence_multiplication_binds_tighter() {
213 // 1 + 2 * 3 -> (+ 1 (* 2 3))
214 let out = parse(&[K::Num(1), K::Plus, K::Num(2), K::Star, K::Num(3), K::Eof]);
215 assert_eq!(out.as_deref(), Some("(+ 1 (* 2 3))"));
216 }
217
218 #[test]
219 fn test_left_associative_addition() {
220 // 1 - 2 - 3 -> (- (- 1 2) 3)
221 let out = parse(&[K::Num(1), K::Minus, K::Num(2), K::Minus, K::Num(3), K::Eof]);
222 assert_eq!(out.as_deref(), Some("(- (- 1 2) 3)"));
223 }
224
225 #[test]
226 fn test_right_associative_power() {
227 // 2 ^ 3 ^ 2 -> (^ 2 (^ 3 2))
228 let out = parse(&[K::Num(2), K::Caret, K::Num(3), K::Caret, K::Num(2), K::Eof]);
229 assert_eq!(out.as_deref(), Some("(^ 2 (^ 3 2))"));
230 }
231
232 #[test]
233 fn test_prefix_operator() {
234 // -2 * 3 -> (* (neg 2) 3)
235 let out = parse(&[K::Minus, K::Num(2), K::Star, K::Num(3), K::Eof]);
236 assert_eq!(out.as_deref(), Some("(* (neg 2) 3)"));
237 }
238}