kaleidoscope-hs.git
4 years agoAdd AST and parsing
Luke Lau [Mon, 3 Jun 2019 14:45:10 +0000 (15:45 +0100)]
Add AST and parsing

The first step in our compiler is to convert the source code into some
sort of data structure that we can work with. This data structure
usually ends up being a tree structure: nodes of expressions built up of
other expressions. For example, (1 + (3 - 2)) would be a tree where 1, 3
and 2 are leaf nodes and +/- are parent nodes.

It represents the syntax of the program, but is abstract as it doesn't
contain the details about it like whitespace or parenthesis: an abstract
syntax tree, if you will.

In the original LLVM Kaleidoscope tutorial, this abstract syntax tree
(AST) is usually built by first lexing the program into separate tokens
like identifiers and keywords, and then parsing it to build up the tree
structure. We're not going to do that in this tutorial, and instead opt
for the Haskell-ier way with parser combinators.

Parser combinators allow us to lex and parse at the same time by simply
specifying what we expect to parse. We'll be using the ReadP monad,
which is also used for the Read class: In fact we'll just be able to
parse our program by calling 'read'! The P in ReadP stands for
precedence, and you'll see later on we'll be able to add some tricks to
prefer certain patterns over others when parsing. We'll also be writing
all our parsing with do notation, which I think you'll agree feels very
natural to use.

4 years agoAdd basic repl
Luke Lau [Sat, 18 May 2019 20:11:11 +0000 (21:11 +0100)]
Add basic repl

For the moment this doesn't have any parsing errors other than "Couldn't
parse". We'll go back to this later!
Also note we're printing to stderr.

4 years agoParse call expressions
Luke Lau [Sun, 19 May 2019 13:16:31 +0000 (14:16 +0100)]
Parse call expressions

The Call constructor stores the name of the callee and the list of
arguments being passed to it.

4 years agoParse parentheses
Luke Lau [Sat, 18 May 2019 19:32:54 +0000 (20:32 +0100)]
Parse parentheses

Yes, it's that easy. Try out the difference between
1 * 2 + 3
and
1 * (2 + 3)

4 years agoParse defs and externs
Luke Lau [Sat, 18 May 2019 16:54:06 +0000 (17:54 +0100)]
Parse defs and externs

They both share a common prototype so we can split that out into a
separate definition. We also want to be able to parse top level
expressions, so we add constructor for that in AST.
Hopefully now you can see the beauty of monadic parsing:
Function <$> readPrec <*> readPrec

4 years agoParse variables in expressions
Luke Lau [Sat, 18 May 2019 16:51:22 +0000 (17:51 +0100)]
Parse variables in expressions

4 years agoParse more binary ops
Luke Lau [Sat, 18 May 2019 16:17:41 +0000 (17:17 +0100)]
Parse more binary ops

We can parameterise the precedence that we parse so that * is parsed
before +/- etc.
Try it out with `ghci AST.hs`, and see the difference between
*AST> read "1 * 2 - 3"
and
*AST> read "1 + 2 - 3"

4 years agoStart parsing expressions
Luke Lau [Sat, 18 May 2019 15:53:40 +0000 (16:53 +0100)]
Start parsing expressions

This starts off with defining not the AST, but just what expressions we
want to be able to parse.
So far we just handle numbers, and addition involving 2 numbers.
We use the built-in ReadPrec parser combinators, which allow us to
recursively parse the binary op of addition, and even allow us to reuse
the Read instance on Int!
prec and step are needed since without them, parseAdd will just get
stuck repeatedly trying to parse the left expression (a).

4 years agoInitial commit
Luke Lau [Sat, 18 May 2019 15:28:49 +0000 (16:28 +0100)]
Initial commit