Add AST and parsing
authorLuke Lau <luke_lau@icloud.com>
Mon, 3 Jun 2019 14:45:10 +0000 (15:45 +0100)
committerLuke Lau <luke_lau@icloud.com>
Mon, 3 Jun 2019 22:58:16 +0000 (23:58 +0100)
commit5c4c0171f43b2d66cec3a882cdf2ecd904c83a1a
tree92a91a5079867369a71975a60c771c6c37cf0e01
parent30a26b7d2b0e17ea523ee34cb5d37242a38882df
parent8f977ec8c72bad55327ada3ef55d62f411cc44f9
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.