Implemented tokens_to_ast. On second thought we should've just parsed the code straight to ast without tokenization (implementing a parser on tokens was such a pain...)

1 files changed, 111 insertions, 7 deletions

diff --git a/src/parse/parsetree.rs b/src/parse/parsetree.rs
index 6d59cf1..46317a4 100644
--- a/src/parse/parsetree.rs
+++ b/src/parse/parsetree.rs
@@ -1,4 +1,5 @@
 
+use std::iter;
 use nom::{
     IResult,
     Parser,
@@ -11,7 +12,7 @@ use nom::{
 use crate::sexp::{SExp, SExp::*, SLeaf::*, util::*};
 
 
-#[derive(Debug,PartialEq)]
+#[derive(Debug,PartialEq,Clone)]
 pub enum Token {
     ParOpen,
     ParClose,
@@ -20,6 +21,33 @@ pub enum Token {
     Whitespace(String),
 }
 
+impl Token {
+    fn same_variant(&self, other: Token) -> bool {
+	match (self, other) {
+	    (ParOpen, ParOpen) => true,
+	    (ParClose, ParClose) => true,
+	    (Num(_), Num(_)) => true,
+	    (Sym(_), Sym(_)) => true,
+	    (Whitespace(_), Whitespace(_)) => true,
+	    _ => false
+	}
+    }
+}
+
+use std::fmt;
+use std::fmt::Display;
+impl Display for Token {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+	write!(f, "{}", match self {
+	    ParOpen  => "(".to_string(),
+	    ParClose => ")".to_string(),
+	    Num(x) => x.to_string(),
+	    Sym(s) => s.to_string(),
+	    Whitespace(s) => s.to_string(),
+	})
+    }
+}
+
 use Token::*;
 use crate::parse::util::*;
 
@@ -41,9 +69,86 @@ fn tokenize(s: &str) -> Result<Vec<Token>, String> {
     }
 }
 
-
 fn tokens_to_ast(tokens: Vec<Token>) -> Result<SExp, String> {
-    todo!()
+    let tokens = iter::once(ParOpen)
+	.chain(tokens.into_iter())
+	.chain(iter::once(ParClose));
+
+    let res = tokens_to_ast_inner(tokens.collect());
+    match res {
+	Ok((rest, result)) if rest.len() == 0 => Ok(result),
+	Ok((rest, _)) => Err(format!("couldn't parse all input: '{:?}' remained", rest)),
+	Err(e) => Err(e),
+    }
+}
+
+use std::collections::VecDeque;
+
+fn tokens_to_ast_inner(
+    mut input: VecDeque<Token>
+) -> Result<(Vec<Token>, SExp), String> {
+
+    println!("{:?}", input.clone());
+
+    let mut current_token = input.pop_front();
+
+    match current_token {
+	Some(ParOpen) => Ok(()),
+	Some(t) => Err(format!(
+		       "expected opening parenthesis, found '{t}'"
+	)),
+	None => Err("unexpected input: expected opening parenthesis".to_string()),
+    }?;
+    current_token = input.pop_front();
+
+    if let Some(Whitespace(_)) = current_token {
+	current_token = input.pop_front();
+    }
+
+    let mut elements = vec![];
+    loop {
+
+	elements.push(match current_token {
+	    Some(Num(x))                 => Ok(Atom(Int(x))),
+	    Some(Sym(s)) if s == "+"     => Ok(Atom(Add)),
+	    Some(Sym(s)) if s == "*"     => Ok(Atom(Mul)),
+	    Some(Sym(s)) if s == "/"     => Ok(Atom(Div)),
+	    Some(Sym(s)) if s == "-"     => Ok(Atom(Sub)),
+	    Some(Sym(s)) if s == "quote" => Ok(Atom(Quote)),
+	    Some(Sym(s))                 => Ok(Atom(Var(s))),
+	    Some(ParClose) => break,
+	    Some(ParOpen)  => {
+		    let subexp = tokens_to_ast_inner(
+			iter::once(ParOpen)
+			    .chain(input.clone())
+			    .collect()
+		    )?;
+		    input = subexp.0.into();
+		    Ok(subexp.1)
+		},
+	    Some(Whitespace(_)) => Err("unexpected whitespace".to_string()),
+	    None => Err("unexpected end of input".to_string()),
+	}?);
+	current_token = input.pop_front();
+
+	match current_token {
+	    Some(Whitespace(_)) => current_token = input.pop_front(),
+	    Some(ParClose) => break,
+	    Some(_) => return Err("expected whitespace or closing parenthesis".to_string()),
+	    None => return Err("unexpected end of input".to_string())
+	};
+	if let Some(ParClose) = current_token {
+	    break;
+	}
+
+    }
+
+    let mut res = Atom(Nil);
+    for el in elements.into_iter().rev() {
+	res = scons(el, res);
+    }
+
+    Ok((input.into(), res))
 }
 
 
@@ -130,8 +235,8 @@ mod private_parsing_tests {
 	    tokens_to_ast(vec![
 		ParOpen,
 		sym("a"),
-		ParClose,
-		sym("b"),
+		ParClose, whitespace(" "),
+		sym("b"), whitespace(" "),
 		ParOpen,
 		sym("c"),
 		ParClose,
@@ -175,10 +280,9 @@ mod private_parsing_tests {
 	// Quote can be parsed
 	assert_eq!(
 	    tokens_to_ast(vec![
-		ParOpen,
 		sym("quote"), whitespace(" "),
 		sym("a"), whitespace(" "),
-		sym("b"), whitespace(" ")
+		sym("b"), whitespace(" "),
 	    ]),
 	    Ok(scons(Quote, scons(var("a"), scons(var("b"), Nil))))
 	);