use crate::lisp::{ error::LispError, lex::{Lexer, Span, Token}, number::LispNumber, LispExpr, }; pub struct Parser<'lex> { lexer: Lexer<'lex>, cur_token: Option<(Span, Token<'lex>)>, } // pub struct ParseError { // pub span: Span, // pub kind: ParseErrorKind, // } // // pub enum ParseErrorKind { // InvalidLiteral, // InvalidToken, // LiteralParseError, // MissingCloseParen, // UnbalancedComma, // UnexpectedEof, // UnexpectedToken { // expected: &'static str, // found: &'static str, // }, // UnmatchedParen, // UnterminatedString, // } 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( || LispError::ParseError, // unmatched paren here )?; match group { Group::Parens(v) => Ok(LispExpr::List(v)), _ => Err(LispError::ParseError), } } Token::Float(f) => f .parse::() .map(|n| LispExpr::Number(LispNumber::Float(n))) .map_err(|_| LispError::ParseError), Token::Integer(i) => i .parse::() .map(|n| LispExpr::Number(LispNumber::Integer(n))) .map_err(|_| LispError::ParseError), Token::String(s) => Ok(LispExpr::StringLit(s.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(LispError::ParseError); // unbalanced comma } 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(LispError::ParseError); // unbalanced comma } 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(LispError::ParseError) // unbalanced paren } else { Err(LispError::ParseError) // unexpected eof } } }; 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), _ => Err(LispError::ParseError), // too many tokens } } 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(); } }