oak_core/parser/
pratt.rs

1use crate::{Language, ParserState, source::Source, tree::GreenNode};
2
3/// Associativity of an operator.
4#[derive(Debug, Clone, Copy, PartialEq, Eq)]
5pub enum Associativity {
6    /// Left-associative (e.g., a + b + c is (a + b) + c).
7    Left,
8    /// Right-associative (e.g., a = b = c is a = (b = c)).
9    Right,
10    /// Non-associative.
11    None,
12}
13
14/// Precedence and associativity of an operator.
15#[derive(Debug, Clone, Copy, PartialEq, Eq)]
16pub struct OperatorInfo {
17    /// Precedence of the operator.
18    pub precedence: u8,
19    /// Associativity of the operator.
20    pub associativity: Associativity,
21}
22
23impl OperatorInfo {
24    /// Creates a left-associative operator info.
25    pub fn left(precedence: u8) -> Self {
26        Self { precedence, associativity: Associativity::Left }
27    }
28
29    /// Creates a right-associative operator info.
30    pub fn right(precedence: u8) -> Self {
31        Self { precedence, associativity: Associativity::Right }
32    }
33
34    /// Creates a non-associative operator info.
35    pub fn none(precedence: u8) -> Self {
36        Self { precedence, associativity: Associativity::None }
37    }
38}
39
40/// A specification for a Pratt parser.
41///
42/// Users implement this trait to define the grammar rules for expressions.
43/// Using a trait allows the compiler to optimize operator lookups using match statements.
44pub trait Pratt<L: Language> {
45    /// Parses a primary expression (e.g., literals, identifiers, group).
46    fn primary<'a, S: Source + ?Sized>(&self, state: &mut ParserState<'a, L, S>) -> &'a GreenNode<'a, L>;
47
48    /// Handles prefix operators and primary expressions.
49    ///
50    /// Default implementation just calls `primary`.
51    fn prefix<'a, S: Source + ?Sized>(&self, state: &mut ParserState<'a, L, S>) -> &'a GreenNode<'a, L> {
52        self.primary(state)
53    }
54
55    /// Handles infix and postfix operators.
56    ///
57    /// Should return `Some(new_node)` if an operator was parsed, or `None` if no operator matches
58    /// or its precedence is lower than `min_precedence`.
59    fn infix<'a, S: Source + ?Sized>(&self, state: &mut ParserState<'a, L, S>, left: &'a GreenNode<'a, L>, min_precedence: u8) -> Option<&'a GreenNode<'a, L>>;
60}
61
62/// A helper for parsing binary (infix) expressions.
63#[inline(always)]
64pub fn binary<'a, L, S, F>(state: &mut ParserState<'a, L, S>, left: &'a GreenNode<'a, L>, op_kind: L::TokenType, op_precedence: u8, assoc: Associativity, result_kind: L::ElementType, mut parse_expr: F) -> &'a GreenNode<'a, L>
65where
66    L: Language,
67    S: Source + ?Sized,
68    F: FnMut(&mut ParserState<'a, L, S>, u8) -> &'a GreenNode<'a, L>,
69    L::ElementType: From<L::TokenType>,
70{
71    let cp = state.checkpoint();
72    state.push_child(left);
73    state.expect(op_kind).ok();
74
75    let next_prec = match assoc {
76        Associativity::Left => op_precedence + 1,
77        Associativity::Right => op_precedence,
78        Associativity::None => op_precedence + 1,
79    };
80
81    let right = parse_expr(state, next_prec);
82    state.push_child(right);
83    state.finish_at(cp, result_kind)
84}
85
86/// A helper for parsing unary (prefix) expressions.
87#[inline(always)]
88pub fn unary<'a, L, S, F>(state: &mut ParserState<'a, L, S>, op_kind: L::TokenType, op_precedence: u8, result_kind: L::ElementType, mut parse_expr: F) -> &'a GreenNode<'a, L>
89where
90    L: Language,
91    S: Source + ?Sized,
92    F: FnMut(&mut ParserState<'a, L, S>, u8) -> &'a GreenNode<'a, L>,
93    L::ElementType: From<L::TokenType>,
94{
95    let cp = state.checkpoint();
96    state.expect(op_kind).ok();
97    let right = parse_expr(state, op_precedence);
98    state.push_child(right);
99    state.finish_at(cp, result_kind)
100}
101
102/// A helper for parsing postfix expressions.
103#[inline(always)]
104pub fn postfix<'a, L, S>(state: &mut ParserState<'a, L, S>, left: &'a GreenNode<'a, L>, op_kind: L::TokenType, result_kind: L::ElementType) -> &'a GreenNode<'a, L>
105where
106    L: Language,
107    S: Source + ?Sized,
108    L::ElementType: From<L::TokenType>,
109{
110    let cp = state.checkpoint();
111    state.push_child(left);
112    state.expect(op_kind).ok();
113    state.finish_at(cp, result_kind)
114}
115
116/// A Pratt parser implementation.
117pub struct PrattParser<L: Language, T: Pratt<L>> {
118    spec: T,
119    _marker: core::marker::PhantomData<L>,
120}
121
122impl<L: Language, T: Pratt<L>> PrattParser<L, T> {
123    /// Creates a new Pratt parser with the given specification.
124    pub const fn new(spec: T) -> Self {
125        Self { spec, _marker: core::marker::PhantomData }
126    }
127
128    /// Parses an expression with the given minimum precedence.
129    pub fn parse_expr<'a, S: Source + ?Sized>(&self, state: &mut ParserState<'a, L, S>, min_precedence: u8) -> &'a GreenNode<'a, L> {
130        Self::parse(state, min_precedence, &self.spec)
131    }
132
133    /// Static version of parse_expr that takes a specification reference.
134    pub fn parse<'a, S: Source + ?Sized>(state: &mut ParserState<'a, L, S>, min_precedence: u8, spec: &T) -> &'a GreenNode<'a, L> {
135        let mut left = spec.prefix(state);
136
137        while let Some(node) = spec.infix(state, left, min_precedence) {
138            left = node;
139        }
140
141        left
142    }
143}
oak_core/parser/pratt.rs

oak_core/parser/
pratt.rs
