From: Luke Lau <luke_lau@icloud.com>
Date: Mon, 3 Jun 2019 14:45:10 +0000 (+0100)
Subject: Add AST and parsing
X-Git-Url: http://git.lukelau.me/?p=kaleidoscope-hs.git;a=commitdiff_plain;h=5c4c0171f43b2d66cec3a882cdf2ecd904c83a1a

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.
---

5c4c0171f43b2d66cec3a882cdf2ecd904c83a1a