Basic expression parsing

6 files changed, 168 insertions, 12 deletions

diff --git a/Cargo.lock b/Cargo.lock
index 41466aa..84c792a 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -3,5 +3,14 @@
 version = 3
 
 [[package]]
+name = "anyhow"
+version = "1.0.44"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "61604a8f862e1d5c3229fdd78f8b02c68dcf73a4c4b05fd636d12240aaa242c1"
+
+[[package]]
 name = "rabbithole"
 version = "0.1.0"
+dependencies = [
+ "anyhow",
+]
diff --git a/Cargo.toml b/Cargo.toml
index 8679632..fe24d01 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -6,3 +6,4 @@ edition = "2018"
 # See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
 
 [dependencies]
+anyhow = "1.0"
\ No newline at end of file
diff --git a/src/main.rs b/src/main.rs
index 2dab78d..3fa6bbf 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -3,11 +3,13 @@ mod parse;
 
 use lex::lexer::Lexer;
 
-use crate::parse::parse;
+use crate::parse::parser::Parser;
 
 fn main() {
-    let source = "1 + 2";
+    let source = "1 * 2 + 3 + (-1)";
+
     let lexer = Lexer::new(source);
+    let mut parser = Parser::new(lexer);
 
-    println!("{:?}", parse(lexer.peekable()));
+    println!("{}", parser.parse().expect("Failed parsing."));
 }
diff --git a/src/parse/ast.rs b/src/parse/ast.rs
index 2f30eaf..0f7ea34 100644
--- a/src/parse/ast.rs
+++ b/src/parse/ast.rs
@@ -1,3 +1,5 @@
+use std::fmt::Display;
+
 use crate::lex::token::Token;
 
 #[derive(Debug)]
@@ -14,3 +16,40 @@ pub enum Expression {
     Group(Box<Expression>),
     Literal(Token),
 }
+
+impl Display for Expression {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        self.nested_fmt(f, 0)
+    }
+}
+
+impl Expression {
+    fn nested_fmt(&self, f: &mut std::fmt::Formatter<'_>, depth: usize) -> std::fmt::Result {
+        let pad = "  ".repeat(depth);
+        match self {
+            Expression::Binary { left, op, right } => {
+                writeln!(f, "{}Binary:", pad)?;
+                writeln!(f, "{}- Left:", pad)?;
+                left.nested_fmt(f, depth + 1)?;
+                writeln!(f, "{}- Operator: {:?}", pad, op.variant)?;
+                writeln!(f, "{}- Right:", pad)?;
+                right.nested_fmt(f, depth + 1)?;
+            }
+            Expression::Unary { op, right } => {
+                writeln!(f, "{}Unary:", pad)?;
+                writeln!(f, "{}- Operator: {:?}", pad, op.variant)?;
+                writeln!(f, "{}- Right:", pad)?;
+                right.nested_fmt(f, depth + 1)?;
+            }
+            Expression::Group(node) => {
+                writeln!(f, "{}Group:", pad)?;
+                node.nested_fmt(f, depth + 1)?;
+            }
+            Expression::Literal(token) => {
+                writeln!(f, "{}Literal: {:?}", pad, token.variant)?;
+            }
+        }
+
+        Ok(())
+    }
+}
diff --git a/src/parse/mod.rs b/src/parse/mod.rs
index 2938131..a310c76 100644
--- a/src/parse/mod.rs
+++ b/src/parse/mod.rs
@@ -1,10 +1,2 @@
 pub mod ast;
-
-use crate::parse::ast::Expression;
-use std::iter::Peekable;
-
-use crate::lex::token::Token;
-
-pub fn parse(tokens: Peekable<impl Iterator<Item = Token>>) -> Expression {
-    todo!()
-}
+pub mod parser;
diff --git a/src/parse/parser.rs b/src/parse/parser.rs
new file mode 100644
index 0000000..dc99262
--- /dev/null
+++ b/src/parse/parser.rs
@@ -0,0 +1,113 @@
+use crate::lex::token::Token;
+use crate::lex::token::TokenVariant;
+use crate::lex::token::TokenVariant::*;
+use crate::parse::ast::Expression;
+use anyhow::anyhow;
+use anyhow::Result;
+use std::iter::Peekable;
+
+pub struct Parser<T: Iterator> {
+    tokens: Peekable<T>,
+}
+
+impl<T: Iterator<Item = Token>> Parser<T> {
+    pub fn new(tokens: T) -> Self {
+        Parser {
+            tokens: tokens.peekable(),
+        }
+    }
+
+    pub fn parse(&mut self) -> Result<Expression> {
+        self.expression()
+    }
+
+    fn expression(&mut self) -> Result<Expression> {
+        self.term_expression()
+    }
+
+    fn term_expression(&mut self) -> Result<Expression> {
+        let mut left = self.factor_expression()?;
+
+        while matches!(
+            self.tokens.peek(),
+            Some(Token {
+                variant: OpPlus | OpMinus,
+                ..
+            })
+        ) {
+            let op = self.tokens.next().unwrap();
+            let right = self.factor_expression()?;
+
+            left = Expression::Binary {
+                left: Box::new(left),
+                op,
+                right: Box::new(right),
+            };
+        }
+
+        Ok(left)
+    }
+
+    fn factor_expression(&mut self) -> Result<Expression> {
+        let mut left = self.unary_expression()?;
+
+        while matches!(
+            self.tokens.peek(),
+            Some(Token {
+                variant: OpSlash | OpStar,
+                ..
+            })
+        ) {
+            let op = self.tokens.next().unwrap();
+            let right = self.unary_expression()?;
+
+            left = Expression::Binary {
+                left: Box::new(left),
+                op,
+                right: Box::new(right),
+            };
+        }
+
+        Ok(left)
+    }
+
+    fn unary_expression(&mut self) -> Result<Expression> {
+        let expression = if let Some(Token {
+            variant: OpPlus | OpMinus | OpNot,
+            ..
+        }) = self.tokens.peek()
+        {
+            Expression::Unary {
+                op: self.tokens.next().unwrap(),
+                right: Box::new(self.unary_expression()?),
+            }
+        } else {
+            self.unit_expression()?
+        };
+
+        Ok(expression)
+    }
+
+    fn unit_expression(&mut self) -> Result<Expression> {
+        if let Some(token) = self.tokens.next() {
+            match token.variant {
+                Int(_) | Float(_) => Ok(Expression::Literal(token)),
+                GroupOpen => {
+                    let expression = self.expression()?;
+                    if let Some(Token {
+                        variant: TokenVariant::GroupClose,
+                        ..
+                    }) = self.tokens.next()
+                    {
+                        Ok(Expression::Group(Box::new(expression)))
+                    } else {
+                        Err(anyhow!("Expected ')' after grouping."))
+                    }
+                }
+                _ => Err(anyhow!("Unexpected token: {:?}", token.variant)),
+            }
+        } else {
+            Err(anyhow!("Expected expression."))
+        }
+    }
+}