From 17a76d59cfac2a19f22e28a6582008b667b5106c Mon Sep 17 00:00:00 2001 From: Rose Hogenson Date: Mon, 27 May 2024 19:03:04 -0700 Subject: Fix backtracking in the parser. --- src/parser.rs | 173 ++++++++++++++++++++++++++++++++++------------------------ 1 file changed, 103 insertions(+), 70 deletions(-) (limited to 'src') diff --git a/src/parser.rs b/src/parser.rs index fda744d..0b7bcd8 100644 --- a/src/parser.rs +++ b/src/parser.rs @@ -4,190 +4,218 @@ use crate::num::Num; use num_bigint::BigInt; use std::str::FromStr; +enum ParseError { + Empty, + Consumed, +} + +fn seq(r: Result) -> Result { + match r { + Err(ParseError::Empty) => Err(ParseError::Consumed), + x => x, + } +} + +fn or(r: Result) -> Result, ParseError> { + match r { + Ok(x) => Ok(Some(x)), + Err(ParseError::Empty) => Ok(None), + Err(ParseError::Consumed) => Err(ParseError::Consumed), + } +} + struct Parser<'a> { r: Lexer<'a>, first_token: Option<&'a str>, } impl<'a> Parser<'a> { - fn peek(&mut self) -> Option<&'a str> { + fn peek(&mut self) -> Result<&'a str, ParseError> { if let Some(t) = self.first_token { - return Some(t); + return Ok(t); } - self.first_token = self.r.next(); - self.first_token + let Some(t) = self.r.next() else { + return Err(ParseError::Empty); + }; + self.first_token = Some(t); + Ok(t) } - fn next(&mut self) -> Option<&'a str> { + fn next(&mut self) -> Result<&'a str, ParseError> { if let Some(t) = std::mem::take(&mut self.first_token) { - return Some(t); + return Ok(t); } - self.r.next() + let Some(t) = self.r.next() else { + return Err(ParseError::Empty); + }; + Ok(t) } fn symbol(&mut self, s: &str) -> bool { - let Some(t) = self.peek() else { + let Ok(t) = self.peek() else { return false; }; if t != s { return false; } - self.next(); + let _ = self.next(); true } - fn parse_num(&mut self) -> Option { + fn parse_num(&mut self) -> Result { let negative = self.symbol("-"); - let t = self.next()?; + let t = seq(self.next())?; if t.contains('.') || t.contains('e') || t.contains('E') { - let f = f64::from_str(t).ok()?; + let Ok(f) = f64::from_str(t) else { + return Err(ParseError::Consumed); + }; if negative { - return Some(num::float(-f)); + return Ok(num::float(-f)); } - return Some(num::float(f)); + return Ok(num::float(f)); } - let i = BigInt::from_str(t).ok()?; + let Ok(i) = BigInt::from_str(t) else { + return Err(ParseError::Consumed); + }; if negative { - return Some(num::int(-i)); + return Ok(num::int(-i)); } - Some(num::int(i)) + Ok(num::int(i)) } - fn paren_expr(&mut self) -> Option { + fn paren_expr(&mut self) -> Result { if !self.symbol("(") { - return None; + return Err(ParseError::Empty); } - let n = self.expr()?; + let n = seq(self.expr())?; if !self.symbol(")") { - return None; + return Err(ParseError::Consumed); } - Some(n) + Ok(n) } - fn parse_const(&mut self) -> Option { + fn parse_const(&mut self) -> Result { if self.symbol("e") { - return Some(num::float(std::f64::consts::E)); + return Ok(num::float(std::f64::consts::E)); } if self.symbol("pi") { - return Some(num::float(std::f64::consts::PI)); + return Ok(num::float(std::f64::consts::PI)); } - None + Err(ParseError::Empty) } - fn atom(&mut self) -> Option { - if let Some(n) = self.paren_expr() { - return Some(n); + fn atom(&mut self) -> Result { + if let Some(n) = or(self.paren_expr())? { + return Ok(n); } - if let Some(n) = self.parse_const() { - return Some(n); + if let Some(n) = or(self.parse_const())? { + return Ok(n); } self.parse_num() } - fn parse_fun(&mut self) -> Option { + fn parse_fun(&mut self) -> Result { if self.symbol("sin") { - return Some(self.atom()?.sin()); + return Ok(self.atom()?.sin()); } if self.symbol("cos") { - return Some(self.atom()?.cos()); + return Ok(self.atom()?.cos()); } if self.symbol("tan") { - return Some(self.atom()?.tan()); + return Ok(self.atom()?.tan()); } if self.symbol("sqrt") { - return Some(self.atom()?.sqrt()); + return Ok(self.atom()?.sqrt()); } if self.symbol("log") || self.symbol("ln") { - return Some(self.atom()?.log()); + return Ok(self.atom()?.log()); } if self.symbol("floor") { - return Some(self.atom()?.floor()); + return Ok(self.atom()?.floor()); } if self.symbol("ceil") || self.symbol("ceiling") { - return Some(self.atom()?.ceil()); + return Ok(self.atom()?.ceil()); } if self.symbol("round") { - return Some(self.atom()?.round()); + return Ok(self.atom()?.round()); } - None + Err(ParseError::Empty) } - fn app_expr_fold(&mut self, e1: Num) -> Option { - if let Some(e2) = self.paren_expr() { + fn app_expr_fold(&mut self, e1: Num) -> Result { + if let Some(e2) = or(self.parse_fun())? { return self.app_expr_fold(e1.mul(e2)); } - if let Some(e2) = self.parse_const() { + if let Some(e2) = or(self.paren_expr())? { return self.app_expr_fold(e1.mul(e2)); } - if let Some(e2) = self.parse_fun() { - return Some(e1.mul(e2)); + if let Some(e2) = or(self.parse_const())? { + return self.app_expr_fold(e1.mul(e2)); } - Some(e1) + Ok(e1) } - fn app_expr(&mut self) -> Option { - if let Some(e) = self.parse_fun() { - return Some(e); + fn app_expr(&mut self) -> Result { + if let Some(e1) = or(self.parse_fun())? { + return Ok(e1); } let e1 = self.atom()?; self.app_expr_fold(e1) } - fn expt_expr_fold(&mut self, e1: Num) -> Option { + fn expt_expr_fold(&mut self, e1: Num) -> Result { if !self.symbol("^") { - return Some(e1); - } - let e2 = self.app_expr()?; - if let Some(e2) = self.expt_expr_fold(e2) { - return Some(e1.pow(e2)); + return Ok(e1); } - None + let e2 = seq(self.app_expr())?; + let e2 = self.expt_expr_fold(e2)?; + Ok(e1.pow(e2)) } - fn expt_expr(&mut self) -> Option { + fn expt_expr(&mut self) -> Result { let n = self.app_expr()?; self.expt_expr_fold(n) } - fn mul_expr_fold(&mut self, e1: Num) -> Option { + fn mul_expr_fold(&mut self, e1: Num) -> Result { if self.symbol("*") { - let e2 = self.expt_expr()?; + let e2 = seq(self.expt_expr())?; let e = e1.mul(e2); return self.mul_expr_fold(e); } if self.symbol("/") { - let e2 = self.expt_expr()?; + let e2 = seq(self.expt_expr())?; let e = e1.div(e2); return self.mul_expr_fold(e); } if self.symbol("//") { - let e2 = self.expt_expr()?; + let e2 = seq(self.expt_expr())?; let e = e1.int_div(e2); return self.mul_expr_fold(e); } - Some(e1) + Ok(e1) } - fn mul_expr(&mut self) -> Option { + fn mul_expr(&mut self) -> Result { let n = self.expt_expr()?; self.mul_expr_fold(n) } - fn add_expr_fold(&mut self, e1: Num) -> Option { + fn add_expr_fold(&mut self, e1: Num) -> Result { if self.symbol("+") { - let e2 = self.mul_expr()?; + let e2 = seq(self.mul_expr())?; let e = e1.add(e2); return self.add_expr_fold(e); } if self.symbol("-") { - let e2 = self.mul_expr()?; + let e2 = seq(self.mul_expr())?; let e = e1.sub(e2); return self.add_expr_fold(e); } - Some(e1) + Ok(e1) } - fn expr(&mut self) -> Option { + fn expr(&mut self) -> Result { let n = self.mul_expr()?; self.add_expr_fold(n) } @@ -198,5 +226,10 @@ pub fn parse(expr: &str) -> Option { r: Lexer { buf: expr }, first_token: None, }; - p.expr() + let n = p.expr().ok()?; + if p.r.next().is_some() { + // Trailing characters. + return None; + } + Some(n) } -- cgit v1.3.1