aboutsummaryrefslogtreecommitdiffstats
path: root/src/parser.rs
diff options
context:
space:
mode:
Diffstat (limited to 'src/parser.rs')
-rw-r--r--src/parser.rs258
1 files changed, 167 insertions, 91 deletions
diff --git a/src/parser.rs b/src/parser.rs
index 6eeb9d8..4cd75be 100644
--- a/src/parser.rs
+++ b/src/parser.rs
@@ -1,18 +1,20 @@
use crate::eval::Num;
-use crate::expr::{BinOp, Expr, UnOp};
use crate::lexer::Lexer;
+use crate::op::{BinOp, Op, UnOp};
use std::str::FromStr;
-enum Op {
+enum Pending {
Paren,
Un(UnOp),
- Bin(BinOp, Expr),
+ Bin(BinOp),
}
struct Parser<'a> {
r: Lexer<'a>,
first_token: Option<&'a str>,
- stack: Vec<Op>,
+ // stack stores the pending operations that can't be flushed yet.
+ stack: Vec<Pending>,
+ result: Vec<Op>,
}
impl<'a> Parser<'a> {
@@ -43,89 +45,93 @@ impl<'a> Parser<'a> {
true
}
- fn parse_num(&mut self) -> Option<Num> {
+ fn parse_num(&mut self) -> Option<()> {
let t = self.next()?;
if t.contains('.') || t.contains('e') || t.contains('E') {
let Ok(f) = f64::from_str(t) else {
return None;
};
- return Some(Num::Float(f));
+ self.result.push(Op::Num(Num::Float(f)));
+ return Some(());
}
let Ok(i) = i128::from_str(t) else {
return None;
};
- Some(Num::Int(i))
+ self.result.push(Op::Num(Num::Int(i)));
+ Some(())
}
- fn parse_const(&mut self) -> Option<Num> {
+ fn parse_const(&mut self) -> Option<()> {
if self.symbol("e") {
- return Some(Num::Float(std::f64::consts::E));
+ self.result.push(Op::Num(Num::Float(std::f64::consts::E)));
+ return Some(());
}
if self.symbol("pi") {
- return Some(Num::Float(std::f64::consts::PI));
+ self.result.push(Op::Num(Num::Float(std::f64::consts::PI)));
+ return Some(());
}
self.parse_num()
}
fn parse_fun(&mut self) -> bool {
if self.symbol("-") {
- self.stack.push(Op::Un(UnOp::Neg));
+ self.stack.push(Pending::Un(UnOp::Neg));
return true;
}
if self.symbol("sin") {
- self.stack.push(Op::Un(UnOp::Sin));
+ self.stack.push(Pending::Un(UnOp::Sin));
return true;
}
if self.symbol("cos") {
- self.stack.push(Op::Un(UnOp::Cos));
+ self.stack.push(Pending::Un(UnOp::Cos));
return true;
}
if self.symbol("tan") {
- self.stack.push(Op::Un(UnOp::Tan));
+ self.stack.push(Pending::Un(UnOp::Tan));
return true;
}
if self.symbol("asin") || self.symbol("arcsin") {
- self.stack.push(Op::Un(UnOp::Asin));
+ self.stack.push(Pending::Un(UnOp::Asin));
return true;
}
if self.symbol("acos") || self.symbol("arccos") {
- self.stack.push(Op::Un(UnOp::Acos));
+ self.stack.push(Pending::Un(UnOp::Acos));
return true;
}
if self.symbol("atan") || self.symbol("arctan") {
- self.stack.push(Op::Un(UnOp::Atan));
+ self.stack.push(Pending::Un(UnOp::Atan));
return true;
}
if self.symbol("sqrt") {
- self.stack.push(Op::Un(UnOp::Sqrt));
+ self.stack.push(Pending::Un(UnOp::Sqrt));
return true;
}
if self.symbol("log") || self.symbol("ln") {
- self.stack.push(Op::Un(UnOp::Log));
+ self.stack.push(Pending::Un(UnOp::Log));
return true;
}
if self.symbol("log10") {
- self.stack.push(Op::Un(UnOp::Log10));
+ self.stack.push(Pending::Un(UnOp::Log10));
return true;
}
if self.symbol("log2") {
- self.stack.push(Op::Un(UnOp::Log2));
+ self.stack.push(Pending::Un(UnOp::Log2));
return true;
}
if self.symbol("floor") {
- self.stack.push(Op::Un(UnOp::Floor));
+ self.stack.push(Pending::Un(UnOp::Floor));
return true;
}
if self.symbol("ceil") || self.symbol("ceiling") {
- self.stack.push(Op::Un(UnOp::Ceil));
+ self.stack.push(Pending::Un(UnOp::Ceil));
return true;
}
if self.symbol("round") {
- self.stack.push(Op::Un(UnOp::Round));
+ self.stack.push(Pending::Un(UnOp::Round));
return true;
}
if self.symbol("abs") {
- self.stack.push(Op::Un(UnOp::Abs));
+ self.stack.push(Pending::Un(UnOp::Abs));
return true;
}
false
@@ -145,134 +151,135 @@ fn prec(op: BinOp) -> i8 {
}
impl<'a> Parser<'a> {
- fn eval(&mut self, e: Expr, target_prec: i8) -> Expr {
- let mut e = e;
+ fn flush(&mut self, target_prec: i8) {
loop {
match self.stack.last() {
- None | Some(Op::Paren) => break,
- Some(Op::Bin(op, _)) if prec(*op) < target_prec => break,
+ None | Some(Pending::Paren) => break,
+ Some(Pending::Bin(op)) if prec(*op) < target_prec => break,
_ => (),
}
match self.stack.pop().unwrap() {
- Op::Un(op) => e = op.expr(e),
- Op::Bin(op, e1) => e = op.expr(e1, e),
- Op::Paren => unreachable!(),
+ Pending::Un(op) => self.result.push(Op::Un(op)),
+ Pending::Bin(op) => self.result.push(Op::Bin(op)),
+ Pending::Paren => unreachable!(),
}
}
- e
}
- fn parse_op(&mut self, e: Expr) {
+ fn parse_op(&mut self) {
if self.symbol("^") {
- let e = self.eval(e, 3);
- self.stack.push(Op::Bin(BinOp::Pow, e));
+ self.flush(3);
+ self.stack.push(Pending::Bin(BinOp::Pow));
return;
}
if self.symbol("*") {
- let e = self.eval(e, 1);
- self.stack.push(Op::Bin(BinOp::Mul, e));
+ self.flush(1);
+ self.stack.push(Pending::Bin(BinOp::Mul));
return;
}
if self.symbol("/") {
- let e = self.eval(e, 1);
- self.stack.push(Op::Bin(BinOp::Div, e));
+ self.flush(1);
+ self.stack.push(Pending::Bin(BinOp::Div));
return;
}
if self.symbol("//") {
- let e = self.eval(e, 1);
- self.stack.push(Op::Bin(BinOp::IntDiv, e));
+ self.flush(1);
+ self.stack.push(Pending::Bin(BinOp::IntDiv));
return;
}
if self.symbol("%") {
- let e = self.eval(e, 1);
- self.stack.push(Op::Bin(BinOp::Mod, e));
+ self.flush(1);
+ self.stack.push(Pending::Bin(BinOp::Mod));
return;
}
if self.symbol("+") {
- let e = self.eval(e, 0);
- self.stack.push(Op::Bin(BinOp::Add, e));
+ self.flush(0);
+ self.stack.push(Pending::Bin(BinOp::Add));
return;
}
if self.symbol("-") {
- let e = self.eval(e, 0);
- self.stack.push(Op::Bin(BinOp::Sub, e));
+ self.flush(0);
+ self.stack.push(Pending::Bin(BinOp::Sub));
return;
}
- let e = self.eval(e, 1);
- self.stack.push(Op::Bin(BinOp::Mul, e));
+ self.flush(1);
+ self.stack.push(Pending::Bin(BinOp::Mul));
}
- fn parse(&mut self) -> Option<Expr> {
- let mut e = loop {
+ fn parse(&mut self) -> Option<()> {
+ loop {
if self.symbol("(") {
- self.stack.push(Op::Paren);
+ self.stack.push(Pending::Paren);
continue;
}
if self.parse_fun() {
continue;
}
- let mut e = Expr::Num(self.parse_const()?);
+ self.parse_const()?;
while self.symbol(")") {
loop {
match self.stack.pop()? {
- Op::Un(op) => e = op.expr(e),
- Op::Bin(op, e1) => e = op.expr(e1, e),
- Op::Paren => break,
+ Pending::Un(op) => self.result.push(Op::Un(op)),
+ Pending::Bin(op) => self.result.push(Op::Bin(op)),
+ Pending::Paren => break,
}
}
}
if self.peek().is_none() {
- break e;
+ break;
}
- self.parse_op(e);
- };
+ self.parse_op();
+ }
loop {
match self.stack.pop() {
- Some(Op::Paren) => return None,
- Some(Op::Un(op)) => e = op.expr(e),
- Some(Op::Bin(op, e1)) => e = op.expr(e1, e),
- None => return Some(e),
+ Some(Pending::Paren) => return None,
+ Some(Pending::Un(op)) => self.result.push(Op::Un(op)),
+ Some(Pending::Bin(op)) => self.result.push(Op::Bin(op)),
+ None => return Some(()),
}
}
}
}
-pub fn parse(expr: &str) -> Option<Expr> {
+// parse turns an expression into bytecode.
+pub fn parse(expr: &str) -> Option<Vec<Op>> {
let mut p = Parser {
r: Lexer { buf: expr },
first_token: None,
stack: Vec::new(),
+ result: Vec::new(),
};
- p.parse()
+ p.parse()?;
+ Some(p.result)
}
#[cfg(test)]
mod tests {
use super::*;
- fn int(i: i128) -> Expr {
- Expr::Num(Num::Int(i))
+ fn int(i: i128) -> Op {
+ Op::Num(Num::Int(i))
}
- fn float(f: f64) -> Expr {
- Expr::Num(Num::Float(f))
+ fn float(f: f64) -> Op {
+ Op::Num(Num::Float(f))
}
#[test]
fn parse_int() {
- assert_eq!(parse("500"), Some(int(500)));
+ assert_eq!(parse("500"), Some(vec![int(500)]));
}
#[test]
fn parse_float() {
- assert_eq!(parse("1e2"), Some(float(100.)));
+ assert_eq!(parse("1e2"), Some(vec![float(100.)]));
}
#[test]
fn parse_fun() {
assert_eq!(
parse("sin pi"),
- Some(UnOp::Sin.expr(float(std::f64::consts::PI)))
+ Some(vec![float(std::f64::consts::PI), Op::Un(UnOp::Sin)])
);
}
@@ -280,7 +287,7 @@ mod tests {
fn parse_nested_fun() {
assert_eq!(
parse("log log 100"),
- Some(UnOp::Log.expr(UnOp::Log.expr(int(100))))
+ Some(vec![int(100), Op::Un(UnOp::Log), Op::Un(UnOp::Log)])
);
}
@@ -288,7 +295,13 @@ mod tests {
fn parse_power() {
assert_eq!(
parse("2^1^2"),
- Some(BinOp::Pow.expr(int(2), BinOp::Pow.expr(int(1), int(2))))
+ Some(vec![
+ int(2),
+ int(1),
+ int(2),
+ Op::Bin(BinOp::Pow),
+ Op::Bin(BinOp::Pow)
+ ])
);
}
@@ -296,7 +309,7 @@ mod tests {
fn parse_fun_power() {
assert_eq!(
parse("log 2^2"),
- Some(BinOp::Pow.expr(UnOp::Log.expr(int(2)), int(2)))
+ Some(vec![int(2), Op::Un(UnOp::Log), int(2), Op::Bin(BinOp::Pow)])
);
}
@@ -304,7 +317,7 @@ mod tests {
fn parse_power_fun() {
assert_eq!(
parse("2^log 2"),
- Some(BinOp::Pow.expr(int(2), UnOp::Log.expr(int(2))))
+ Some(vec![int(2), int(2), Op::Un(UnOp::Log), Op::Bin(BinOp::Pow)])
);
}
@@ -312,7 +325,13 @@ mod tests {
fn parse_pow_mul() {
assert_eq!(
parse("2^2*2"),
- Some(BinOp::Mul.expr(BinOp::Pow.expr(int(2), int(2)), int(2)))
+ Some(vec![
+ int(2),
+ int(2),
+ Op::Bin(BinOp::Pow),
+ int(2),
+ Op::Bin(BinOp::Mul)
+ ])
);
}
@@ -320,7 +339,13 @@ mod tests {
fn parse_mul_pow() {
assert_eq!(
parse("2*2^2"),
- Some(BinOp::Mul.expr(int(2), BinOp::Pow.expr(int(2), int(2))))
+ Some(vec![
+ int(2),
+ int(2),
+ int(2),
+ Op::Bin(BinOp::Pow),
+ Op::Bin(BinOp::Mul)
+ ])
);
}
@@ -328,7 +353,13 @@ mod tests {
fn parse_mul_div() {
assert_eq!(
parse("2*2/2"),
- Some(BinOp::Div.expr(BinOp::Mul.expr(int(2), int(2)), int(2)))
+ Some(vec![
+ int(2),
+ int(2),
+ Op::Bin(BinOp::Mul),
+ int(2),
+ Op::Bin(BinOp::Div)
+ ])
);
}
@@ -336,7 +367,13 @@ mod tests {
fn parse_add_mul() {
assert_eq!(
parse("2+2*2"),
- Some(BinOp::Add.expr(int(2), BinOp::Mul.expr(int(2), int(2))))
+ Some(vec![
+ int(2),
+ int(2),
+ int(2),
+ Op::Bin(BinOp::Mul),
+ Op::Bin(BinOp::Add)
+ ])
);
}
@@ -344,7 +381,13 @@ mod tests {
fn parse_mul_add() {
assert_eq!(
parse("2*2+2"),
- Some(BinOp::Add.expr(BinOp::Mul.expr(int(2), int(2)), int(2)))
+ Some(vec![
+ int(2),
+ int(2),
+ Op::Bin(BinOp::Mul),
+ int(2),
+ Op::Bin(BinOp::Add)
+ ])
);
}
@@ -352,7 +395,7 @@ mod tests {
fn parse_fun_add() {
assert_eq!(
parse("log 2+2"),
- Some(BinOp::Add.expr(UnOp::Log.expr(int(2)), int(2))),
+ Some(vec![int(2), Op::Un(UnOp::Log), int(2), Op::Bin(BinOp::Add)])
);
}
@@ -360,7 +403,13 @@ mod tests {
fn parse_parens() {
assert_eq!(
parse("(1+2)*3"),
- Some(BinOp::Mul.expr(BinOp::Add.expr(int(1), int(2)), int(3)))
+ Some(vec![
+ int(1),
+ int(2),
+ Op::Bin(BinOp::Add),
+ int(3),
+ Op::Bin(BinOp::Mul)
+ ])
);
}
@@ -368,7 +417,11 @@ mod tests {
fn parse_implicit_multiplication() {
assert_eq!(
parse("2pi"),
- Some(BinOp::Mul.expr(int(2), float(std::f64::consts::PI))),
+ Some(vec![
+ int(2),
+ float(std::f64::consts::PI),
+ Op::Bin(BinOp::Mul)
+ ])
);
}
@@ -376,7 +429,14 @@ mod tests {
fn parse_implicit_multiplication_neg() {
assert_eq!(
parse("-2 2 -2"),
- Some(BinOp::Sub.expr(BinOp::Mul.expr(UnOp::Neg.expr(int(2)), int(2)), int(2)))
+ Some(vec![
+ int(2),
+ Op::Un(UnOp::Neg),
+ int(2),
+ Op::Bin(BinOp::Mul),
+ int(2),
+ Op::Bin(BinOp::Sub)
+ ])
);
}
@@ -384,7 +444,12 @@ mod tests {
fn parse_fun_implicit_multiplication() {
assert_eq!(
parse("sin 2pi"),
- Some(BinOp::Mul.expr(UnOp::Sin.expr(int(2)), float(std::f64::consts::PI))),
+ Some(vec![
+ int(2),
+ Op::Un(UnOp::Sin),
+ float(std::f64::consts::PI),
+ Op::Bin(BinOp::Mul)
+ ])
);
}
@@ -392,7 +457,13 @@ mod tests {
fn parse_unary_negate() {
assert_eq!(
parse("1---2"),
- Some(BinOp::Sub.expr(int(1), UnOp::Neg.expr(UnOp::Neg.expr(int(2)))))
+ Some(vec![
+ int(1),
+ int(2),
+ Op::Un(UnOp::Neg),
+ Op::Un(UnOp::Neg),
+ Op::Bin(BinOp::Sub)
+ ])
);
}
@@ -400,17 +471,22 @@ mod tests {
fn parse_negate_fun() {
assert_eq!(
parse("log-log 2"),
- Some(UnOp::Log.expr(UnOp::Neg.expr(UnOp::Log.expr(int(2)))))
+ Some(vec![
+ int(2),
+ Op::Un(UnOp::Log),
+ Op::Un(UnOp::Neg),
+ Op::Un(UnOp::Log)
+ ])
);
}
#[test]
fn parse_unmatched_parens() {
- assert_eq!(parse("0))))"), None,);
+ assert_eq!(parse("0))))"), None);
}
#[test]
fn parse_unmatched_op() {
- assert_eq!(parse("2^2+"), None,);
+ assert_eq!(parse("2^2+"), None);
}
}
generated by cgit v1.3.1 (git 2.54.0) at 2026-09-04 04:20:43 +0000