LLVM Tutorial #20: For loops!

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 finished implementing if statements. This time we continue on to the second half of chapter 5 and implement the parser for the for loop expression.

Transcript

The following transcript was automatically generated by an algorithm.

00:01 : hello there uh welcome back
00:03 : to the series where we uh we we're
00:06 : walking through the llvm tutorial
00:11 : called uh kaleidoscope or it's actually
00:14 : called
00:15 : i believe getting
00:18 : no it's called like making your first
00:23 : programming language front end with llvm
00:26 : and uh if you've been following along
00:28 : with the series
00:29 : you've uh walked through uh four
00:32 : chapters
00:33 : and a half of this tutorial
00:37 : which contains eight chapters i took a
00:40 : hiatus from this project but i'm
00:42 : i've decided to continue on with it and
00:45 : hopefully bring it to completion
00:47 : um as part of my the hiatus
00:51 : uh from this project uh another project
00:54 : that i worked on
00:56 : a few months ago was uh was
00:59 : a programming language uh written
01:03 : where the parser and the generator was
01:05 : written in javascript
01:07 : but it spits out llvm uh
01:10 : llvm code so um
01:14 : and i actually brought this project to
01:16 : pretty far
01:17 : i put a whole bunch of work into this uh
01:20 : unfortunately i didn't document this
01:22 : project with any videos but
01:24 : if you are interested in looking at the
01:27 : source code
01:28 : then uh have at it this is the url over
01:32 : here
01:33 : um if there's any interest in me
01:37 : making videos uh sort of showing
01:40 : how this code works please let me know
01:43 : in the comments
01:44 : and then i may i may do that sometime in
01:47 : the future
01:49 : for this video i'm going to continue on
01:53 : exactly where it left off where i left
01:55 : off was
01:57 : we have actually completed
02:00 : half of chapter five and that
02:03 : the first half was implementing if
02:06 : statements in the language
02:08 : the second half which i'm going to
02:10 : attempt now is going to be implementing
02:13 : the for loop expression
02:15 : which is gonna look like this which
02:18 : looks kind of like a cross
02:20 : between a c
02:24 : plus plus a for loop
02:27 : and a python for loop maybe it's more
02:31 : like a
02:32 : basic for loop
02:35 : in any case uh we're gonna do this
02:39 : uh let's see where the tutorial takes us
02:43 : okay first we're gonna need uh lecture
02:46 : extensions
02:48 : um for the for loop i
02:52 : am not quite sure what this syntax means
02:56 : honestly uh is this some sort of
02:59 : grammar that i haven't seen before
03:03 : um did they use this syntax
03:06 : earlier they kind of did
03:10 : wait a minute oh
03:13 : oh i i i'm looking at the wrong version
03:16 : of this tutorial that's why
03:18 : this is the old camel version of the
03:20 : tutorial
03:23 : but i want the c plus plus version
03:28 : not the o camo version let me see
03:34 : there we go okay all right we're good
03:38 : now so
03:38 : if you look if you're like me
03:42 : you looked at that syntax you got a
03:45 : little confused
03:46 : uh because you haven't seen the old
03:49 : camel code before
03:51 : uh that's why so we're gonna stick with
03:54 : the c
03:54 : plus plus version although if you prefer
03:56 : ocamo then by all means
03:58 : go for that so the first thing we're
04:00 : going to do is
04:02 : add the definition for
04:05 : a token a lecture token for the
04:08 : for keyword and we'll add
04:11 : a line of code to recognize that
04:15 : so um that one of the lines is
04:19 : over here so let me see talk four
04:23 : i would assume
04:26 : uh yeah and in so we're gonna have an in
04:29 : keyword as well which is part of the
04:33 : for loop statement and then
04:37 : later on in this cascading
04:41 : if statement i mean uh yeah
04:45 : the this i don't know if the word
04:48 : cascading is correct
04:49 : but this series of if statements we're
04:52 : gonna add
04:53 : two of them um i'm just gonna copy it
04:56 : because this is all very
04:59 : self-explanatory
05:01 : uh and i don't feel like
05:04 : i'm uh
05:08 : i'm getting value out of typing it all
05:11 : out
05:12 : in general if you've seen my
05:15 : walkthroughs i prefer to type things out
05:18 : if i think i can learn something from
05:22 : that process okay now that we have
05:26 : the lecture we're going to add a
05:29 : parser component to this
05:34 : oh is this the part no this is the ast
05:37 : node we're going to add an ast node
05:40 : for the for loop expression
05:44 : that's what we're doing so we're going
05:46 : to go down to the section where
05:48 : we have all of these ast nodes the ast
05:51 : nodes are classes
05:53 : each of which pose fixed
05:56 : uh ending in ast
06:00 : to add one maybe close to the bottom
06:03 : here
06:04 : we have functions
06:09 : maybe after the if statement where's the
06:13 : if
06:13 : okay
06:17 : yep okay so i'm gonna
06:22 : this part i'm gonna sort of copy it over
06:26 : i'm gonna type out the statements
06:30 : um i'm gonna move this over a little bit
06:34 : okay let's go for this maybe make this
06:37 : font a little bit smaller
06:50 : there it is all right let me try this so
06:52 : class
06:53 : for expert ht public
06:57 : it it extends the the base class
07:01 : for the expert ast
07:07 : for for the ast notes which is called
07:10 : the expert ast
07:13 : and then we're going to have a var name
07:16 : as the string i believe this is like
07:19 : something like
07:20 : 4 n
07:23 : equals 0 comma and
07:27 : what was the syntax again
07:32 : and while this is while oh
07:35 : let's go with i so for i is
07:38 : 0 while i is less than 10
07:42 : and this is the amount to increment i
07:46 : guess
07:47 : and then you say in and then your
07:51 : the next statement can have i inside the
07:56 : scope
07:59 : i think we can do something like this so
08:01 : this var name i believe
08:02 : would have been this i or whatever you
08:05 : chose to name it
08:07 : okay um so this is the for name
08:12 : i'm gonna have a unique pointer to an
08:15 : expression ast
08:19 : one for each of these parts
08:22 : and each of these parts is a there's a
08:24 : start and an end
08:27 : i think this is the start this is the
08:29 : end
08:30 : the step is this number here and the
08:33 : body would be
08:35 : this here okay so we have an ast
08:38 : note for each of those chunks
08:43 : and then
08:54 : we basically okay i'm not gonna type
08:57 : these out because
08:58 : it's very rapid repetitive but
09:01 : essentially what it is
09:06 : um
09:11 : essentially what it is is listing out
09:14 : every instance variable that we have
09:17 : previously defined uh as
09:21 : a parameter of the constructor
09:26 : um and then so and then
09:29 : and then we're gonna list all of them
09:31 : out again as as
09:33 : part of this static initializer list
09:37 : i believe that's what they are called
09:39 : and this is kind of
09:41 : tedious as well so i'm going to type
09:44 : so this is basically for name
09:48 : i believe that references this one this
09:50 : this bar name
09:51 : references this one whereas this var
09:54 : name references this one
09:56 : both of them happen to be the same name
09:59 : which is quite confusing
10:00 : um and then the next part we're going to
10:04 : have to use
10:05 : standard move because this is a unique
10:08 : pointer
10:09 : unique pointer is something actually
10:10 : during the hiatus i've
10:12 : learned a little bit more about so i
10:14 : hopefully i can speak to it a little bit
10:16 : more
10:17 : now than previously a unique pointer is
10:20 : a pointer where if
10:24 : within the body of some code
10:27 : you have a pointer
10:31 : to a particular object in the in dynamic
10:35 : memory also aka the heap then that
10:39 : pointer is the only pointer that's
10:41 : allowed to point to that object
10:43 : um as as in all other pointers
10:47 : to that object in other scopes of the
10:50 : code
10:51 : are invalid but because of that uh if
10:54 : you want to
10:54 : pass this pointer to another
10:58 : variable or or you want to pass this
11:00 : pointer to
11:01 : as a argument of a function because you
11:04 : want that function to have
11:06 : access to this object in the dynamic
11:09 : memory
11:10 : well you have to invalidate yourself
11:14 : to make the argument or the other
11:18 : variable
11:19 : the other pointer that you're passing to
11:22 : uh valid
11:23 : so that process of that transference
11:27 : the transfer of the validity of the
11:29 : pointer
11:31 : happens using the standard move method
11:34 : which is saying whoever passed their
11:37 : unique pointer
11:38 : into us i just noticed i misspelled this
11:43 : so i'm going to fix that
11:44 : yeah so whenever we were saying like a
11:47 : new for
11:51 : expert ast and they're passing in this
11:54 : well first they're passing in a variable
11:57 : name
11:58 : and then they're passing in this expert
12:00 : est
12:03 : and then dot dot so this is a unique
12:06 : pointer
12:07 : and from the scope of this line this
12:10 : unique pointer
12:11 : is um
12:15 : is a going to be valid in this scope but
12:19 : once it gets passed
12:20 : in it has got to be valid in the scope
12:23 : of the constructor for this stuff to
12:25 : work
12:28 : so they will actually have to
12:31 : move this thing i think they will
12:34 : actually have to type
12:36 : this standard move here as well but we
12:38 : also have to type the standard move
12:41 : in the initializer list as well which
12:44 : actually it's i'm not totally sure why
12:47 : we have to do it
12:48 : both here and here if you know why
12:52 : please tell me in the comments um by the
12:55 : way thank you for everyone who has
12:57 : uh who has contributed in the comments
13:01 : uh teaching me more about c
13:04 : plus plus so yeah if if you can
13:07 : enlighten me about
13:09 : like why i need to write standard move
13:11 : here when i'm calling the constructor
13:13 : and also
13:14 : i have to write standard move here in
13:16 : the initializer list
13:18 : please enlighten me
13:22 : so okay i don't feel like typing all of
13:25 : this out so i'm just gonna copy the rest
13:27 : of this
13:32 : okay and then finally
13:36 : i'm going to do this code gen
13:40 : override thing uh
13:44 : which i believe that's saying i need to
13:46 : override
13:47 : the code gen method that's
13:50 : declared in the base class
13:53 : i want when you call code gen i want
13:57 : you to be calling my version of the code
14:00 : gen that's declared for
14:02 : the for expert ast class
14:06 : and then i assume later on we're going
14:08 : to have a
14:10 : actual implementation of this code gen
14:13 : method
14:14 : to come okay
14:19 : so now
14:26 : all right we're gonna we're gonna
14:27 : implement the parser
14:29 : that will be able to recognize the new
14:32 : syntax
14:33 : and generate an ast note here
14:36 : let me find a good place to put that
14:38 : parser code
14:44 : is this code formatted weird
14:48 : okay
14:56 : okay i'm gonna put the parser code
14:59 : after the one for the if statement
15:03 : i believe or
15:06 : or the prototype one maybe
15:11 : where's the parser code for the if
15:13 : statement
15:14 : no there it is okay this is the partial
15:17 : code for the if statement so i'm gonna
15:18 : put
15:19 : this code right after it and
15:22 : the parser is currently
15:25 : implemented as a series of um
15:30 : static functions
15:38 : okay
15:43 : okay so first we're gonna get the token
15:46 : uh which
15:46 : it it's it i again is
15:50 : the convention of this code base is that
15:52 : before it calls
15:54 : this um this
15:57 : parse whatever function in this case the
16:00 : for
16:00 : statement the for expression it has
16:03 : already seen that
16:05 : there's a four token so it just assumes
16:09 : the the next token is the fourth token
16:12 : because whoever calls it has already
16:14 : determined that
16:15 : so the first thing is we're just gonna
16:17 : eat the four token
16:21 : um and then we're going to say
16:24 : uh the next token
16:28 : after that which is the kertoke the
16:30 : current token
16:32 : we're expecting that guy to be a
16:35 : token identifier token
16:38 : uh which is
16:41 : who is it oh gosh i'm gonna
16:44 : i'm gonna split my split my editor here
16:53 : there it is okay
16:56 : so for here okay
17:00 : so this guy is supposed to be an
17:03 : identifier token this eye here
17:05 : so so this this um
17:12 : so then what this code is doing is
17:14 : saying
17:15 : well if it's not an identifier that i'm
17:18 : confused i'm gonna err out
17:28 : okay and then i'm gonna log i believe i
17:31 : implemented it the log
17:34 : function in a slightly different way
17:38 : from how they did it so i'm going to
17:40 : reference
17:41 : my own code for how i do this i just
17:44 : call
17:45 : lock error
17:49 : okay expected identifier
17:53 : after four
17:56 : yep and i'm just gonna
18:00 : return null pointer separately
18:04 : okay like i disagree with how the author
18:06 : wrote
18:07 : this thing so i decided to do it
18:11 : differently
18:12 : um so now we're gonna try to get the
18:15 : identifier
18:17 : now which is actually just there's a
18:20 : global variable called
18:22 : identifier string as i remember
18:25 : uh which would already contain that
18:28 : identifier string
18:30 : so
18:39 : and then we're gonna eat that token
18:45 : and by eat uh i
18:48 : we also by eating the token we also
18:51 : advance
18:51 : the token cursor to the next token and
18:54 : the stream so now that we've
18:57 : advanced the cursor the next token we
19:00 : should be looking at
19:01 : is the equals token because again
19:04 : it looks like
19:08 : i should probably write that here
19:11 : so again the
19:14 : the syntax looks like something like
19:22 : this
19:28 : the syntax should look something like
19:30 : this uh so
19:31 : we we've parsed the four
19:35 : there and then advanced to here
19:38 : and then it would get an identifier and
19:40 : then we're gonna advance
19:42 : and now we should be getting this equal
19:45 : sign
19:45 : so this is just saying hey if it's not
19:49 : an equal sign
19:52 : we have a problem
20:09 : and then we're gonna eat it
20:17 : okay after that we're to have we're
20:20 : going to
20:20 : parse
20:23 : this 0 here
20:26 : and that is actually going to be the
20:29 : start
20:32 : expression okay
20:35 : so
20:42 : and if we are unable to parse that start
20:47 : token then we're going to return no
20:49 : pointer to signal a failure
20:53 : otherwise we keep going so now
20:57 : i i'm going to assume that whatever
20:59 : parse expression
21:01 : the reason we're parsing expression even
21:03 : though this is only a number is because
21:05 : well this could potentially be like a
21:08 : more complex
21:09 : expression like a plus b right so we
21:13 : that kind of thing uh need to be dealt
21:15 : with
21:16 : so we we call out to parse expression to
21:19 : parse this
21:21 : initial value uh or the start value for
21:26 : for i or whatever that variable name
21:28 : happens to be
21:30 : and then we're gonna say okay we're
21:33 : gonna try to match a
21:35 : comma now
21:47 : and if we don't get a comma again
21:50 : that's a problem so we will print this
21:53 : error
21:55 : statement and then return a no pointer
21:59 : to signal that it didn't work
22:03 : and then we're gonna advance this token
22:05 : and then our
22:06 : advanced to here and we should see
22:09 : another identifier
22:11 : so that's uh wait wait wait wait wait
22:22 : oh the end so we we're parsing an
22:26 : expression so this entire thing is going
22:29 : to be the expression
22:30 : which signals the end okay
22:34 : that makes sense
22:43 : and if we don't get the end
22:46 : then we're gonna again return the null
22:50 : pointer to signal that it didn't work
22:53 : and then the step value is optional
22:56 : so this i guess this last
23:00 : this last bit is optional i guess if
23:03 : they don't supply it
23:05 : we're gonna assume
23:08 : it's one or something um
23:14 : yeah probably uh so
23:19 : in any case we're going to uh
23:33 : we're going to expect that this comma
23:36 : exists or i guess in this case it's like
23:39 : if it doesn't
23:40 : exist that's okay we're gonna
23:44 : uh so so it's like it does it because
23:47 : it's
23:47 : optional we're not gonna not going to
23:52 : require that it'd be there
23:55 : therefore we don't we don't log the
23:57 : error if it's not there and we would
24:00 : if we detect that it's there there's a
24:02 : comma
24:04 : then we try to parse
24:07 : this step this step
24:11 : value but but they're saying this is
24:13 : optional so they could have written it
24:15 : like this without the comma 1.0
24:18 : but but it would be wrong to have a
24:21 : comma
24:22 : but no number in there however which is
24:25 : why
24:25 : we we still have this check to see if
24:27 : they they put a comma here
24:30 : but we're not able to parse the
24:32 : expression
24:33 : then that's a failure as well and we
24:35 : signal that
24:36 : with a no pointer
24:40 : okay i'm going to say get next token
24:42 : this is
24:44 : to advance past this comma to the next
24:48 : thing and then
24:56 : we're going to call a parse expression
24:57 : to parse what the step is
24:59 : and if that didn't work we're going to
25:01 : return a null pointer
25:02 : now we're
25:06 : expecting this in keyword now
25:10 : i'm going to say if it's not that that's
25:13 : a problem
25:14 : and we're going to error out
25:25 : and return the null pointer otherwise if
25:28 : it
25:29 : if everything is fine we're gonna eat
25:31 : the token
25:32 : which advances the token pointer to the
25:35 : next thing
25:36 : uh which will we will advance
25:39 : past all of this and the next thing
25:41 : should be the body of the function which
25:43 : is just
25:44 : one expression so again we call parse
25:46 : expression
25:48 : to parse that
25:54 : so if there isn't a body i'm gonna
25:57 : return a null pointer
26:00 : now finally we're ready to create a ast
26:03 : note that represents this entire for
26:06 : statement
26:07 : and uh yeah you can see we we need to do
26:10 : these
26:11 : standard colon colon moves
26:14 : here to move each of these start
26:17 : and step and body they're unique
26:19 : pointers so we need to
26:21 : do this move which invalidates
26:25 : the the variables
26:29 : here the pointer variables here
26:31 : invalidates them
26:32 : and makes the pointers within
26:36 : the class valid
26:39 : so that's what's happening
26:43 : so we're going to make a unique pointer
26:49 : ast and then we have an id
26:52 : name i'm going to standard move the
26:55 : start
26:57 : standard move the end
27:01 : standard move the
27:06 : step
27:09 : standard move the body
27:13 : and that's the end of this function and
27:16 : now
27:16 : we need to hook it up as a primary
27:19 : expression
27:20 : so there's this parse primary
27:25 : function which has this huge
27:28 : well it's not that huge at this point
27:31 : it could eventually it could get huge
27:34 : but uh there has this switch statement
27:36 : that uh given the what the type of the
27:39 : current token
27:41 : it dispatches it out to one of these
27:43 : specific
27:44 : parts parts or functions so we're going
27:47 : to add one
27:48 : for the for statement
27:52 : the other lid down here it doesn't
27:55 : matter
27:55 : where you add it i guess i'll add it
27:57 : that's the second thing
28:02 : so here we we call the function that we
28:05 : just wrote
28:06 : here that's how it actually gets
28:09 : utilized
28:11 : okay now
28:16 : um i might want to try to compile this
28:21 : at this point let me see if it works
28:24 : i'm going to say build my lang.cc
28:31 : and maybe this compiles and if it
28:34 : compiles
28:36 : well if it doesn't compile then it will
28:38 : help me uh
28:39 : fix my syntax errors so i think i
28:42 : forgot to get rid of this i was just
28:44 : writing this line as an example
28:46 : here try again
28:52 : my battery is getting low okay
28:58 : um all right we have some errors
29:04 : unknown type name is td
29:07 : oh i need two colons here instead of one
29:10 : so let me go fix that
29:17 : hopefully that's enough to fix
29:24 : it
29:48 : duh okay
29:55 : a missing v table
30:03 : uh
30:06 : oh missing v table for
30:10 : [Music]
30:11 : this some v table is the thing you use
30:15 : for um
30:18 : for dynamic uh overriding
30:22 : of methods such as this one
30:26 : so missing v table
30:32 : is this a missing v table usually means
30:35 : the first non
30:36 : inline virtual member oh yeah
30:40 : we haven't defined we haven't defined
30:43 : the cogen
30:44 : method and that's why we have this
30:47 : error so uh uh perhaps
30:52 : um
30:56 : the code gen is what we should do next
30:59 : but uh i'm gonna
31:00 : i'm gonna stop this session here
31:04 : and uh and implement the code gen
31:07 : in the next video um
31:10 : so i will i will see you over there