commit e837e24b9a1c9f1509e46b8adffb37ca1c77853f
parent 9d3f254954f24e37832e52860723a5b3cd7ded74
Author: Demonstrandum <moi@knutsen.co>
Date: Wed, 17 Jul 2019 20:04:21 +0100
Super basic Pratt parser, needs to be extended.
Diffstat:
4 files changed, 107 insertions(+), 77 deletions(-)
diff --git a/src/syntax/ast.rs b/src/syntax/ast.rs
@@ -154,12 +154,14 @@ pub enum Nodes {
impl fmt::Display for Nodes {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
let printable = match self {
- Nodes::Ident(node) => format!("%ident {{ :value \"{}\" }}", node.value),
- Nodes::Num(node) => format!("%num {{ :value {} }}", node.value),
- Nodes::Str(node) => format!("%str {{ :value \"{}\" }}", node.value),
- Nodes::Sym(node) => format!("%sym {{ :value \"{}\" }}", node.value),
- Nodes::Call(node) => format!("%call {{ :callee \"{}\" }}", node.callee),
- Nodes::Block(node) => format!("%block {{ ... }}"),
+ Nodes::Ident(node) => format!("%ident{{ :value \"{}\" }}", node.value),
+ Nodes::Num(node) => format!("%num{{ :value {} }}", node.value),
+ Nodes::Str(node) => format!("%str{{ :value \"{}\" }}", node.value),
+ Nodes::Sym(node) => format!("%sym{{ :value \"{}\" }}", node.value),
+ Nodes::Call(node) => format!(
+ "%call{{ :callee ({}) :operands [| {} |] }}", node.callee,
+ node.operands.iter().map(Nodes::to_string).collect::<Vec<String>>().join(" ")),
+ Nodes::Block(node) => format!("%block{{ ... }}"),
};
write!(f, "{}", printable)
}
@@ -236,6 +238,6 @@ impl Root {
impl fmt::Display for Root {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
let str_mapped : Vec<String> = self.branches.iter().map(Nodes::to_string).collect();
- write!(f, "%root{{\n {}\n}}", str_mapped.join(",\n "))
+ write!(f, "[|\n {}\n|]", str_mapped.join(",\n "))
}
}
\ No newline at end of file
diff --git a/src/syntax/operators.rs b/src/syntax/operators.rs
@@ -1,6 +1,6 @@
/// Side of associativity.
-#[derive(PartialEq)]
+#[derive(Copy, Clone, PartialEq)]
pub enum Side {
Left, Right, Neither
}
@@ -10,35 +10,38 @@ pub enum Side {
/// - Its precedence (as an i32), the higher the int, the higher the precedence.
/// - Associativity, which can either be left, right, or no associativity.
/// - The number of arguments it takes / its arity. Either one, or two.
+#[derive(Copy, Clone)]
pub struct Operator {
- pub name : String,
+ pub name : &'static str,
pub precedence : i32,
pub associativity : Side,
pub arity : i32,
}
impl Operator {
- pub fn new(name : &str, precedence : i32, associativity : Side, arity : i32) -> Self {
+ pub fn new(name : &'static str, precedence : i32, associativity : Side, arity : i32) -> Self {
Operator {
- name: name.to_string(),
+ name: name.clone(),
precedence,
associativity,
arity,
}
}
- pub fn is_left(&self) -> bool {
- if self.associativity == Side::Left {
- return true;
- }
- false
- }
+ pub fn is_left(&self) -> bool { self.associativity == Side::Left }
- pub fn is_right(&self) -> bool {
- if self.associativity == Side::Right {
- return true;
- }
- false
+ pub fn is_right(&self) -> bool { self.associativity == Side::Right }
+
+ pub fn has_arity(&self, n : i32) -> bool { self.arity == n }
+
+ pub fn is_unary(&self) -> bool { self.has_arity(1) }
+
+ pub fn is_binary(&self) -> bool { self.has_arity(2) }
+
+ pub fn is_variable(&self) -> bool { self.has_arity(0) }
+
+ pub fn is_func(&self) -> bool {
+ self.precedence == 190 && self.arity >= 1
}
}
@@ -57,51 +60,61 @@ macro_rules! push_op {
impl PrecedenceTable {
pub fn new() -> Self {
let op = Operator::new;
- let mut table = PrecedenceTable { table: vec![
- op( "::",21, Side::Left, 2),
- op( "<>",20, Side::Right, 2),
- // Function calls have precedence 19, i.e. very high.
- // e.g. `f x + 3` bracketed is the same as `(f (x) (+) (3))`.
- op("not",18, Side::Right, 1),
- op( "-",17, Side::Right, 1),
- op( "^",16, Side::Right, 2),
- op( "*",15, Side::Left, 2),
- op( "/",15, Side::Left, 2),
- op("mod",15, Side::Left, 2),
- op( "&",14, Side::Left, 2),
- op( "|",13, Side::Left, 2),
- op( "+",12, Side::Left, 2),
- op( "-",12, Side::Left, 2),
- op( "\\",12, Side::Left, 2),
- op( "->",11, Side::Right, 2),
- op( ">>",10, Side::Right, 2),
- op( "<<",10, Side::Left, 2),
- op( "==", 9, Side::Neither, 2),
- op( "is",9, Side::Neither, 2),
- op( "/=", 9, Side::Neither, 2),
- op("isn't",9,Side::Neither, 2),
- op( "<", 9, Side::Neither, 2),
- op( "<=", 9, Side::Neither, 2),
- op( ">", 9, Side::Neither, 2),
- op( ">=", 9, Side::Neither, 2),
- op( "<-", 8, Side::Neither, 2),
- op( "&&", 7, Side::Right, 2),
- op("and", 7, Side::Right, 2),
- op( "||", 6, Side::Right, 2),
- op( "or", 6, Side::Right, 2),
- op( "..", 5, Side::Neither, 2),
- op( ":", 4, Side::Neither, 2),
- op( "|>", 4, Side::Right, 2),
- op( "=", 3, Side::Right, 2),
- op( "if", 2, Side::Neither, 2),
- op("unless", 2, Side::Neither, 2),
- op( ",", 1, Side::Right, 2),
- op( "=>", 0, Side::Neither, 2),
+ let table = PrecedenceTable { table: vec![
+ op( "::",210, Side::Left, 2),
+ op( "<>",200, Side::Right, 2),
+ // Function calls have precedence 190, i.e. very high.
+ // e.g. `f x + 3` bracketed is the same as `((f x) + 3)`.
+ op("not",180, Side::Right, 1),
+ op( "-",170, Side::Right, 1),
+ op( "^",160, Side::Right, 2),
+ op( "*",150, Side::Left, 2),
+ op( "/",150, Side::Left, 2),
+ op("mod",150, Side::Left, 2),
+ op( "&",140, Side::Left, 2),
+ op( "|",130, Side::Left, 2),
+ op( "+",120, Side::Left, 2),
+ op( "-",120, Side::Left, 2),
+ op( "\\",120, Side::Left, 2),
+ op( "->",110, Side::Right, 2),
+ op( ">>",100, Side::Right, 2),
+ op( "<<",100, Side::Left, 2),
+ op( "==", 90, Side::Neither, 2),
+ op( "is",90, Side::Neither, 2),
+ op( "/=", 90, Side::Neither, 2),
+ op("isn't",90,Side::Neither, 2),
+ op( "<", 90, Side::Neither, 2),
+ op( "<=", 90, Side::Neither, 2),
+ op( ">", 90, Side::Neither, 2),
+ op( ">=", 90, Side::Neither, 2),
+ op( "<-", 80, Side::Neither, 2),
+ op( "&&", 70, Side::Right, 2),
+ op("and", 70, Side::Right, 2),
+ op( "||", 60, Side::Right, 2),
+ op( "or", 60, Side::Right, 2),
+ op( "..", 50, Side::Neither, 2),
+ op( ":", 40, Side::Neither, 2),
+ op( "|>", 40, Side::Right, 2),
+ op( "=", 30, Side::Right, 2),
+ op( "if", 20, Side::Neither, 2),
+ op("unless", 20, Side::Neither, 2),
+ op( ",", 10, Side::Right, 2),
+ op( "=>", 1, Side::Neither, 2),
]};
table
}
+ pub fn new_op(&mut self, name : &'static str, prec : i32, assoc : Side, arity : i32) -> Operator {
+ let op = Operator::new(name, prec, assoc, arity);
+ self.table.push(op);
+ op
+ }
+
+ pub fn new_fun(&mut self, name : &'static str, max_arity : i32) -> Operator {
+ self.new_op(name, 19, Side::Neither, max_arity)
+ }
+
pub fn lookup(&self, name : &str, arity : i32) -> Option<&Operator> {
self.table.iter().filter(|o| o.name == name && o.arity == arity).next()
}
@@ -109,4 +122,10 @@ impl PrecedenceTable {
pub fn exists(&self, name : &str) -> bool {
self.table.iter().filter(|o| o.name == name).next().is_some()
}
+
+ pub fn precedence(&self, name : &str) -> Option<i32> {
+ let op = self.lookup(name, 2);
+ if op.is_some() { return Some(op.unwrap().precedence) }
+ return None;
+ }
}
\ No newline at end of file
diff --git a/src/syntax/parser.rs b/src/syntax/parser.rs
@@ -7,6 +7,7 @@ use ast::{Numerics, Nodes};
pub fn parse(stream : Vec<Token>) -> ast::Root {
let mut environment = ParseEnvironment::new(stream);
+ environment.optable.new_fun("max", 4);
environment.start();
@@ -29,28 +30,36 @@ impl ParseEnvironment {
}
pub fn start(&mut self) {
- while !self.stream.is_empty() {
- let token = self.stream.remove(0);
- match token.class {
- TokenType::Op => {
- if !self.optable.exists(&token.string) { panic!("Use of undefined operator."); }
- // ...
- }
- _ => panic!("Unexpected token.")
- };
- }
- self.root.branches.push(ast::IdentNode::new("hello"));
+ let e = self.expr(0);
+ self.root.branches.push(e);
}
- fn atom(&self, token : &Token) -> Nodes {
+ fn null_den(&mut self, token : &Token) -> Nodes {
match token.class {
TokenType::Ident => ast::IdentNode::new(&token.string),
- TokenType::Op => ast::IdentNode::new(&token.string),
+ TokenType::Op => ast::CallNode::new(ast::IdentNode::new(&token.string), vec![self.expr(300)]),
TokenType::Num => ast::NumNode::new(&*token.string),
TokenType::Str => ast::StrNode::new(&token.string),
_ => panic!("Passed non-atomic token to `atom` parser.")
}
}
+
+ fn expr(&mut self, right_prec : i32) -> Nodes {
+ let popped = &self.stream.remove(0);
+ let mut left = self.null_den(popped);
+
+ while self.optable.precedence(&self.stream[0].string).unwrap_or(0) > right_prec {
+ if self.stream[0].class == TokenType::EOF { break; }
+ let op = self.optable.lookup(&self.stream.remove(0).string, 2).unwrap();
+ left = self.left_den(left, op.clone());
+ }
+ return left;
+ }
+
+ fn left_den(&mut self, left : Nodes, op : operators::Operator) -> Nodes {
+ let right = self.expr(op.precedence - (if op.is_right() { 1 } else { 0 }));
+ ast::CallNode::new(ast::IdentNode::new(op.name), vec![left, right])
+ }
}
#[cfg(test)]
diff --git a/test.vh b/test.vh
@@ -1 +1 @@
-3 + 8 * 9-
\ No newline at end of file
+- 8+
\ No newline at end of file
