aboutsummaryrefslogtreecommitdiff
path: root/sloth/src/parser
diff options
context:
space:
mode:
Diffstat (limited to 'sloth/src/parser')
-rw-r--r--sloth/src/parser/ast.rs122
-rw-r--r--sloth/src/parser/expr.rs54
-rw-r--r--sloth/src/parser/mod.rs27
-rw-r--r--sloth/src/parser/stmt.rs149
4 files changed, 264 insertions, 88 deletions
diff --git a/sloth/src/parser/ast.rs b/sloth/src/parser/ast.rs
index 1a994df..8442cc2 100644
--- a/sloth/src/parser/ast.rs
+++ b/sloth/src/parser/ast.rs
@@ -2,16 +2,76 @@ use std::fmt::Display;
use crate::lexer::{self, TokenType};
use crate::parser::ParsingError;
+use crate::symtable::SymbolTable;
#[derive(PartialEq, Clone, Debug)]
+/// AstNode that is either an Expr or Stmt, typically used for iterating over an
+/// Ast for analysis reasons.
+pub enum AstNode<'a> {
+ Expr(&'a Expr),
+ Stmt(&'a Stmt),
+}
+
+impl<'a> AstNode<'a> {
+ pub fn children(&self) -> impl Iterator<Item = AstNode> {
+ let mut children = Vec::new();
+ match self {
+ Self::Expr(expr) => children.extend(expr.children()),
+ Self::Stmt(stmt) => children.extend(stmt.children()),
+ }
+ children.into_iter()
+ }
+}
+
+#[derive(Clone, Debug)]
pub struct Expr {
pub id: i32,
pub kind: ExprKind,
+ pub symtable: SymbolTable,
+}
+
+impl PartialEq for Expr {
+ fn eq(&self, other: &Self) -> bool {
+ self.id == other.id && self.kind == other.kind
+ }
}
impl Expr {
- pub fn new(id: i32, kind: ExprKind) -> Self {
- Self { id, kind }
+ pub fn new(id: i32, kind: ExprKind, symtable: SymbolTable) -> Self {
+ Self { id, kind, symtable }
+ }
+
+ /// Useful for testing
+ pub fn without_table(id: i32, kind: ExprKind) -> Self {
+ Self {
+ id,
+ kind,
+ symtable: SymbolTable::new(),
+ }
+ }
+
+ pub fn as_node(&self) -> AstNode {
+ AstNode::Expr(self)
+ }
+
+ pub fn children(&self) -> impl Iterator<Item = AstNode> {
+ let mut children = Vec::new();
+
+ match &self.kind {
+ ExprKind::Grouping(inner) => children.push(inner.as_node()),
+ ExprKind::BinaryOp { lhs, rhs, .. } => {
+ children.push(lhs.as_node());
+ children.push(rhs.as_node());
+ }
+ ExprKind::UnaryOp { value, .. } => children.push(value.as_node()),
+ ExprKind::Call { callee, args } => {
+ children.push(callee.as_node());
+ children.extend(args.iter().map(Expr::as_node));
+ }
+ _ => (),
+ }
+
+ children.into_iter()
}
}
@@ -35,15 +95,67 @@ pub enum ExprKind {
},
}
-#[derive(PartialEq, Clone, Debug)]
+#[derive(Clone, Debug)]
pub struct Stmt {
pub id: i32,
pub kind: StmtKind,
+ pub symtable: SymbolTable,
+}
+
+impl PartialEq for Stmt {
+ fn eq(&self, other: &Self) -> bool {
+ self.id == other.id && self.kind == other.kind
+ }
}
impl Stmt {
- pub fn new(id: i32, kind: StmtKind) -> Self {
- Self { id, kind }
+ pub fn new(id: i32, kind: StmtKind, symtable: SymbolTable) -> Self {
+ Self { id, kind, symtable }
+ }
+
+ /// Useful for testing
+ pub fn without_table(id: i32, kind: StmtKind) -> Self {
+ Self {
+ id,
+ kind,
+ symtable: SymbolTable::new(),
+ }
+ }
+
+ pub fn as_node(&self) -> AstNode {
+ AstNode::Stmt(self)
+ }
+
+ pub fn children(&self) -> impl Iterator<Item = AstNode> {
+ let mut children = Vec::new();
+
+ match &self.kind {
+ StmtKind::Block(inner) => {
+ children.extend(inner.iter().map(Self::as_node));
+ }
+ StmtKind::ExprStmt(expr) => children.push(expr.as_node()),
+ StmtKind::IfStmt {
+ condition,
+ if_then,
+ else_then,
+ } => {
+ children.push(condition.as_node());
+ children.push(if_then.as_node());
+ if let Some(else_then) = else_then {
+ children.push(else_then.as_node());
+ }
+ }
+ StmtKind::WhileStmt { condition, body } => {
+ children.push(condition.as_node());
+ children.push(body.as_node());
+ }
+ StmtKind::DefineVariable { value, .. } => children.push(value.as_node()),
+ StmtKind::AssignVariable { value, .. } => children.push(value.as_node()),
+ StmtKind::DefineFunction { body, .. } => children.push(body.as_node()),
+ StmtKind::Return(value) => children.push(value.as_node()),
+ }
+
+ children.into_iter()
}
}
diff --git a/sloth/src/parser/expr.rs b/sloth/src/parser/expr.rs
index 48ee038..5fd9b49 100644
--- a/sloth/src/parser/expr.rs
+++ b/sloth/src/parser/expr.rs
@@ -21,7 +21,7 @@ impl<'a> AstParser<'a> {
value: Box::new(value),
};
- return Ok(Expr::new(self.reserve_id(), kind));
+ return Ok(Expr::new(self.reserve_id(), kind, self.top.clone()));
}
self.call()
@@ -43,10 +43,14 @@ impl<'a> AstParser<'a> {
self.consume(TokenType::ClosingParen, "Expected ')'")?;
- expr = Expr::new(self.reserve_id(), ExprKind::Call {
- callee: Box::new(expr),
- args: arguments,
- });
+ expr = Expr::new(
+ self.reserve_id(),
+ ExprKind::Call {
+ callee: Box::new(expr),
+ args: arguments,
+ },
+ self.top.clone(),
+ );
}
Ok(expr)
@@ -66,7 +70,7 @@ impl<'a> AstParser<'a> {
_ => return Err(ParsingError::UnexpectedToken),
};
- Ok(Expr::new(self.reserve_id(), kind))
+ Ok(Expr::new(self.reserve_id(), kind, self.top.clone()))
}
}
@@ -88,7 +92,7 @@ macro_rules! binary_expr {
rhs: Box::new(rhs),
};
- expr = Expr::new(self.reserve_id(), kind);
+ expr = Expr::new(self.reserve_id(), kind, self.top.clone());
}
Ok(expr)
@@ -115,6 +119,7 @@ mod tests {
use crate::lexer::Lexer;
use crate::parser::ast::{BinaryOp, Expr, ExprKind, Literal};
+ use crate::symtable::SymbolTable;
use crate::AstParser;
#[test]
@@ -122,25 +127,40 @@ mod tests {
let lexer = Lexer::new("3 + 5 * 4 - 9 / 3");
let tokens = lexer.collect_vec();
- let expected_ast = Ok(Expr::new(8, ExprKind::BinaryOp {
+ let expected_ast = Ok(Expr::without_table(8, ExprKind::BinaryOp {
op: BinaryOp::Sub,
- lhs: Box::new(Expr::new(4, ExprKind::BinaryOp {
+ lhs: Box::new(Expr::without_table(4, ExprKind::BinaryOp {
op: BinaryOp::Add,
- lhs: Box::new(Expr::new(0, ExprKind::Literal(Literal::Integer(3)))),
- rhs: Box::new(Expr::new(3, ExprKind::BinaryOp {
+ lhs: Box::new(Expr::without_table(
+ 0,
+ ExprKind::Literal(Literal::Integer(3)),
+ )),
+ rhs: Box::new(Expr::without_table(3, ExprKind::BinaryOp {
op: BinaryOp::Mul,
- lhs: Box::new(Expr::new(1, ExprKind::Literal(Literal::Integer(5)))),
- rhs: Box::new(Expr::new(2, ExprKind::Literal(Literal::Integer(4)))),
+ lhs: Box::new(Expr::without_table(
+ 1,
+ ExprKind::Literal(Literal::Integer(5)),
+ )),
+ rhs: Box::new(Expr::without_table(
+ 2,
+ ExprKind::Literal(Literal::Integer(4)),
+ )),
})),
})),
- rhs: Box::new(Expr::new(7, ExprKind::BinaryOp {
+ rhs: Box::new(Expr::without_table(7, ExprKind::BinaryOp {
op: BinaryOp::Div,
- lhs: Box::new(Expr::new(5, ExprKind::Literal(Literal::Integer(9)))),
- rhs: Box::new(Expr::new(6, ExprKind::Literal(Literal::Integer(3)))),
+ lhs: Box::new(Expr::without_table(
+ 5,
+ ExprKind::Literal(Literal::Integer(9)),
+ )),
+ rhs: Box::new(Expr::without_table(
+ 6,
+ ExprKind::Literal(Literal::Integer(3)),
+ )),
})),
}));
- let mut parser = AstParser::new(tokens);
+ let mut parser = AstParser::new(tokens, SymbolTable::new());
let generated_ast = parser.expression();
println!("Expected AST:\n{expected_ast:#?}\n\n");
diff --git a/sloth/src/parser/mod.rs b/sloth/src/parser/mod.rs
index bc47ddd..3328137 100644
--- a/sloth/src/parser/mod.rs
+++ b/sloth/src/parser/mod.rs
@@ -3,8 +3,9 @@ pub mod expr;
pub mod graph;
pub mod stmt;
-use self::ast::{Literal, Stmt};
+use self::ast::{Literal, Stmt, StmtKind};
use crate::lexer::{Token, TokenType};
+use crate::symtable::SymbolTable;
#[derive(thiserror::Error, Debug, PartialEq)]
pub enum ParsingError {
@@ -19,28 +20,36 @@ pub struct AstParser<'a> {
tokens: Vec<Token<'a>>,
index: usize,
id: i32,
+ top: SymbolTable,
}
impl<'a> AstParser<'a> {
- pub fn parse(tokens: Vec<Token<'a>>) -> Result<Vec<Stmt>, ParsingError> {
- let mut parser = Self::new(tokens);
+ pub fn parse(tokens: Vec<Token<'a>>, root: SymbolTable) -> Result<Stmt, ParsingError> {
+ let mut parser = Self::new(tokens, root);
let mut statements = Vec::new();
while !parser.eof() {
statements.push(parser.statement()?);
}
- Ok(statements)
+ let root = Stmt::new(
+ parser.reserve_id(),
+ StmtKind::Block(statements),
+ parser.top.clone(),
+ );
+
+ Ok(root)
}
}
/// Implementation containing utilities used by the parsers internal components
impl<'a> AstParser<'a> {
- pub fn new(tokens: Vec<Token<'a>>) -> Self {
+ pub fn new(tokens: Vec<Token<'a>>, root: SymbolTable) -> Self {
Self {
tokens,
index: 0,
id: 0,
+ top: root,
}
}
@@ -109,6 +118,14 @@ impl<'a> AstParser<'a> {
id
}
+ pub fn push_table(&mut self) {
+ self.top = self.top.make_child();
+ }
+
+ pub fn pop_table(&mut self) {
+ self.top = self.top.parent().unwrap();
+ }
+
pub fn eof(&self) -> bool {
self.index >= self.tokens.len()
}
diff --git a/sloth/src/parser/stmt.rs b/sloth/src/parser/stmt.rs
index 2370311..c7433c2 100644
--- a/sloth/src/parser/stmt.rs
+++ b/sloth/src/parser/stmt.rs
@@ -42,7 +42,7 @@ impl<'a> AstParser<'a> {
else_then: else_then.map(|it| it.into()),
};
- Ok(Stmt::new(self.reserve_id(), kind))
+ Ok(Stmt::new(self.reserve_id(), kind, self.top.clone()))
}
fn while_stmt(&mut self) -> Result<Stmt, ParsingError> {
@@ -57,7 +57,7 @@ impl<'a> AstParser<'a> {
body: body.into(),
};
- Ok(Stmt::new(self.reserve_id(), kind))
+ Ok(Stmt::new(self.reserve_id(), kind, self.top.clone()))
}
// TODO: Make variable types optional
@@ -82,7 +82,7 @@ impl<'a> AstParser<'a> {
typ,
};
- Ok(Stmt::new(self.reserve_id(), kind))
+ Ok(Stmt::new(self.reserve_id(), kind, self.top.clone()))
}
// TODO: Make argument types optional
@@ -126,7 +126,7 @@ impl<'a> AstParser<'a> {
body: body.into(),
};
- Ok(Stmt::new(self.reserve_id(), kind))
+ Ok(Stmt::new(self.reserve_id(), kind, self.top.clone()))
}
fn return_stmt(&mut self) -> Result<Stmt, ParsingError> {
@@ -134,7 +134,7 @@ impl<'a> AstParser<'a> {
let value = self.expression()?;
self.consume(TokenType::SemiColon, "Expected ';' at end of statement")?;
let kind = StmtKind::Return(value);
- Ok(Stmt::new(self.reserve_id(), kind))
+ Ok(Stmt::new(self.reserve_id(), kind, self.top.clone()))
}
fn assign_variable(&mut self) -> Result<Stmt, ParsingError> {
@@ -143,32 +143,43 @@ impl<'a> AstParser<'a> {
let value = self.expression()?;
self.consume(TokenType::SemiColon, "Expected ';' at end of statement")?;
let kind = StmtKind::AssignVariable { identifier, value };
- Ok(Stmt::new(self.reserve_id(), kind))
+ Ok(Stmt::new(self.reserve_id(), kind, self.top.clone()))
}
fn expression_stmt(&mut self) -> Result<Stmt, ParsingError> {
let expr = self.expression()?;
self.consume(TokenType::SemiColon, "Expected ';' at end of statement")?;
let kind = StmtKind::ExprStmt(expr);
- Ok(Stmt::new(self.reserve_id(), kind))
+ Ok(Stmt::new(self.reserve_id(), kind, self.top.clone()))
}
fn block(&mut self) -> Result<Stmt, ParsingError> {
- // Consume the opening brace
- self.consume(TokenType::OpeningBrace, "Expected '{'")?;
+ // This inner function exists to make cleanup of the pushed symbol table easier
+ // in the case of a parsing error.
+ fn inner(this: &mut AstParser) -> Result<Stmt, ParsingError> {
+ // Consume the opening brace
+ this.consume(TokenType::OpeningBrace, "Expected '{'")?;
+
+ // Get the body of the block
+ let mut body = Vec::new();
+ while !this.eof() && this.peek().tt != TokenType::ClosingBrace {
+ body.push(this.statement()?);
+ }
- // Get the body of the block
- let mut body = Vec::new();
- while !self.eof() && self.peek().tt != TokenType::ClosingBrace {
- body.push(self.statement()?);
- }
+ // Consume the closing brace
+ this.consume(TokenType::ClosingBrace, "Expected '}'")?;
+
+ let kind = StmtKind::Block(body);
- // Consume the closing brace
- self.consume(TokenType::ClosingBrace, "Expected '}'")?;
+ Ok(Stmt::new(this.reserve_id(), kind, this.top.clone()))
+ }
- let kind = StmtKind::Block(body);
+ // Push a table, call the inner function and then pop that table
+ self.push_table();
+ let result = inner(self);
+ self.pop_table();
- Ok(Stmt::new(self.reserve_id(), kind))
+ result
}
}
@@ -179,26 +190,27 @@ mod tests {
use super::{AstParser, StmtKind};
use crate::lexer::Lexer;
use crate::parser::ast::{BinaryOp, Expr, ExprKind, FunctionInput, Literal, Stmt};
+ use crate::symtable::SymbolTable;
#[test]
fn standalone_blocks() {
let tokens = Lexer::new("{{{ 0; }}}").collect_vec();
- let expected_ast = Ok(Stmt::new(
+ let expected_ast = Ok(Stmt::without_table(
4,
- StmtKind::Block(vec![Stmt::new(
+ StmtKind::Block(vec![Stmt::without_table(
3,
- StmtKind::Block(vec![Stmt::new(
+ StmtKind::Block(vec![Stmt::without_table(
2,
- StmtKind::Block(vec![Stmt::new(
+ StmtKind::Block(vec![Stmt::without_table(
1,
- StmtKind::ExprStmt(Expr::new(0, Literal::Integer(0).into())),
+ StmtKind::ExprStmt(Expr::without_table(0, Literal::Integer(0).into())),
)]),
)]),
)]),
));
- let mut parser = AstParser::new(tokens);
+ let mut parser = AstParser::new(tokens, SymbolTable::new());
let generated_ast = parser.statement();
println!("Expected AST:\n{expected_ast:#?}\n\n");
@@ -211,17 +223,23 @@ mod tests {
fn basic_variable_definition() {
let tokens = Lexer::new("var foo: Int = 5 + 3;").collect_vec();
- let expected_ast = Ok(Stmt::new(3, StmtKind::DefineVariable {
+ let expected_ast = Ok(Stmt::without_table(3, StmtKind::DefineVariable {
identifier: "foo".to_string(),
- value: Expr::new(2, ExprKind::BinaryOp {
+ value: Expr::without_table(2, ExprKind::BinaryOp {
op: BinaryOp::Add,
- lhs: Box::new(Expr::new(0, ExprKind::Literal(Literal::Integer(5)))),
- rhs: Box::new(Expr::new(1, ExprKind::Literal(Literal::Integer(3)))),
+ lhs: Box::new(Expr::without_table(
+ 0,
+ ExprKind::Literal(Literal::Integer(5)),
+ )),
+ rhs: Box::new(Expr::without_table(
+ 1,
+ ExprKind::Literal(Literal::Integer(3)),
+ )),
}),
typ: "Int".to_string(),
}));
- let mut parser = AstParser::new(tokens);
+ let mut parser = AstParser::new(tokens, SymbolTable::new());
let generated_ast = parser.statement();
println!("Expected AST:\n{expected_ast:#?}\n\n");
@@ -243,42 +261,51 @@ mod tests {
)
.collect_vec();
- let expected_ast = Ok(Stmt::new(11, StmtKind::DefineFunction {
+ let expected_ast = Ok(Stmt::without_table(11, StmtKind::DefineFunction {
identifier: "foo".to_owned(),
inputs: vec![FunctionInput {
identifier: "bar".to_owned(),
typ: "Int".to_owned(),
}],
output: Some("Int".to_owned()),
- body: Box::new(Stmt::new(
+ body: Box::new(Stmt::without_table(
10,
StmtKind::Block(vec![
- Stmt::new(3, StmtKind::DefineVariable {
+ Stmt::without_table(3, StmtKind::DefineVariable {
identifier: "baz".to_owned(),
- value: Expr::new(2, ExprKind::BinaryOp {
+ value: Expr::without_table(2, ExprKind::BinaryOp {
op: BinaryOp::Add,
- lhs: Box::new(Expr::new(0, ExprKind::Identifier("bar".to_owned()))),
- rhs: Box::new(Expr::new(1, Literal::Integer(1).into())),
+ lhs: Box::new(Expr::without_table(
+ 0,
+ ExprKind::Identifier("bar".to_owned()),
+ )),
+ rhs: Box::new(Expr::without_table(1, Literal::Integer(1).into())),
}),
typ: "Int".to_owned(),
}),
- Stmt::new(7, StmtKind::AssignVariable {
+ Stmt::without_table(7, StmtKind::AssignVariable {
identifier: "baz".to_owned(),
- value: Expr::new(6, ExprKind::BinaryOp {
+ value: Expr::without_table(6, ExprKind::BinaryOp {
op: BinaryOp::Add,
- lhs: Box::new(Expr::new(4, ExprKind::Identifier("baz".to_owned()))),
- rhs: Box::new(Expr::new(5, Literal::Integer(1).into())),
+ lhs: Box::new(Expr::without_table(
+ 4,
+ ExprKind::Identifier("baz".to_owned()),
+ )),
+ rhs: Box::new(Expr::without_table(5, Literal::Integer(1).into())),
}),
}),
- Stmt::new(
+ Stmt::without_table(
9,
- StmtKind::Return(Expr::new(8, ExprKind::Identifier("baz".to_owned()))),
+ StmtKind::Return(Expr::without_table(
+ 8,
+ ExprKind::Identifier("baz".to_owned()),
+ )),
),
]),
)),
}));
- let mut parser = AstParser::new(tokens);
+ let mut parser = AstParser::new(tokens, SymbolTable::new());
let generated_ast = parser.statement();
println!("Expected AST:\n{expected_ast:#?}\n\n");
@@ -304,45 +331,45 @@ mod tests {
)
.collect_vec();
- let expected_ast = Ok(Stmt::new(17, StmtKind::IfStmt {
- condition: Expr::new(0, ExprKind::Identifier("foo".to_owned())),
- if_then: Box::new(Stmt::new(
+ let expected_ast = Ok(Stmt::without_table(17, StmtKind::IfStmt {
+ condition: Expr::without_table(0, ExprKind::Identifier("foo".to_owned())),
+ if_then: Box::new(Stmt::without_table(
3,
- StmtKind::Block(vec![Stmt::new(
+ StmtKind::Block(vec![Stmt::without_table(
2,
- StmtKind::ExprStmt(Expr::new(1, Literal::Integer(0).into())),
+ StmtKind::ExprStmt(Expr::without_table(1, Literal::Integer(0).into())),
)]),
)),
- else_then: Some(Box::new(Stmt::new(16, StmtKind::IfStmt {
- condition: Expr::new(4, ExprKind::Identifier("bar".to_owned())),
- if_then: Box::new(Stmt::new(
+ else_then: Some(Box::new(Stmt::without_table(16, StmtKind::IfStmt {
+ condition: Expr::without_table(4, ExprKind::Identifier("bar".to_owned())),
+ if_then: Box::new(Stmt::without_table(
7,
- StmtKind::Block(vec![Stmt::new(
+ StmtKind::Block(vec![Stmt::without_table(
6,
- StmtKind::ExprStmt(Expr::new(5, Literal::Integer(1).into())),
+ StmtKind::ExprStmt(Expr::without_table(5, Literal::Integer(1).into())),
)]),
)),
- else_then: Some(Box::new(Stmt::new(15, StmtKind::IfStmt {
- condition: Expr::new(8, ExprKind::Identifier("baz".to_owned())),
- if_then: Box::new(Stmt::new(
+ else_then: Some(Box::new(Stmt::without_table(15, StmtKind::IfStmt {
+ condition: Expr::without_table(8, ExprKind::Identifier("baz".to_owned())),
+ if_then: Box::new(Stmt::without_table(
11,
- StmtKind::Block(vec![Stmt::new(
+ StmtKind::Block(vec![Stmt::without_table(
10,
- StmtKind::ExprStmt(Expr::new(9, Literal::Integer(2).into())),
+ StmtKind::ExprStmt(Expr::without_table(9, Literal::Integer(2).into())),
)]),
)),
- else_then: Some(Box::new(Stmt::new(
+ else_then: Some(Box::new(Stmt::without_table(
14,
- StmtKind::Block(vec![Stmt::new(
+ StmtKind::Block(vec![Stmt::without_table(
13,
- StmtKind::ExprStmt(Expr::new(12, Literal::Integer(3).into())),
+ StmtKind::ExprStmt(Expr::without_table(12, Literal::Integer(3).into())),
)]),
))),
}))),
}))),
}));
- let mut parser = AstParser::new(tokens);
+ let mut parser = AstParser::new(tokens, SymbolTable::new());
let generated_ast = parser.statement();
println!("Expected AST:\n{expected_ast:#?}\n\n");
generated by cgit v1.2.3 (git 2.46.0) at 2025-10-29 08:00:05 +0000