use crate::lisp::{ error::{LispError, ParseError, ParseErrorKind}, lex::{Lexer, Span, Token}, number::LispNumber, LispExpr, }; pub struct Parser<'lex> { lexer: Lexer<'lex>, cur_token: Option<(Span, Token<'lex>)>, } enum Group { Backticks(i32), CommaAt, Quotes(u32), Parens(Vec), } impl<'lex> Parser<'lex> { pub fn new(lexer: Lexer<'lex>) -> Self { Self { lexer, cur_token: None, } } pub fn parse_expr(&mut self) -> Result { let mut stack = Vec::new(); let mut total_backticks = 0; loop { let (span, token) = self.next()?; let r: Result = match token { Token::LeftParen => { stack.push(Group::Parens(Vec::new())); continue; } Token::RightParen => { let group = stack.pop().ok_or_else( || (ParseError::new(span, ParseErrorKind::UnmatchedParen)), // unmatched paren here )?; match group { Group::Parens(v) => Ok(LispExpr::List(v)), _ => Err(From::from(ParseError::new( span, ParseErrorKind::UnexpectedToken { expected: "expression", found: "(", }, ))), } } Token::Float(f) => f .parse::() .map(|n| LispExpr::Number(LispNumber::Float(n))) .map_err(|_| ParseError::new(span, ParseErrorKind::LiteralParseError).into()), Token::Integer(i) => i .parse::() .map(|n| LispExpr::Number(LispNumber::Integer(n))) .map_err(|_| ParseError::new(span, ParseErrorKind::LiteralParseError).into()), Token::String(s) => Ok(LispExpr::StringLit(s[1..s.len() - 1].into())), Token::Char(s) => Ok(LispExpr::Char(s.chars().nth(2).ok_or_else( || -> LispError { ParseError::new(span, ParseErrorKind::LiteralParseError).into() }, )?)), Token::Name(n) => Ok(name_expr(n)), Token::BackQuote => { total_backticks += 1; if let Some(&mut Group::Backticks(ref mut n)) = stack.last_mut() { *n += 1; continue; } stack.push(Group::Backticks(1)); continue; } Token::Comma => { if total_backticks <= 0 { return Err(ParseError::new(span, ParseErrorKind::UnbalancedComma).into()); } total_backticks -= 1; if let Some(&mut Group::Backticks(ref mut n)) = stack.last_mut() { *n -= 1; continue; } stack.push(Group::Backticks(-1)); continue; } Token::CommaAt => { if total_backticks <= 0 { return Err(ParseError::new(span, ParseErrorKind::UnbalancedComma).into()); } total_backticks -= 1; stack.push(Group::CommaAt); continue; } Token::Quote => { if let Some(&mut Group::Quotes(ref mut n)) = stack.last_mut() { *n += 1; continue; } stack.push(Group::Quotes(1)); continue; } Token::End => { let any_paren = stack.iter().any(|group| match *group { Group::Parens(_) => true, _ => false, }); if any_paren { Err(ParseError::new(span, ParseErrorKind::MissingCloseParen).into()) } else { Err(ParseError::new(span, ParseErrorKind::UnexpectedEof).into()) } } }; let mut v = r?; loop { match stack.last_mut() { None => return Ok(v), Some(&mut Group::Parens(ref mut values)) => { values.push(v); break; } _ => (), } let group = stack.pop().unwrap(); match group { Group::Backticks(n) if n > 0 => { total_backticks -= n; v = v.quasiquote(n as u32); } Group::Backticks(n) if n < 0 => { total_backticks -= n; v = v.comma((-n) as u32); } Group::CommaAt => { total_backticks += 1; v = v.comma_at(1); } Group::Quotes(n) => v = v.quote(n), _ => (), } } } } fn next(&mut self) -> Result<(Span, Token<'lex>), LispError> { let r = self.peek()?; self.cur_token = None; Ok(r) } fn peek(&mut self) -> Result<(Span, Token<'lex>), LispError> { if let Some(tok) = self.cur_token { Ok(tok) } else { let tok = self.lexer.next_token()?; self.cur_token = Some(tok); Ok(tok) } } pub fn parse_single_expr(&mut self) -> Result { let expr = self.parse_expr()?; match self.next()? { (_, Token::End) => Ok(expr), (span, token) => Err(ParseError::new( span, ParseErrorKind::UnexpectedToken { expected: "EOF", found: token.name(), }, ) .into()), } } pub fn parse_exprs(&mut self) -> Result, LispError> { let mut res = Vec::new(); loop { match self.peek()? { (_, Token::End) => break, _ => res.push(self.parse_expr()?), } } Ok(res) } } fn name_expr(input: &str) -> LispExpr { match input { "#t" => LispExpr::BoolLit(true), "#f" => LispExpr::BoolLit(false), _ => LispExpr::Ident(input.into()), } } #[cfg(test)] mod tests { use super::*; fn parse(input: &str) -> Result { let mut parser = Parser::new(Lexer::new(input, 0)); parser.parse_single_expr() } #[test] // fn parse_lisp_expr() { // assert_eq!( // parse("1.5").unwrap(), // LispExpr::Number(LispNumber::Float(1.5)) // ); // assert_eq!( // parse(r#""hello""#).unwrap(), // LispExpr::StringLit(r#""hello""#.into()) // ); // assert_eq!(parse("foo").unwrap(), LispExpr::Ident("foo".into())); // let items = (1..=5) // .map(LispNumber::Integer) // .map(LispExpr::Number) // .collect::>(); // assert_eq!(parse("(1 2 3 4 5)").unwrap(), LispExpr::List(items)); // let foo = LispExpr::Ident("foo".into()); // let bar = LispExpr::Comma(Box::new(LispExpr::Ident("bar".into())), 1); // assert_eq!( // parse("`(foo ,bar)").unwrap(), // LispExpr::Quasiquote(Box::new(LispExpr::List(vec![foo, bar])), 1) // ) // } #[should_panic] #[test] fn unbalanced_comma() { parse("`(foo ,,bar)").unwrap(); } #[should_panic] #[test] fn unbalanced_paren() { parse("(foo").unwrap(); } }