aboutsummaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/parser.rs319
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()
}
generated by cgit v1.3.1 (git 2.54.0) at 2026-09-04 04:27:34 +0000