use lexington::{Lexer,Match,Matcher,Scanner,Within}; use lexington::{ShiftReduceParser,ShiftReduceRule}; use Expr::*; use PartExpr::*; /// A simple definition of the components of a polynomial. #[derive(Copy,Clone,Debug,PartialEq)] enum Kind { LeftBrace, RightBrace, Plus, Star, Number, Identifier, Eof } /// A simple definition of a polynomial expression. #[derive(Clone,Debug,PartialEq)] enum Expr<'a> { // An integer coefficient Int(isize), // A variable Var(&'a str), // A sum e1 + .. + en Sum(Vec>), // A product e1 * .. * .. en Product(Vec>), } impl<'a> Expr<'a> { // Swap out self with dummy pub fn take(&mut self) -> Expr<'a> { let mut res : Expr<'a> = Int(0); // Swap out e with dummy value std::mem::swap(self,&mut res); // res } } /// A partial expression respresents an expression which is /// potentially in the process of being parsed (i.e. may not have beeN- /// fully parsed yet). #[derive(Clone,Debug,PartialEq)] enum PartExpr<'a> { // Indicates an expression is expected, but nothing has yet been // parsed for it. Empty, // Indicates parsing an expression has begun, but is not yet // closed (i.e. completed). Open(Expr<'a>), // Indicates an expression for which parsing has completed. Closed(Expr<'a>) } impl<'a> PartExpr<'a> { // Unwrap partial expression as a completed (i.e. closed) // expression. This can fail if `self` is not, in fact, closed. fn unwrap(self) -> Expr<'a> { match self { Closed(t) => t, _ => { panic!("cannot unwrap incomplete expression"); } } } // Close this expression (assuming it is open). fn close(self) -> PartExpr<'a> { match self { Open(t) => Closed(t), _ => self } } // Evolve partial expression into a sum. Note that, in some // cases, this evolution should be prevented. For example, a // product cannot evolve into a sum as that represents an // ambiguous expression such as `x*y+z` which we choose to // prohibit. fn into_sum(&mut self) -> Result { match self { // Sum is already a sum Open(Sum(_)) => Ok(true), // Close expression becomes sum Closed(e) => { *self = Open(Sum(vec![e.take()])); Ok(true)} // Otherwise, rule does not apply _ => Ok(false) } } // Evolve partial expression into a product. Note that, in some // cases, this evolution should be prevented. For example, a sum // cannot evolve into a product as that represents an ambiguous // expression such as `x*y+z` which we choose to prohibit. fn into_product(&mut self) -> Result { match self { // Product is already a sum Open(Product(_)) => Ok(true), // Close expression becomes product Closed(e) => { *self = Open(Product(vec![e.take()])); Ok(true)} // Otherwise, rule does not apply _ => Ok(false) } } } fn scanner() -> impl Scanner { // [0..9]+ let number = Within('0'..='9').one_or_more(); // [a..zA..Z_]([0..9a..zA..Z_]*) let identifier_start = Within('a'..='z') .or(Within('A'..='Z')).or('_'); let identifier_rest = Within('0'..='9').or(Within('a'..='z')) .or(Within('A'..='Z')).or('_').zero_or_more(); let identifier = identifier_start.then(identifier_rest); // Construct scanner Match(number,Kind::Number) .and_match(identifier,Kind::Identifier) .and_match('+',Kind::Plus) .and_match('*',Kind::Star) .and_match('(',Kind::LeftBrace) .and_match(')',Kind::RightBrace) .eof(Kind::Eof) } fn parse<'a>(input: &'a str) -> Result,()> { let scanner = scanner(); // Construct Lexer let lexer = Lexer::new(input,scanner); // Rule for combining s-expressions let reduction_rule = |mut l:PartExpr<'a>,r:PartExpr<'a>| { match (&mut l,&r) { (Empty,_) => Ok(r), (Open(Sum(es)),_) => { es.push(r.unwrap()); Ok(l) } (Open(Product(es)),_) => { es.push(r.unwrap()); Ok(l) } (_,_) => todo!("Reducing {l:?} <= {r:?})") } }; // Rule for parsing strings into numbers let st = ShiftReduceParser::new() .apply(reduction_rule) .terminate(Kind::Number,|tok| Closed(Int(input[tok.range()].parse().unwrap()))) .terminate(Kind::Identifier,|tok| Closed(Var(&input[tok.range()]))) .update_as(Kind::Plus, |t| t.into_sum()) .update_as(Kind::Star, |t| t.into_product()) .open(Kind::LeftBrace, Empty) .close_with(Kind::RightBrace, |e| e.close()) .close_with(Kind::Eof, |e| e.close()) .first(Empty) .parse(lexer)?; // Extract the term Ok(st.unwrap()) } fn check_ok(input: &str, expecting: Expr) { // Parse tokens into expression let actual = parse(input).unwrap(); // Check what we got assert_eq!(actual,expecting); } #[test] fn arith_01() { check_ok("x",Var("x")); } #[test] fn arith_02() { check_ok("(x)",Var("x")); } #[test] fn arith_03() { check_ok("123",Int(123)); } #[test] fn arith_04() { check_ok("(123)",Int(123)); } #[test] fn arith_05() { check_ok("x+1",Sum(vec![Var("x"),Int(1)])); } #[test] fn arith_06() { check_ok("1+x",Sum(vec![Int(1),Var("x")])); } #[test] fn arith_07() { check_ok("x+y",Sum(vec![Var("x"),Var("y")])); } #[test] fn arith_08() { check_ok("1+x+y",Sum(vec![Int(1),Var("x"),Var("y")])); } #[test] fn arith_09() { check_ok("x+2+y",Sum(vec![Var("x"),Int(2),Var("y")])); } #[test] fn arith_10() { check_ok("x+y+z",Sum(vec![Var("x"),Var("y"),Var("z")])); } #[test] fn arith_11() { check_ok("x*1",Product(vec![Var("x"),Int(1)])); } #[test] fn arith_12() { check_ok("1*x",Product(vec![Int(1),Var("x")])); } #[test] fn arith_13() { check_ok("x*y",Product(vec![Var("x"),Var("y")])); } #[test] fn arith_14() { check_ok("(x+1)*y",Product(vec![Sum(vec![Var("x"),Int(1)]),Var("y")])); } #[test] fn arith_15() { check_ok("x*(y+1)",Product(vec![Var("x"),Sum(vec![Var("y"),Int(1)])])); } // #[test] // fn arith_16() { // check_err("x*y+1",Sum(vec![Product(vec![Var("x"),Var("y")]),Int(1)])); // } // #[test] // fn arith_17() { // check_ok("1*x*y+1",Sum(vec![Product(vec![Var("x"),Var("y")]),Int(1)])); // } // #[test] // fn arith_18() { // check_ok("x+y*1",Sum(vec![Product(vec![Var("x"),Var("y")]),Int(1)])); // } // #[test] // fn arith_19() { // check_ok("1+x+y*1",Sum(vec![Product(vec![Var("x"),Var("y")]),Int(1)])); // }