LLVM Tutorial #3: AST Nodes

I am learning LLVM. In this series I am planning to walk through the introductory tutorial called Kaleidoscope at https://llvm.org/docs/tutorial/MyFirstLanguageFrontend/. In the last episode we finished making the lexer which supplies us with tokens. This time we start working on the parser that generates the AST. Beginning with creating classes for the various types of AST nodes.

Transcript

The following transcript was automatically generated by an algorithm.

00:02 : hello there this is Toby and we're gonna
00:05 : continue the series where we follow the
00:10 : LLVM tutorial to make a toy programming
00:16 : language called kaleidoscope so yeah
00:21 : we're at Chapter two
00:24 : last episode and last chapter chapter
00:27 : one we made a lecture which is able to
00:30 : give us a series of tokens so they type
00:35 : in a number like 2345 they'll recognize
00:41 : it as a number and I know we recognize
00:44 : it as a number because negative 5 is the
00:49 : code for a number token token number and
00:52 : if I type in something that looks like a
00:55 : variable name that's fubar fubar
01:01 : definitely looks like a variable name
01:03 : and it recognize it as negative 4
01:06 : negative 4 is the token type for
01:11 : identifiers right there's also a token
01:15 : type for the DEF keyword and externally
01:18 : word as well so death an extern yield
01:22 : their respective token type numbers so I
01:28 : can verify that the lecture works again
01:33 : all of the code is supplied by the
01:35 : tutorial so although there might be
01:39 : places where I decided to go off on my
01:42 : own a little bit if I'm feeling brave
01:44 : but for the most part I'm gonna be
01:45 : following the code in the tutorial and
01:48 : at various points in the tutorial they
01:51 : actually give you the full listing of
01:53 : the code like at the end of chapter 2
01:55 : this section do get give you the full
01:58 : source code so in case you made a
02:00 : mistake somewhere along the way that you
02:02 : can figure out how to solve you always
02:05 : just copy their code and have a working
02:08 : if the kid okay so in Chapter two that's
02:13 : what we're doing
02:14 : I might split this up into two parts I'm
02:17 : not sure yet because chapter two is kind
02:19 : of a long a long lengthy section of this
02:26 : tutorial I'm gonna be making a recursive
02:30 : descent parser complete with operator
02:34 : president's parsing and this is actually
02:38 : something that's very interesting to me
02:40 : personally because I've been recently
02:44 : spending some time learning these things
02:47 : how to how to hand code a recursive
02:51 : descent parser in particular without
02:54 : using the help of a parser generator
02:56 : tool like like nearly Jas in the past I
03:01 : have created some material some online
03:06 : material teaching people how to use a
03:09 : parser generator called nearly GS to
03:13 : help you build a parser in a very quick
03:15 : way but is also worth if you're serious
03:19 : about compilers learning how to make
03:23 : compilers you should also learn how to
03:26 : do it the hard way
03:28 : as well and the hard way is writing a
03:33 : parser by hand using the recursive
03:36 : descent technique which is what we're
03:40 : gonna do here first let's start with the
03:43 : abstract syntax tree okay we're gonna
03:45 : make a class hierarchy or a bunch of
03:49 : classes representing the different ast
03:53 : nodes in this programming language it's
03:56 : is phenotype they'll be represented by a
04:03 : specific class with a with a first named
04:08 : name that represents that type of syntax
04:13 : element in the language
04:16 : if we go back one chapter this is go
04:21 : back so in chapter 1 we saw a very small
04:27 : example of a program in this program
04:30 : language it's called kaleidoscope so the
04:34 : program code in this programming
04:36 : language looks like this it's got a deaf
04:38 : keyword
04:39 : it's got identifiers like any normal
04:43 : proven language it's got identifiers
04:46 : it's got operators like less than
04:48 : science - science + science etc it's got
04:52 : comments each of these types of things
04:55 : is like a syntax element in the language
04:58 : and they need some representation in the
05:03 : ast like the DEF keyword needs an ast
05:08 : type that represents the death keyword
05:11 : and a identifier or variable or a
05:16 : function definition such as this one or
05:19 : variable reference or if statement all
05:23 : of these things need a syntax element
05:25 : that represents that thing or a class
05:30 : that represents that syntax element and
05:33 : that's what we're gonna be making so
05:36 : we're gonna make one one base class
05:39 : called the expert ast and then all the
05:43 : other classes are gonna extend from that
05:46 : to be their specialized type of ast node
05:51 : okay okay we're continuing I'm just
05:58 : gonna keep working in this file I'm
06:00 : gonna comment out this mean function
06:02 : which I wrote just to test out the
06:04 : lecture the tutorial didn't instruct me
06:07 : to do that I just decided to do that
06:23 : okay so this is the base class from
06:27 : which all of these specific ast node
06:30 : types will extend oh by the way you have
06:34 : to put a semicolon after each class
06:36 : definition what is defined here well we
06:41 : defined this destructor which is virtual
06:47 : that actually kind of confounds me a
06:50 : little bit why we define this as virtual
06:55 : but um I have a feeling is because if we
07:00 : didn't define this then C++ would want
07:04 : us to define it so this is just going to
07:07 : preemptively define it and the fact that
07:11 : it's virtual means a subclass may choose
07:14 : to overwrite its implementation I think
07:17 : that's what it means
07:19 : yeah I'm not much I'm not exactly a C++
07:23 : expert but that's my guess as to why we
07:28 : need this okay now that we have the base
07:32 : class we're gonna make a number expert
07:35 : ast to represent any numbers in the
07:38 : program this colon means extension so
07:46 : number expert ast extends expert ast why
07:52 : do we need to write public here turns
07:55 : out that in C++ there's a concept of
07:59 : [Music]
08:00 : sort of making it public the fact that
08:04 : you inherit from another class versus
08:08 : keeping it private I haven't seen that
08:12 : concept and other languages so I believe
08:15 : this is unique to C++ if you if you do
08:21 : not make it public that you extend
08:24 : another class I believe then the
08:26 : consequence is a you can you're not
08:29 : allowed to cast a object of this class
08:32 : to a variable that has the
08:36 : type of your parent class you are only
08:39 : allowed to make that cast if you made a
08:42 : public that you extend that parent class
08:46 : I hope I'm right about that and instead
08:52 : of giving out false information again
08:54 : take what I say with a grain of salt
08:57 : because I'm not a C++ expert although I
09:02 : am trying to be okay what is this guy
09:11 : well this is the constructor a
09:13 : constructor has the same name as the
09:15 : class and it looks like a method and
09:19 : what is this thing after the colon that
09:22 : is called the initializer list all this
09:25 : does is really assign this value to this
09:28 : variable inside the class so if you're a
09:33 : Java programmer or even a JavaScript
09:35 : programmer you're probably more used to
09:38 : doing this like like you do like this
09:43 : like that
09:44 : well this initializer list thing just
09:50 : this the same thing with a different
09:52 : syntax and you can do it either style
09:56 : and also slightly confusing that it's ow
10:02 : ow ow so they are referring to two
10:10 : different things
10:11 : this one is referring to this one
10:13 : whereas this one is referring to this
10:15 : one so you could actually call them
10:18 : different things so I'm gonna call this
10:20 : one let's say I call this one V right
10:24 : it's a capital V
10:26 : and this does exactly exactly the same
10:30 : thing right yeah so I'll leave this one
10:35 : like that it does the exact same thing
10:38 : okay so I'm gonna I'm gonna define the
10:42 : other ones the other ones are gonna be
10:44 : pretty much the same style just with
10:47 : different
10:48 : for their variables I'm gonna copy this
10:51 : one too to be a little more expedient
10:54 : here now one thing I wanna say is when
10:59 : you're dealing with a string
11:02 : I actually don't tote 100% understand
11:04 : why we need to define the input
11:07 : parameter of this constructor to be a
11:10 : cons string with an and though and I
11:14 : know what the an means usually the N
11:16 : means the address of so if you have a
11:23 : variable in C++ and that variable is
11:26 : like a string well the string is stored
11:29 : in memory somewhere and that memory has
11:34 : an address location which is usually a
11:37 : hex number like that like so if you put
11:41 : an N in front of that string variable
11:44 : that gives you the address location
11:47 : where your thing is stored as a number I
11:49 : don't actually understand why this is
11:52 : used in the context of the parameter
11:55 : list I have to read more about it or if
11:58 : somebody knows if you are watching this
12:01 : and you know the answer please enlighten
12:04 : me we have a binary expert ast I'm going
12:11 : to type this out because it also extends
12:22 : the base class expert ast and it has a
12:27 : char it has operator which is this chart
12:32 : so the operator is like a plus plus and
12:44 : then we have a unique pointer was
12:54 : completely cool as to what it was
12:55 : earlier today until I researched a
12:58 : little bit but let me type this out
13:00 : first and then
13:01 : explain again we're going to use this
13:08 : pattern of just passing in these
13:10 : parameters into the constructor and then
13:13 : just using the initializer list to
13:16 : initialize these three variables and
13:21 : each one of them is actually a unique
13:24 : pointer to a exper ast and then we'll do
13:36 : this initializer listing
13:46 : okay I think that's it for the binary
13:54 : expert AST
14:09 : yep I have an extra car was that the
14:15 : problem that extra come up is a
14:21 : non-static data member what's the
14:26 : problem I need a semicolon
14:29 : oh it needs to be capital o okay that
14:47 : was it for up but what about left-hand
14:50 : side and right-hand side
14:54 : this it's a deleted function cannot be
15:02 : referenced
15:10 : oh I need to do this standard move thing
15:14 : okay I see well I don't know if I can
15:19 : explain this one honestly does that work
15:26 : that works okay good
15:27 : I didn't even copy this code correctly
15:30 : because I wasn't going by okay what is
15:35 : this unique pointer thing a unique
15:38 : pointer in C++ is what they call a smart
15:42 : pointer okay a smart pointer and it's I
15:51 : guess it's a relatively new innovation
15:53 : in C++ I guess if you you know really
15:59 : understand why a smart pointer is needed
16:03 : you need have to understand more about
16:06 : well what did people do before there
16:09 : were smart pointers well they just had
16:12 : pointers is it they didn't have smart
16:16 : pointers at one point and they just had
16:18 : pointers what the heck are pointers so
16:22 : whenever you have whenever you have
16:27 : array of stuff like a type that has a
16:32 : combination of stuff in it array or an
16:35 : object or a dictionary or any of these
16:37 : things when you have a variable that is
16:42 : the array like it I have an array it's
16:45 : actually a pointer to some location in
16:49 : memory that contains the actual data
16:53 : okay this C plus first that's not
16:57 : totally true sometimes the data is right
17:00 : there on the stack for you but in many
17:03 : cases you're dealing with a pointer and
17:08 : the pointer is sort of represented as an
17:13 : address location right if you know where
17:15 : this stuff is stored in your memory you
17:21 : know the address
17:22 : of this stuff you can go there and get
17:25 : it there for a pointer is in reality a
17:27 : address location now somebody has to be
17:32 : responsible for cleaning up this memory
17:37 : location as in if you're gonna claim a
17:40 : section of memory well that's that's
17:43 : like that's kind of a big deal because
17:48 : if you weren't using that memory
17:51 : somebody else could be using it so
17:53 : there's this concept of ownership of a
17:56 : memory so if if you're gonna use your
18:01 : memory and you're done with it you you
18:04 : better free it up so that other people
18:07 : or other parts of the code can use that
18:10 : memory and in some languages starting
18:16 : with Java and JavaScript also and Python
18:19 : or Ruby or most of languages have this
18:22 : thing call it the garbage collector so
18:25 : that you don't have to so that the
18:28 : developer doesn't actually have to
18:29 : explicitly say free up this memory I'm
18:32 : not using it anymore so other other
18:34 : parts of the code can use it but C++
18:37 : doesn't have a garbage collector and C
18:41 : and C++ and Objective C as well they do
18:45 : not have a garbage collector and
18:47 : programmer is actually responsible for
18:50 : freeing up the memory that they use when
18:52 : they're done with it which means and in
18:56 : the past the way c++ dealt with that is
18:59 : to say well when you're making a class
19:02 : and this class is not needed anymore or
19:06 : an object of this class is not needed
19:08 : anymore it goes out of scope say you
19:12 : have a variable let me make an example
19:15 : actually like let's say you have a
19:17 : function
19:20 : and then you make a variable of some
19:26 : sort of class I'll call this pen expert
19:32 : like that and and it's initialized with
19:36 : some value blah blah blah you do some
19:39 : stuff with it but but because this
19:42 : variable is declared within the body of
19:44 : this function when this function is done
19:48 : we actually don't need this variable
19:50 : anymore and therefore the any memory
19:55 : that is variable users can be freed up
19:58 : implicitly when when you make a class
20:01 : though you might do something in the
20:04 : constructor or in its method that claims
20:07 : additional memory and if you do that
20:10 : then it's your responsibility to clean
20:12 : it up in the destructor what's the
20:15 : destructor well it's written like this
20:17 : it's it also has the name of the class
20:20 : but it has the tilde in front of it so
20:23 : if you allocate for some memory here
20:25 : let's say you do like some other thing I
20:30 : need equals new that other thing this
20:39 : new statement allocates memory for that
20:41 : other thing and because this is a C++
20:47 : and you want to be responsible you're
20:50 : gonna need to say delete that some other
20:53 : thing that I need within the destructor
20:57 : to properly clean up after yourself
21:00 : smart pointers coming back to this smart
21:04 : pointer is an innovation that relieves
21:07 : you of that responsibility if you have a
21:09 : smart pointer then you don't need to
21:12 : explicitly delete the thing that you own
21:17 : so yeah and we'll talk more about it as
21:24 : we go but that's there's more or less
21:27 : what this unique pointer is so if you
21:31 : have a unique pointer to the
21:33 : expert ast then because this class
21:38 : almost this unique pointer we didn't
21:41 : actually have to write a destructor the
21:44 : thing that where you do all the cleanup
21:46 : stuff this cleaning up of this the
21:50 : object that's pointed to by the pointer
21:53 : is it's done automatically when an
21:56 : object of this class is not needed
21:59 : anymore okay all righty I'm just gonna
22:03 : copy this one for expedience reasons and
22:09 : vector this one uses a vector it has a
22:12 : string this course where ast is like a
22:15 : call expression which is something like
22:18 : you know tip 5 represents like something
22:23 : like whereas the binary expression
22:25 : represents like something like 2 plus 2
22:28 : right fit 5 has a collie that's the name
22:32 : of the function and an argument less
22:35 : that's what's a vector a vector is a
22:42 : dynamic array so there would correspond
22:44 : to an array in JavaScript for example so
22:48 : this guy is gonna be a vector of unique
22:50 : pointers to ast notes is expert ast
22:55 : notes ok and this stuff yeah is the same
22:59 : deal this standard move is basically
23:03 : saying wherever this unique pointer came
23:08 : from we're gonna move it to be owned by
23:11 : this object so so there's this concept
23:15 : of ownership that's very key to how
23:17 : smart pointers work and this move
23:22 : operation is sort of transferring the
23:25 : ownership from one part of the code to
23:28 : another part of the code and in this
23:30 : particular case is transferring their
23:31 : ownership from outside of this class to
23:34 : inside of this class and we have a
23:40 : couple more AST notes I'm just gonna
23:42 : copy this
23:47 : this is a function definition ast node
23:51 : so it I think in this programming
23:53 : language it looks like death you know
23:57 : say fib there's a function definition
24:01 : and this proto as T is the function
24:06 : signature part of the definition whereas
24:10 : the function ast contains the proto
24:13 : contains its own function signature plus
24:17 : the body and what is in the proto the
24:21 : proto is has the name of the function
24:23 : plus the argument list that would be in
24:26 : here so there will be an N here and n is
24:28 : in the argument list so yeah so these
24:31 : two ast nodes represent a function
24:36 : definition okay the next part is going
24:46 : to be actually building the parser we
24:48 : have set the groundwork for building the
24:52 : parser we've defined the ast nodes
24:55 : actually there's this red squiggly here
24:58 : it says it's an incomplete type oh
25:01 : because I need to import vector if I'm
25:04 : going to use it or include yeah that
25:21 : solves it I had to do is include vector
25:25 : ok so we have all the ast nodes that we
25:28 : need at least thus far in this program
25:31 : the next step is gonna be writing the
25:33 : recursive descent parser I'm gonna save
25:36 : that this for the next video so if
25:40 : you're interested in follow along I'll
25:42 : see you on the other side