Parsin

3 files changed, 247 insertions, 62 deletions

diff --git a/gock.ts b/gock.ts
deleted file mode 100644
index e8d1c53..0000000
--- a/gock.ts
+++ /dev/null
@@ -1,42 +0,0 @@
-type Int = "Int";
-type Bool = "Bool";
-type Atom = Int | Bool;
-type SimpleType = Arrow | Atom;
-type Arrow = {
-  left:    SimpleType;
-  right:   SimpleType;
-};
-
-type Identifier = string;
-
-type Binding = {
-  name:    Identifier;
-  type?:   SimpleType;
-};
-
-type Abstraction = {
-  binding: Binding;
-  body:    ASTNode;
-};
-
-type ASTNode = Abstraction | Application | Identifier;
-
-//
-
-class Environment<T> {
-  constructor(private readonly _captures: Map<Identifier, T>, private readonly _parent?: Environment) {}
-
-  public add(identifier: Identifier, substitution: T): Environment<T> {
-    const captures = new HashMap(); captures.put(identifier, substitution);
-    return new Environment<>(captures, this);
-  }
-
-  public get(identifier: Identifier): T? {
-    if (this._captures.has(identifier)) return this._captures.get(identifier);
-    return this._parent?.get(identifier);
-  }
-}
-
-//const tokenize
-// const parse
-// const check
diff --git a/grammar.txt b/grammar.txt
index 84b8123..ec9fa9c 100644
--- a/grammar.txt
+++ b/grammar.txt
@@ -2,20 +2,22 @@ let x = 2;
     y = 3; in
   (x y)
 
-let x: (Int) = 2;
+let x: (Int) =
+      let y: (Int) = { x }; in
+        y;
     y: (Int) = 3;
-    f: ((Int -> Int) -> Int) = [a, b] { ((plus a) b) }; in
+    f: (((Int) -> (Int)) -> Int) = [a, b] { ((plus a) b) }; in
   ((f x) y)
 ---
 
 
 LetStatement: "let" [Assignment ";"]+ "in" Body
 Binding: Ident (":" TypeDecl)?
-Assignment: Binding "=" Computation
+Assignment: Binding "=" Statement
+Statement: LetStatement | Abstraction
 Computation: Identifier | Application | Abstraction
 Application: "(" Computation Computation ")"
 Abstraction: "[" UncurriedArguments "]" "{" Computation "}"
-UncurriedArguments: Binding ("," Binding)+
 
 LetStatement: "let" Ident (":" TypeDecl)? "=" Computation in
 
@@ -24,6 +26,6 @@ Arrow: TypeDecl "->" TypeDecl
 TypeDecl: "(" BaseType | Arrow ")"
 
 Binding: Identifier (":" TypeDecl)?
-UncurriedArguments: Identifier
+UncurriedArguments: Identifier ["," Identifier]+
 Abstraction: UncurriedArguments "{" Binding "=>" Computation "}"
 
diff --git a/src/main.rs b/src/main.rs
index 7ec318a..5018b43 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -1,4 +1,4 @@
-#[derive(Debug, Clone, PartialEq)]
+#[derive(Debug, Clone, PartialEq, Eq)]
 enum TokenType {
     Lparen,
     Rparen,
@@ -6,18 +6,22 @@ enum TokenType {
     Rbrace,
     Lbracket,
     Rbracket,
+    Arrow,
+    Comma,
+    Equals,
+    Semicolon,
     Colon,
     Identifier(String),
     Eof,
 }
 
-#[derive(Debug, Clone, Copy)]
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
 struct Blame {
     line: usize,
     char: usize,
 }
 
-#[derive(Debug)]
+#[derive(Debug, PartialEq, Eq)]
 struct Token {
     token: TokenType,
     blame: Blame,
@@ -36,7 +40,7 @@ impl Lexer {
         tokens.push(Token {
             token: TokenType::Eof,
             blame: Blame {
-                line: tokens.len(),
+                line: program.lines().count(),
                 char: 0,
             },
         });
@@ -59,6 +63,7 @@ impl Lexer {
         };
 
         for (i, c) in text.char_indices() {
+            let lookahead = text.chars().nth(i.saturating_add(1));
             let singlechar = match c {
                 '(' => Some(TokenType::Lparen),
                 ')' => Some(TokenType::Rparen),
@@ -67,6 +72,12 @@ impl Lexer {
                 '{' => Some(TokenType::Lbrace),
                 '}' => Some(TokenType::Rbrace),
                 ':' => Some(TokenType::Colon),
+                ';' => Some(TokenType::Semicolon),
+                '-' => {
+                    Some(TokenType::Arrow).take_if(|_| lookahead.filter(|it| *it == '>').is_some())
+                }
+                ',' => Some(TokenType::Comma),
+                '=' => Some(TokenType::Equals),
                 _ => None,
             };
 
@@ -109,16 +120,182 @@ type Identifier = String;
 
 struct Binding {
     name: Identifier,
-    arg_type: Option<SimpleType>,
+    arg_type: Option<Box<TypeDeclaration>>,
+}
+
+struct TypeDeclaration {
+    base_type: Option<Identifier>,
+    arrow: Option<Box<(TypeDeclaration, TypeDeclaration)>>,
+}
+
+struct Assignment {
+    binding: Binding,
+    computation: Computation,
+}
+
+struct Arguments {
+    args_list: Vec<Identifier>,
+}
+
+struct Abstraction {
+    arguments: Arguments,
+    body: Box<Computation>,
+}
+
+struct Application {
+    apply: Option<(Box<Computation>, Box<Computation>)>,
+}
+
+struct Computation {
+    application: Option<Application>,
+    abstraction: Option<Abstraction>,
+    identifier: Option<Identifier>,
+}
+
+struct LetStatement {
+    assignments: Vec<Assignment>,
 }
 
 enum ASTNode {
-    Abstraction {
-        binding: Binding,
-        body: Box<ASTNode>,
-    },
-    Application((Box<ASTNode>, Box<ASTNode>)),
-    Identifier(Identifier),
+    Binding(Binding),
+    TypeDeclaration(TypeDeclaration),
+    Assignment(Assignment),
+    Arguments(Arguments),
+    Abstraction(Abstraction),
+    Application(Application),
+    Computation(Computation),
+    LetStatement(LetStatement),
+}
+
+struct Parser {
+    position: usize,
+    tokens: Vec<Token>,
+}
+
+#[derive(Debug)]
+enum ParsingFailure {
+    Blame(Blame, String),
+    PastTokens,
+}
+
+impl Parser {
+    fn peek(&mut self) -> Option<&Token> {
+        return self.tokens.get(self.position + 1);
+    }
+
+    fn consume_if_and_map<T>(
+        &mut self,
+        f: fn(&Token) -> Option<T>,
+        msg: String,
+    ) -> Result<T, ParsingFailure> {
+        if self.position == self.tokens.len() {
+            return Result::Err(ParsingFailure::PastTokens);
+        }
+        let val = f(&self.tokens[self.position]);
+        if val.is_some() {
+            self.position += 1;
+            return Result::Ok(val.unwrap()); //&self.tokens[self.position - 1]);
+        }
+        return Result::Err(ParsingFailure::Blame(self.tokens[self.position].blame, msg));
+    }
+
+    fn consume_if_match(
+        &mut self,
+        f: fn(&Token) -> bool,
+        msg: String,
+    ) -> Result<&Token, ParsingFailure> {
+        if self.position == self.tokens.len() {
+            return Result::Err(ParsingFailure::PastTokens);
+        }
+        if f(&self.tokens[self.position]) {
+            self.position += 1;
+            return Result::Ok(&self.tokens[self.position - 1]);
+        }
+        return Result::Err(ParsingFailure::Blame(self.tokens[self.position].blame, msg));
+    }
+
+    fn consume_if_match_nomsg(&mut self, f: fn(&Token) -> bool) -> Result<&Token, ParsingFailure> {
+        return self.consume_if_match(f, String::from("Unexpected error"));
+    }
+
+    fn parse_type_declaration(&mut self) -> Result<TypeDeclaration, ParsingFailure> {}
+
+    fn parse_binding(&mut self) -> Result<Binding, ParsingFailure> {
+        return self
+            .consume_if_and_map(
+                |it| match ((*it).token).clone() {
+                    // unfortunately, gotta clone to make the borrow checker happy. maybe i'll come back to this :3
+                    TokenType::Identifier(name) => Some(name),
+                    _ => None,
+                },
+                String::from("Expected identifier"),
+            )
+            .and_then(|name| {
+                let val = self.consume_if_match_nomsg(|it| (*it).token == TokenType::Colon);
+                if val.is_ok() {
+                    let blame = val.unwrap().blame;
+                    if let Ok(type_decl) = self.parse_type_declaration() {
+                        return Ok(Binding {
+                            name,
+                            arg_type: Some(Box::new(type_decl)),
+                        });
+                    }
+                    return Err(ParsingFailure::Blame(
+                        blame,
+                        String::from("Expected type declaration"),
+                    ));
+                }
+                return Ok(Binding {
+                    name,
+                    arg_type: None,
+                });
+            });
+    }
+
+    fn parse_assignment(&mut self) -> Result<Assignment, ParsingFailure> {
+        let binding = self.parse_binding();
+        if binding.is_ok()
+            && let Ok(ok) = self.consume_if_match(
+                |it| (*it).token == TokenType::Equals,
+                String::from("Expected equals after binding"),
+            )
+        {
+            return Ok(Assignment {
+                binding: binding.unwrap(),
+                computation: self.parse_computation(),
+            });
+        }
+        return Err();
+        //
+        //        if (self.consume_if_matches(|it| (*it).token == TokenType::Colon)) {
+        //            type_declaration = self.parse_type_declaration();
+        //        }
+        //        self.consume_if_matches(|it| (*it))
+        //        //return self.consume_if_matches(|it| match (*it)
+    }
+
+    fn parse_let_statement(&mut self) -> Result<&LetStatement, ParsingFailure> {
+        self.consume_if_match_nomsg(|it| (*it).token == TokenType::Identifier(String::from("let")));
+
+        let assignments: Vec<&Assignment> = Vec::new();
+        let assignment = self.parse_assignment();
+        self.consume_if_match_nomsg(|it| (*it).token == TokenType::Semicolon);
+    }
+
+    fn parse(&mut self) -> Result<ASTNode, ParsingFailure> {
+        let consume = |args| {};
+
+        //        let program: LetStatement = self.parseLetStatement();
+    }
+
+    fn new(tokens: Vec<Token>) -> Parser {
+        return Parser {
+            position: 0,
+            tokens,
+        };
+        
+    }
+    //    fn new() -> Parser {}
 }
 
 pub enum StepResult<T> {
@@ -164,9 +341,7 @@ impl<T> Environment<'_, T> {
     }
 }
 
-fn main() {
-    println!("Hello, world!");
-}
+fn main() {}
 
 #[cfg(test)]
 mod tests {
@@ -181,10 +356,60 @@ mod tests {
         let env = Environment::root(ident.clone(), &val);
         assert_eq!(env.get(ident.clone()), Some(&val));
         let env2 = env.add(ident2.clone(), &val2);
-        assert_eq!(env2.get(ident.clone()), Some(&val2));
+        assert_eq!(env2.get(ident2.clone()), Some(&val2));
         let env3 = env2.add(ident.clone(), &val3);
         assert_eq!(env3.get(ident2.clone()), Some(&val2));
         assert_eq!(env3.get(ident.clone()), Some(&val3));
         assert_eq!(env.get(ident.clone()), Some(&val));
     }
+
+    #[test]
+    fn test_lex() {
+        let prog = "let identity: ((Int) \n-> (Int)) = [a] { a };";
+        let analysis = Lexer::analyze(prog);
+        assert_eq!(
+            analysis[0],
+            Token {
+                token: TokenType::Identifier(String::from("let")),
+                blame: Blame { line: 0, char: 0 }
+            }
+        );
+        assert_eq!(
+            analysis[1],
+            Token {
+                token: TokenType::Identifier(String::from("identity")),
+                blame: Blame { line: 0, char: 4 }
+            }
+        );
+        assert_eq!(
+            analysis[2],
+            Token {
+                token: TokenType::Colon,
+                blame: Blame { line: 0, char: 12 }
+            }
+        );
+        assert_eq!(
+            analysis[7],
+            Token {
+                token: TokenType::Arrow,
+                blame: Blame { line: 1, char: 0 }
+            }
+        );
+        assert_eq!(
+            analysis[21],
+            Token {
+                token: TokenType::Eof,
+                blame: Blame { line: 2, char: 0 }
+            }
+        );
+    }
+
+    #[test]
+    fn test_parse() {
+        let prog = "let Identity: ((Int) -> (Int)) = [a] { a };";
+        let tokens = Lexer::analyze(prog);
+        let mut parser = Parser::new(tokens);
+        let ast = parser.parse().ok();
+        ast.unwrap();
+    }
 }