diff options
| -rw-r--r-- | gock.ts | 42 | ||||
| -rw-r--r-- | grammar.txt | 12 | ||||
| -rw-r--r-- | src/main.rs | 255 |
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(); + } } |