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)))?; match group { Group::Parens(v) => { if v.len() == 0 { Ok(LispExpr::Unit) } else { 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(|| { ParseError::new(span, ParseErrorKind::LiteralParseError) })?)) } 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)); } 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)); } 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)) } else { Err(ParseError::new(span, ParseErrorKind::UnexpectedEof)) } } }; 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>), ParseError> { let r = self.peek()?; self.cur_token = None; Ok(r) } fn peek(&mut self) -> Result<(Span, Token<'lex>), ParseError> { 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, ParseError> { 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("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(); } }