mathengine_parser/
parser.rs

1use crate::ast::Expression;
2use crate::error::ParseError;
3use mathengine_lexer::{Operation, Token};
4
5pub struct Parser {
6    tokens: Vec<Token>,
7    pos: usize,
8}
9
10impl Parser {
11    pub fn new(tokens: Vec<Token>) -> Self {
12        Self { tokens, pos: 0 }
13    }
14
15    // Entry point for parsing - parses the entire token stream and ensures all tokens are consumed
16    pub fn parse(&mut self) -> Result<Expression, ParseError> {
17        if self.tokens.is_empty() {
18            return Err(ParseError::EmptyTokenStream);
19        }
20
21        let expr = self.parse_expression(0)?;
22        if self.pos < self.tokens.len() {
23            return Err(ParseError::UnexpectedToken {
24                expected: "end of input".to_string(),
25                found: self.tokens[self.pos].clone(),
26                position: self.pos,
27            });
28        }
29        Ok(expr)
30    }
31
32    // Pratt parsing algorithm - handles binary operators with correct precedence and associativity
33    // min_precedence determines the minimum operator precedence this call will handle
34    fn parse_expression(&mut self, min_precedence: u8) -> Result<Expression, ParseError> {
35        let mut left = self.parse_primary()?;
36
37        while let Some(token) = self.peek() {
38            match token {
39                Token::Operation(op) => {
40                    let precedence = self.get_precedence(op);
41                    if precedence < min_precedence {
42                        break;
43                    }
44
45                    let op = match self.advance() {
46                        Some(Token::Operation(o)) => o.clone(),
47                        _ => unreachable!(),
48                    };
49
50                    let right_precedence = if self.is_right_associative(&op) {
51                        precedence
52                    } else {
53                        precedence + 1
54                    };
55
56                    let right = self.parse_expression(right_precedence)?;
57                    left = Expression::Binary {
58                        op,
59                        left: Box::new(left),
60                        right: Box::new(right),
61                    };
62                }
63                _ => break,
64            }
65        }
66
67        Ok(left)
68    }
69
70    // Parses primary expressions: numbers, parenthesized expressions, and unary operators
71    fn parse_primary(&mut self) -> Result<Expression, ParseError> {
72        let start_pos = self.pos;
73        match self.advance() {
74            Some(Token::Number(n)) => Ok(Expression::Number(*n)),
75            Some(Token::UnitValue { value, unit }) => Ok(Expression::UnitValue {
76                value: *value,
77                unit: unit.clone(),
78            }),
79            Some(Token::Unit(unit)) => Ok(Expression::Unit(unit.clone())),
80            Some(Token::Lparen) => {
81                let expr = self.parse_expression(0)?;
82                match self.advance() {
83                    Some(Token::Rparen) => Ok(expr),
84                    Some(other) => Err(ParseError::UnexpectedToken {
85                        expected: "')'".to_string(),
86                        found: other.clone(),
87                        position: self.pos - 1,
88                    }),
89                    None => Err(ParseError::UnexpectedEndOfInput {
90                        expected: "')'".to_string(),
91                    }),
92                }
93            }
94            Some(Token::Operation(Operation::Subtract)) => {
95                let operand = self.parse_primary()?;
96                Ok(Expression::Unary {
97                    op: Operation::Subtract,
98                    operand: Box::new(operand),
99                })
100            }
101            Some(token) => Err(ParseError::UnexpectedToken {
102                expected: "number, unit value, '(', or unary operator".to_string(),
103                found: token.clone(),
104                position: start_pos,
105            }),
106            None => Err(ParseError::UnexpectedEndOfInput {
107                expected: "expression".to_string(),
108            }),
109        }
110    }
111
112    // Returns the current token without consuming it
113    fn peek(&self) -> Option<&Token> {
114        self.tokens.get(self.pos)
115    }
116
117    // Consumes and returns the current token, advancing the position
118    fn advance(&mut self) -> Option<&Token> {
119        if self.pos < self.tokens.len() {
120            let token = &self.tokens[self.pos];
121            self.pos += 1;
122            Some(token)
123        } else {
124            None
125        }
126    }
127
128    // Returns the precedence level for each operator (higher number = higher precedence)
129    fn get_precedence(&self, op: &Operation) -> u8 {
130        match op {
131            Operation::Add | Operation::Subtract => 1,
132            Operation::Multiply | Operation::Divide => 2,
133            Operation::Power => 3,
134            Operation::Convert => 5,
135        }
136    }
137
138    // Determines if an operator is right-associative (currently all ops are left-associative)
139    fn is_right_associative(&self, op: &Operation) -> bool {
140        match op {
141            Operation::Power => true, // Power is right-associative: 2^3^4 = 2^(3^4)
142            _ => false,
143        }
144    }
145}
146
mathengine_parser/parser.rs

mathengine_parser/
parser.rs
