LLVM Tutorial #16: If Expression Parser

In this series I walkthrough the LLVM "Kaleidoscope" Tutorial, where you follow step by step to create your first programming language frontend using LLVM as the backend. Last time we made a "JIT"! This time we start implementing if statements, starting with the lexer and the parser.

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : hello there this is Toby and welcome
00:03 : back to the LLVM tutorial walkthrough
00:07 : series we're at the beginning of chapter
00:11 : 5 and last video we finished up chapter
00:16 : 4 and we have a working compiler
00:21 : which is honestly pretty amazing let me
00:26 : um let me show it off so my program is
00:30 : called my lang that's CC also to prep
00:36 : for this I have their code for chapter 5
00:39 : compiling successfully so if I run into
00:43 : trouble I have their code to refer to
00:47 : which I know already works okay let me
00:51 : run the code as it was finished at the
00:56 : end of chapter 4th to show you where we
00:59 : are at so we have this repre prompt and
01:04 : we can type in some code in the
01:08 : Kaleidoscope language and it will it
01:13 : will basically parse this code generate
01:17 : equivalent code in terms of LLVM ir
01:22 : which looks like that it prints that out
01:26 : to you that's the code in lob Mir it
01:29 : composed that down to machine code the
01:32 : machine code done is stored into the
01:35 : memory into some memory buffer in within
01:40 : the executable and then the memory
01:44 : buffer of instructions is executed and
01:48 : it returns to you this C function which
01:51 : when you call it will actually go
01:54 : through those instructions and execute
01:56 : them and the result of the execution
01:58 : gets printed out in this wrapper like
02:02 : this so that's what we have let's start
02:06 : chapter 5
02:08 : okay so chapter five is about if stamens
02:16 : and for loops so any so control
02:19 : structures which is actually really
02:21 : interesting so currently we have no
02:23 : control flow structure that's what we're
02:26 : going to add in this chapter so let's
02:31 : start with the if-then-else so an if
02:35 : statement in kaleidoscope looks like
02:37 : this again this kind of looks like Ruby
02:40 : I would say yeah it looks like Ruby the
02:44 : whole language is very ruby slash Python
02:47 : like so that makes sense I guess first
02:54 : step is we need to extend the lexer and
02:56 : the parser to be able to parse the if
02:58 : statement so let's go ahead and do that
03:03 : first we need the tokens that represent
03:07 : the if keyword the then keyword and the
03:10 : else keyword so let's go ahead and put
03:12 : those in so our lexer is that around the
03:16 : top of the file so I'll just copy design
03:21 : I won't bother typing them all out
03:23 : because is very straightforward and I
03:28 : wouldn't be learning that much by typing
03:30 : it all out now we we need to recognize
03:36 : the new keywords in the lecture this is
03:38 : actually easy because we already have
03:39 : example of how to do that so this is
03:41 : just get tok function is responsible for
03:46 : [Music]
03:50 : this in case you're joining us late and
03:54 : haven't followed every one of the
03:58 : previous episodes so let's say you're
04:03 : your string is space
04:15 : last get taupe is responsible for
04:24 : reading character by character and when
04:27 : it when it sees a token as a group it
04:32 : will return that thing as a token so you
04:34 : know first read it oh it's an I so I is
04:38 : a the character because of that I want
04:42 : to try to grab more characters so it
04:45 : will advance this arrow to the next one
04:47 : and so forth and then and then it will
04:50 : say oh there's an another alphabet
04:52 : character I'll put it into the group and
04:55 : then advance the arrow and O is a space
04:58 : so space should the limit a word so that
05:03 : this stops it so these two guys as a
05:08 : token so this is a token now and
05:11 : previously this would have been
05:13 : recognized as an identifier token
05:15 : because it was not put in the list of
05:19 : key word we had the DEF keyword and
05:21 : extern keyword and the keywords are
05:24 : recognized pretty simply by adding one
05:27 : of these if statements so because all
05:29 : we're doing here is adding keywords then
05:32 : add just add one of these if statements
05:34 : for each keyword so let's go ahead and
05:36 : do that until we just have if if not ID
05:47 : if then and else and in the case of if
05:52 : we're gonna say that while this token is
05:55 : of type Tok if yeah that one and if we
06:02 : if the word we found was done it's a
06:05 : token if then Tok then sorry
06:08 : and if the word we found was else then
06:11 : what the token is called Tok else so
06:14 : we're done with this part and yeah and
06:17 : that's exactly what the tutorial asked
06:20 : me to type by the way when you're
06:25 : working through a tutorial
06:30 : try to think at a higher level so I
06:34 : decided to do because I thought that I
06:37 : pretty much knew what I was what I was
06:39 : doing for this case I decided it to
06:42 : instead refer to the sort of copying the
06:49 : example code character by character I
06:52 : decided to just do it myself without
06:55 : looking at it if you feel up to doing
06:58 : that then by all means you should try
07:01 : that and I'm not talking about just this
07:06 : tutorial just tutorials in general okay
07:10 : AST extensions for if-then-else
07:13 : yeah so now we need ast nodes for the if
07:19 : expression we don't have an else
07:23 : expression or then expression because
07:26 : then and ELLs are just part of the if
07:29 : expression so what we have is I'm gonna
07:34 : refer to this code this time and type it
07:37 : in so we're gonna go to the section of
07:40 : code where I have these oh I don't know
07:43 : why I decided to end that like that
07:47 : actually I know why okay so I'm gonna so
07:53 : this is the section where I define the
07:55 : classes for the various ast node types
07:58 : that we have so I'm going to add a new
08:02 : one I will add it actually near the
08:06 : bottom or near the top near the bottom
08:11 : or at the bottom which is after you
08:14 : after the function of all these blank
08:18 : lines I'm going to remove them I'll do
08:21 : it here
08:24 : yes I will do it here okay so I'm gonna
08:27 : add a new class called if expert ast
08:31 : which is an ASU node that represents the
08:34 : if statement and again we're gonna use
08:39 : the unique pointer which is a managed
08:47 : pointer I think I don't know if it's
08:50 : totally man it's it's called a smart
08:52 : pointer and C C++ parlance okay this is
09:03 : B so this basically we have three three
09:08 : variables each one has the same type I'm
09:17 : gonna list them and line them up with
09:20 : each other so we have a then the current
09:26 : which is a condition and then and an
09:28 : else and then we're gonna have this
09:32 : initializer list this move thing is
09:41 : necessary in order to move when it's
09:44 : passed into this object when a
09:48 : constructor of this if expert ast object
09:51 : is created these unique pointers are
09:54 : passed in and we actually want to move
09:56 : the ownership of these three things into
10:01 : the object as in D as in my if expert
10:07 : ast object comes these three pointers
10:10 : now again I'm going to line them up with
10:16 : each other
10:23 : okay like that this we need this the
10:28 : body of the constructor which is going
10:31 : to be empty and over here and again
10:35 : we're gonna need to write the code gen
10:38 : for it but we're gonna do that later
10:43 : because we need to this is saying we're
10:49 : gonna overwrite the base classes
10:51 : definition of code gen but the base
10:53 : class has no real definition of cochin
10:56 : the base class has a virtual definition
10:59 : of coach kujan I actually will show that
11:04 : ya when you set the implementation of a
11:08 : method to zero in C++ that means this is
11:12 : a virtual method it's really bizarre
11:15 : that's how it works as documented by all
11:20 : the tutorials that I've found okay now
11:27 : let's write the parser for the if
11:31 : statement or the if expression I guess
11:40 : there are all these parse functions here
11:43 : are they function toward a method
11:46 : they're functions just we don't actually
11:49 : have a parse or a class come to think of
11:56 : it that's a little surprising but that's
12:00 : cool we just have a bunch of functions
12:02 : that parse the input so yeah unique
12:10 : pointer X / es t parse if Express so
12:17 : again if you haven't been following
12:20 : following along in the previous episodes
12:23 : we have a parse function for each
12:27 : concept in the language its syntactic
12:30 : element in the language so there's parts
12:35 : primary which a primer
12:37 : is like either an identifier our number
12:39 : or a sting in paren it's like an under e
12:42 : expression an expression that just has
12:45 : one thing in it we have parts identifier
12:48 : or Co expression parts paren expression
12:52 : etc etc etc I'm going to add a parse
12:57 : function for if expressions so first
13:01 : we're gonna get next token which eats
13:03 : the if so the way this works is whoever
13:09 : is calling the parse if expression they
13:11 : have already detected that the current
13:13 : token is the if statement and then it
13:18 : when it sees that the current token is
13:21 : the if keyword it dispatches this
13:23 : function it will once we're done writing
13:26 : all the code that needs to be written so
13:29 : this get next token just advances the
13:31 : pointer so like it's like oh we have
13:36 : this token called if okay so let me
13:41 : advance the pointer so that we're
13:44 : looking at the next thing whatever that
13:47 : thing is and then after the if statement
13:56 : there should be an expression because
13:58 : it's like if n plus if n greater than 1
14:01 : and the N greater than 1 would be the
14:03 : expression that we're gonna defer to the
14:07 : parse expression function to parse that
14:09 : and then we'll check whether that
14:11 : succeeded or not
14:12 : so it's like you for the condition here
14:16 : if you if it didn't work I'm gonna
14:19 : return the null pointer and in this
14:22 : parser a null pointer is a signal that
14:24 : it didn't work so yeah it didn't work
14:29 : although it doesn't it doesn't totally
14:31 : stop the world either it's a little
14:35 : ambiguous actually sometimes we log an
14:38 : error like this sometimes we don't oh
14:41 : but I guess even in cases where we login
14:44 : there are we
14:45 : return a null pointer so returning null
14:47 : just means parsing this thing did not
14:50 : work whatever that thing is
14:54 : okay so now we're gonna say okay we we
14:59 : parsed to an if statement again in this
15:04 : language it's like if it's greater than
15:07 : two
15:08 : although I don't think the greater than
15:10 : sign is part of the language
15:14 : so it's like if n is great less than two
15:18 : then we're gonna say times two else
15:24 : maybe I don't know maybe that's the if
15:30 : statement so we're saying hey we were
15:34 : looking at the if statement now we're
15:36 : gonna advance the pointer and have
15:39 : parsed expression parse this in less
15:43 : than two part part expression is going
15:46 : to parse this part is if it was
15:52 : successful it's gonna end up being being
15:56 : that condition that's returned so then
15:59 : now the cursor is over here and then
16:02 : we're gonna say okay well actually the
16:05 : cursor should be over here and now we're
16:07 : saying hey are we looking at the den
16:09 : token now we should be if it's a valid
16:12 : estimate if it's not then if it's not a
16:16 : den token we actually don't really know
16:18 : what to do wait so so it's gonna print a
16:21 : error it's gonna log in here
16:26 : so that's what this code does I I
16:35 : decided to detour they do it a little
16:39 : differently from the way the tutorial
16:41 : does it the tutorial has a variety of
16:44 : log error functions which return a
16:47 : variety of different types of things but
16:50 : in reality all those functions return
16:52 : null and so instead of doing that I
16:56 : didn't want to bother writing a variety
16:59 : of log error functions so I just have
17:01 : one log error function then after
17:05 : calling the logger function I'm just
17:06 : gonna manually return null pointer that
17:09 : this way I don't have to have a variety
17:13 : of log error functions and that's what I
17:15 : prefer okay so this eats today
17:30 : okay so now it's it's gonna it's gonna
17:34 : parse the part after the den now so see
17:38 : it eight to then keyword eat den then
17:41 : eat the then after eating this den
17:46 : keyword then then then is gonna advance
17:53 : the pointer to this and token and we're
17:56 : gonna call this parse expression one
17:58 : more time and expect it to parse this
18:02 : expression and say this expression is
18:05 : what represents the den this expression
18:08 : is what represents to them
18:10 : this one is the cond we have two cond
18:12 : and then the den and then later on we'll
18:15 : have the else so this guy is the cond
18:20 : this guy is the den and this guy is
18:23 : going to ptl's and those are the three
18:27 : parts of an oops three parts of a if
18:30 : expression node as we saw when we were
18:35 : creating that if expression AST class
18:41 : now if we it was not successful in
18:44 : parsing the den part then again return
18:49 : the null pointer it didn't work
18:57 : and again we're expecting an else here
19:01 : so if we're not looking at an else after
19:04 : parsing the expression for them then
19:07 : there didn't work
19:09 : expect it now nick up next token just
19:22 : eat the else why does that still see it
19:27 : done then EDL's
19:30 : they didn't put in accounting et else
19:33 : but I know what they meant so now we're
19:36 : gonna Auto is like var in some languages
19:43 : but it allows you to not have to
19:46 : explicitly write out the name of the
19:49 : class I mean the name of the type of
19:51 : this variable in for it you know let the
19:55 : compiler in for it because compilers
19:59 : nowadays are pretty smart
20:05 : even C++ Oh
20:22 : so now we're successful in parsing all
20:26 : three parts the condom and the else we
20:30 : can put them together and say hey now we
20:34 : can have an if exper ast and if you're
20:38 : confused by this make unique just think
20:41 : of it as kneeling up kneeling up an
20:44 : instance of this class except you point
20:48 : to it using a unique pointer which is a
20:53 : which is called a smart pointer okay so
21:03 : there we have it oh actually one thing I
21:05 : want to tell you about
21:06 : I made an enhancement to my website this
21:11 : past week which is that the videos if
21:17 : you click on a video link on my website
21:21 : for most of the videos that I have put
21:25 : out it it now has this page which shows
21:30 : you the transcript the text transcript
21:32 : of the video so you could you could skim
21:37 : through
21:38 : skim through the text if you want and
21:41 : you can click on one of these time
21:43 : markers to jump to a particular location
21:46 : in the video if you want to so hopefully
21:50 : this will help some of you who are
21:54 : interested in this material but but feel
21:59 : like there's too much material to go
22:01 : through you can sort of look for and
22:04 : skip to the part or the episodes that
22:07 : are you're interested in I think there
22:12 : is one episode where I talk about smart
22:14 : pointers maybe does I don't I don't
22:16 : remember which one okay so now now I
22:22 : have a function that can parse if
22:25 : expressions now I think
22:28 : but we have to dispatch to it so we're
22:32 : gonna go to the parts primary function
22:34 : which I saw already and add a dispatch
22:38 : for the parse if expert which kind of
22:42 : looks like this like case is an if
22:45 : stokin right I'll just add it to the top
22:47 : here please we're looking at the if
22:50 : token then we want to dispatch the parse
22:54 : if expert to parse an if statement which
23:02 : is what they put at the bottom I put at
23:05 : the top it should work either way okay
23:10 : so now we have a parser I wonder if it
23:15 : compiles so Oh something I've changed
23:19 : actually offline is that I changed my
23:30 : build script to take a command-line
23:33 : argument instead of hard-coding the name
23:36 : of the file that I'm going to compile so
23:40 : it references to command-line argument
23:43 : this is bash by the way and I'm sorry if
23:46 : you're not on a UNIX system this is not
23:50 : gonna work out for you if you're on like
23:53 : Windows so I'm sorry about that I might
23:57 : I might try all of this compiling all of
24:00 : this code on Windows at some point and
24:03 : if I do I will share that as well but
24:06 : anyway this is for UNIX and this is how
24:08 : you reference a parameter and then this
24:12 : is how you substitute the file extension
24:16 : so this substitutes the CC file
24:19 : extension of the file with a dot bin
24:21 : extension so now the way I use my build
24:25 : script is a core built
24:28 : then the name of my file and then you'll
24:33 : build a binary that way with the prefix
24:39 : of my file dot bin so it's gonna
24:41 : generate a my Lang bin well if it works
24:44 : which it didn't Hemi fix this first
24:50 : problem
24:51 : three three I'm not sure if I can get
24:54 : everything to compile at this point I
24:56 : was saying use of undeclared identifier
24:59 : parts if so it's saying at the point
25:03 : where I tried to call this parse parsed
25:08 : if X power function the compiler hasn't
25:12 : seen it yet so I think for this case I
25:15 : can just move this part if Express
25:19 : function up by one so that it would be
25:24 : able to see
25:37 : okay so
25:53 : core to implicitly deleted copy
25:56 : constructor of unique today
26:18 : did I write this wrong mm let me
26:22 : double-check it with their code here
26:35 : you
27:05 : the error is about line 333 which is
27:13 : here
27:40 : hmm I'm not sure what the problem is hmm
27:47 : I thought that I'm gonna try to just
27:49 : copy the code but I yeah
27:52 : just in case I made a mistake cuz I
27:56 : don't really have a clue about what the
27:59 : problem is same problem so it wasn't my
28:15 : cook that was the problem it could be
28:19 : that it's because wait
28:30 : we do it could be that it's because I
28:37 : haven't finished the code and the next
28:40 : part that we would do is just is
28:46 : implementing the coach and method of the
28:51 : if expert ast node so I could test that
29:00 : hypothesis really quick and say hey if I
29:06 : just implement the code gen method I
29:12 : mean I mean just look at their code if
29:18 : we if it did work this this this
29:22 : paragraph is saying once we get it
29:24 : working the LLVM code is gonna look like
29:27 : this oh this actually tells you if you
29:35 : put this LLVM code into a file call it t
29:39 : dot ll we can use this o LVM - es which
29:46 : a sa stands for assemble oh and then you
29:52 : can analyze this very interesting ok so
29:59 : that is a very interesting actually I
30:02 : want to dig into this a little bit and
30:06 : abandon my hunt in trying to fix this
30:09 : error message for now we'll eventually
30:12 : get this fix but I think we've completed
30:17 : building out the parser we haven't been
30:20 : able to test it yet unfortunately but um
30:24 : I'll stop this episode here and then in
30:27 : the next episode we'll look into this
30:30 : LLVM code here for for the if statement
30:35 : and see how it works and what it looks
30:37 : like