expr_solver/
parser.rs

1use crate::ast::{BinOp, Expr, UnOp};
2use crate::lexer::Lexer;
3use crate::source::Source;
4use crate::span::{Span, SpanError};
5use crate::token::Token;
6use thiserror::Error;
7
8/// Expression parsing errors.
9#[derive(Error, Debug, Clone)]
10pub enum ParseError {
11    #[error("Unexpected token '{found}', expected '{expected}'")]
12    UnexpectedToken {
13        found: String,
14        expected: String,
15        span: Span,
16    },
17}
18
19impl SpanError for ParseError {
20    fn span(&self) -> Span {
21        match self {
22            ParseError::UnexpectedToken { span, .. } => *span,
23        }
24    }
25}
26
27pub type ParseResult<'src, 'sym> = Result<Expr<'src, 'sym>, ParseError>;
28
29/// Recursive descent parser for mathematical expressions.
30///
31/// Uses operator precedence climbing for efficient binary operator parsing.
32pub struct Parser<'src> {
33    lexer: Lexer<'src>,
34    lookahead: Token<'src>,
35    span: Span,
36}
37
38impl<'src, 'sym> Parser<'src> {
39    /// Creates a new parser from a source.
40    pub fn new(source: &'src Source) -> Self {
41        let mut lexer = Lexer::new(source);
42        let lookahead = lexer.next();
43        let span = lexer.span();
44        Self {
45            lexer,
46            lookahead,
47            span,
48        }
49    }
50
51    /// Parses the source into an abstract syntax tree.
52    ///
53    /// Returns `None` for empty input, or an expression AST on success.
54    pub fn parse(&mut self) -> Result<Option<Expr<'src, 'sym>>, ParseError> {
55        if self.lookahead == Token::EOF {
56            return Ok(None);
57        }
58        let expr = self.expression()?;
59        self.expect(&Token::EOF)?;
60        Ok(Some(expr))
61    }
62
63    fn expression(&mut self) -> ParseResult<'src, 'sym> {
64        let lhs = self.primary()?;
65        self.climb(lhs, 1)
66    }
67
68    fn primary(&mut self) -> ParseResult<'src, 'sym> {
69        let span = self.span;
70        match self.lookahead {
71            Token::Number(n) => {
72                self.advance();
73                Ok(Expr::literal(n, span))
74            }
75            Token::Ident(id) => {
76                self.advance();
77                if self.lookahead == Token::ParenOpen {
78                    return self.call(id, span);
79                }
80                Ok(Expr::ident(id, span))
81            }
82            Token::Minus => {
83                self.advance();
84                let expr = self.primary()?;
85                let expr = self.climb(expr, Token::Negate.precedence())?;
86                let span = self.span.merge(expr.span);
87                Ok(Expr::unary(UnOp::Neg, expr, span))
88            }
89            Token::ParenOpen => {
90                self.advance();
91                let expr = self.expression()?;
92                self.expect(&Token::ParenClose)?;
93                Ok(expr)
94            }
95            _ => Err(ParseError::UnexpectedToken {
96                found: self.lookahead.lexeme().to_string(),
97                expected: "an expression".to_string(),
98                span,
99            }),
100        }
101    }
102
103    fn call(&mut self, id: &'src str, span: Span) -> ParseResult<'src, 'sym> {
104        // assume lookahead is '('
105        self.advance();
106
107        let mut args: Vec<Expr<'src, 'sym>> = Vec::new();
108        while self.lookahead != Token::ParenClose {
109            let arg = self.expression()?;
110            args.push(arg);
111            if self.lookahead == Token::Comma {
112                self.advance();
113            } else {
114                break;
115            }
116        }
117        self.expect(&Token::ParenClose)?;
118
119        let span = span.merge(self.span);
120        Ok(Expr::call(id, args, span))
121    }
122
123    fn climb(&mut self, mut lhs: Expr<'src, 'sym>, min_prec: u8) -> ParseResult<'src, 'sym> {
124        let mut prec = self.lookahead.precedence();
125        while prec >= min_prec {
126            // Handle postfix unary operators
127            if self.lookahead.is_postfix_unary() {
128                let op = self.lookahead.clone();
129                let op_span = self.span;
130                self.advance();
131                prec = self.lookahead.precedence();
132
133                let unary_op = UnOp::from_token(&op);
134                let span = lhs.span.merge(op_span);
135                lhs = Expr::unary(unary_op, lhs, span);
136                continue;
137            }
138
139            let op = self.lookahead.clone();
140
141            self.advance();
142            let mut rhs = self.primary()?;
143            prec = self.lookahead.precedence();
144
145            while prec > op.precedence()
146                || (self.lookahead.is_right_associative() && prec == op.precedence())
147            {
148                rhs = self.climb(rhs, prec)?;
149                prec = self.lookahead.precedence();
150            }
151
152            let op = BinOp::from_token(&op);
153            let span = lhs.span.merge(rhs.span);
154            lhs = Expr::binary(op, lhs, rhs, span);
155        }
156        Ok(lhs)
157    }
158
159    fn advance(&mut self) {
160        self.lookahead = self.lexer.next();
161        self.span = self.lexer.span();
162    }
163
164    fn accept(&mut self, t: &Token<'src>) -> bool {
165        if self.lookahead == *t {
166            self.advance();
167            true
168        } else {
169            false
170        }
171    }
172
173    fn expect(&mut self, tkn: &Token<'src>) -> Result<(), ParseError> {
174        if !self.accept(tkn) {
175            return Err(ParseError::UnexpectedToken {
176                found: self.lookahead.lexeme().to_string(),
177                expected: tkn.lexeme().to_string(),
178                span: self.span,
179            });
180        }
181        Ok(())
182    }
183}
expr_solver/parser.rs

expr_solver/
parser.rs
