Basic expression parsing

3 files changed, 153 insertions, 9 deletions

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."))
+        }
+    }
+}