diff options
| -rw-r--r-- | src/parser.rs | 319 |
1 files changed, 175 insertions, 144 deletions
diff --git a/src/parser.rs b/src/parser.rs index 3728ebf..2b33e0f 100644 --- a/src/parser.rs +++ b/src/parser.rs @@ -4,55 +4,39 @@ use crate::lexer::Lexer; use num::BigInt; use std::str::FromStr; -enum ParseError { - Empty, - Consumed, -} - -fn seq<T>(r: Result<T, ParseError>) -> Result<T, ParseError> { - match r { - Err(ParseError::Empty) => Err(ParseError::Consumed), - x => x, - } -} - -fn or<T>(r: Result<T, ParseError>) -> Result<Option<T>, ParseError> { - match r { - Ok(x) => Ok(Some(x)), - Err(ParseError::Empty) => Ok(None), - Err(ParseError::Consumed) => Err(ParseError::Consumed), - } +enum Op { + Paren, + Op { + prec: i8, + eval: Box<dyn FnOnce(Num) -> Num>, + }, } struct Parser<'a> { r: Lexer<'a>, first_token: Option<&'a str>, + stack: Vec<Op>, } impl<'a> Parser<'a> { - fn peek(&mut self) -> Result<&'a str, ParseError> { + fn peek(&mut self) -> Option<&'a str> { if let Some(t) = self.first_token { - return Ok(t); + return Some(t); } - let Some(t) = self.r.next() else { - return Err(ParseError::Empty); - }; + let t = self.r.next()?; self.first_token = Some(t); - Ok(t) + Some(t) } - fn next(&mut self) -> Result<&'a str, ParseError> { + fn next(&mut self) -> Option<&'a str> { if let Some(t) = std::mem::take(&mut self.first_token) { - return Ok(t); + return Some(t); } - let Some(t) = self.r.next() else { - return Err(ParseError::Empty); - }; - Ok(t) + self.r.next() } fn symbol(&mut self, s: &str) -> bool { - let Ok(t) = self.peek() else { + let Some(t) = self.peek() else { return false; }; if t != s { @@ -62,176 +46,227 @@ impl<'a> Parser<'a> { true } - fn parse_num(&mut self) -> Result<Num, ParseError> { + fn parse_num(&mut self) -> Option<Num> { let negative = self.symbol("-"); - let t = seq(self.next())?; + let t = self.next()?; if t.contains('.') || t.contains('e') || t.contains('E') { let Ok(f) = f64::from_str(t) else { - return Err(ParseError::Consumed); + return None; }; if negative { - return Ok(eval::float(-f)); + return Some(eval::float(-f)); } - return Ok(eval::float(f)); + return Some(eval::float(f)); } let Ok(i) = BigInt::from_str(t) else { - return Err(ParseError::Consumed); + return None; }; if negative { - return Ok(eval::int(-i)); + return Some(eval::int(-i)); } - Ok(eval::int(i)) + Some(eval::int(i)) } - fn paren_expr(&mut self) -> Result<Num, ParseError> { - if !self.symbol("(") { - return Err(ParseError::Empty); - } - let n = seq(self.expr())?; - if !self.symbol(")") { - return Err(ParseError::Consumed); - } - Ok(n) - } - - fn parse_const(&mut self) -> Result<Num, ParseError> { + fn parse_const(&mut self) -> Option<Num> { if self.symbol("e") { - return Ok(eval::float(std::f64::consts::E)); + return Some(eval::float(std::f64::consts::E)); } if self.symbol("pi") { - return Ok(eval::float(std::f64::consts::PI)); - } - Err(ParseError::Empty) - } - - fn atom(&mut self) -> Result<Num, ParseError> { - if let Some(n) = or(self.paren_expr())? { - return Ok(n); - } - if let Some(n) = or(self.parse_const())? { - return Ok(n); + return Some(eval::float(std::f64::consts::PI)); } self.parse_num() } - fn parse_fun(&mut self) -> Result<Num, ParseError> { + fn parse_fun(&mut self) -> bool { if self.symbol("sin") { - return Ok(seq(self.fun_expr())?.sin()); + self.stack.push(Op::Op { + prec: 3, + eval: Box::new(eval::Num::sin), + }); + return true; } if self.symbol("cos") { - return Ok(seq(self.fun_expr())?.cos()); + self.stack.push(Op::Op { + prec: 3, + eval: Box::new(eval::Num::cos), + }); + return true; } if self.symbol("tan") { - return Ok(seq(self.fun_expr())?.tan()); + self.stack.push(Op::Op { + prec: 3, + eval: Box::new(eval::Num::tan), + }); + return true; } if self.symbol("sqrt") { - return Ok(seq(self.fun_expr())?.sqrt()); + self.stack.push(Op::Op { + prec: 3, + eval: Box::new(eval::Num::sqrt), + }); + return true; } if self.symbol("log") || self.symbol("ln") { - return Ok(seq(self.fun_expr())?.log()); + self.stack.push(Op::Op { + prec: 3, + eval: Box::new(eval::Num::log), + }); + return true; } if self.symbol("log10") { - return Ok(seq(self.fun_expr())?.log10()); + self.stack.push(Op::Op { + prec: 3, + eval: Box::new(eval::Num::log10), + }); + return true; } if self.symbol("log2") { - return Ok(seq(self.fun_expr())?.log2()); + self.stack.push(Op::Op { + prec: 3, + eval: Box::new(eval::Num::log2), + }); + return true; } if self.symbol("floor") { - return Ok(seq(self.fun_expr())?.floor()); + self.stack.push(Op::Op { + prec: 3, + eval: Box::new(eval::Num::floor), + }); + return true; } if self.symbol("ceil") || self.symbol("ceiling") { - return Ok(seq(self.fun_expr())?.ceil()); + self.stack.push(Op::Op { + prec: 3, + eval: Box::new(eval::Num::ceil), + }); + return true; } if self.symbol("round") { - return Ok(seq(self.fun_expr())?.round()); + self.stack.push(Op::Op { + prec: 3, + eval: Box::new(eval::Num::round), + }); + return true; } if self.symbol("abs") { - return Ok(seq(self.fun_expr())?.abs()); + self.stack.push(Op::Op { + prec: 3, + eval: Box::new(eval::Num::abs), + }); + return true; } - Err(ParseError::Empty) + false } - fn fun_expr(&mut self) -> Result<Num, ParseError> { - if let Some(n) = or(self.parse_fun())? { - return Ok(n); - } - self.atom() - } - - fn fun_expr_no_num(&mut self) -> Result<Num, ParseError> { - if let Some(n) = or(self.parse_fun())? { - return Ok(n); - } - if let Some(n) = or(self.paren_expr())? { - return Ok(n); - } - self.parse_const() - } - - fn expt_expr(&mut self) -> Result<Num, ParseError> { - let e1 = self.fun_expr()?; - if self.symbol("^") { - let e2 = seq(self.expt_expr())?; - return Ok(e1.pow(e2)); + fn eval(&mut self, n: Num, target_prec: i8) -> Num { + let mut n = n; + while let Some(Op::Op { prec, .. }) = self.stack.last() { + if *prec < target_prec { + break; + } + let Some(Op::Op { eval, .. }) = self.stack.pop() else { + unreachable!(); + }; + n = eval(n); } - Ok(e1) + n } - fn expt_expr_no_num(&mut self) -> Result<Num, ParseError> { - let e1 = self.fun_expr_no_num()?; + fn parse_op(&mut self, n: Num) { if self.symbol("^") { - let e2 = seq(self.expt_expr())?; - return Ok(e1.pow(e2)); + let n1 = self.eval(n, 3); + self.stack.push(Op::Op { + prec: 2, + eval: Box::new(move |n2| n1.pow(n2)), + }); + return; } - Ok(e1) - } - - fn mul_expr_fold(&mut self, e1: Num) -> Result<Num, ParseError> { if self.symbol("*") { - let e2 = seq(self.expt_expr())?; - return self.mul_expr_fold(e1.mul(e2)); + let n1 = self.eval(n, 1); + self.stack.push(Op::Op { + prec: 1, + eval: Box::new(move |n2| n1.mul(n2)), + }); + return; } if self.symbol("/") { - let e2 = seq(self.expt_expr())?; - return self.mul_expr_fold(e1.div(e2)); + let n1 = self.eval(n, 1); + self.stack.push(Op::Op { + prec: 1, + eval: Box::new(move |n2| n1.div(n2)), + }); + return; } if self.symbol("//") { - let e2 = seq(self.expt_expr())?; - return self.mul_expr_fold(e1.int_div(e2)); + let n1 = self.eval(n, 1); + self.stack.push(Op::Op { + prec: 1, + eval: Box::new(move |n2| n1.int_div(n2)), + }); + return; } if self.symbol("%") { - let e2 = seq(self.expt_expr())?; - return self.mul_expr_fold(e1.modulo(e2)); - } - // Allow implicit multiplication - if let Some(e2) = or(self.expt_expr_no_num())? { - return self.mul_expr_fold(e1.mul(e2)); + let n1 = self.eval(n, 1); + self.stack.push(Op::Op { + prec: 1, + eval: Box::new(move |n2| n1.modulo(n2)), + }); + return; } - Ok(e1) - } - - fn mul_expr(&mut self) -> Result<Num, ParseError> { - let n = self.expt_expr()?; - self.mul_expr_fold(n) - } - - fn add_expr_fold(&mut self, e1: Num) -> Result<Num, ParseError> { if self.symbol("+") { - let e2 = seq(self.mul_expr())?; - let e = e1.add(e2); - return self.add_expr_fold(e); + let n1 = self.eval(n, 0); + self.stack.push(Op::Op { + prec: 0, + eval: Box::new(move |n2| n1.add(n2)), + }); + return; } if self.symbol("-") { - let e2 = seq(self.mul_expr())?; - let e = e1.sub(e2); - return self.add_expr_fold(e); + let n1 = self.eval(n, 0); + self.stack.push(Op::Op { + prec: 0, + eval: Box::new(move |n2| n1.sub(n2)), + }); + return; } - Ok(e1) + let n1 = self.eval(n, 1); + self.stack.push(Op::Op { + prec: 1, + eval: Box::new(move |n2| n1.mul(n2)), + }); } - fn expr(&mut self) -> Result<Num, ParseError> { - let n = self.mul_expr()?; - self.add_expr_fold(n) + fn parse(&mut self) -> Option<Num> { + let mut n = loop { + if self.symbol("(") { + self.stack.push(Op::Paren); + continue; + } + if self.parse_fun() { + continue; + } + let mut n = self.parse_const()?; + while self.symbol(")") { + loop { + let op = self.stack.pop()?; + let Op::Op { eval, .. } = op else { + break; + }; + n = eval(n); + } + } + if self.peek().is_none() { + break n; + } + self.parse_op(n); + }; + while let Some(op) = self.stack.pop() { + let Op::Op { eval, .. } = op else { + return None; + }; + n = eval(n); + } + Some(n) } } @@ -239,11 +274,7 @@ pub fn parse(expr: &str) -> Option<Num> { let mut p = Parser { r: Lexer { buf: expr }, first_token: None, + stack: Vec::new(), }; - let n = p.expr().ok()?; - if p.r.next().is_some() { - // Trailing characters. - return None; - } - Some(n) + p.parse() } |