LLVM Tutorial #2: Lexer

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/. Let's see how it goes. In this episode we implement an simple lexer.

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : I think we're live
00:07 : hey this is Toby this is I walked
00:11 : through of the LLVM tutorial so I did
00:17 : some intro in the last video this video
00:20 : we're gonna dive straight into it
00:21 : into the first chapter there's gonna be
00:25 : some in software that you need to
00:29 : install if you if you don't I'm on a Mac
00:35 : but I think this is this can be done on
00:38 : Linux and Windows as well but in any
00:42 : case you're gonna need AC compiler to
00:44 : start this now LLVM project itself
00:47 : provides AC compiler and it's possible
00:50 : to use that however if you're on a Mac
00:55 : it's pretty convenient and recommended
00:59 : to install either the command-line tools
01:02 : which you can find instructions on how
01:05 : to do that here or you can install Xcode
01:08 : which is their development environment
01:10 : which is much larger install but if you
01:14 : are interested in developing for the
01:17 : Apple platform this is recommended I
01:20 : have just the command-line tools
01:22 : installed myself I don't care to install
01:25 : Xcode it's a very very large package and
01:29 : I personally don't use it and to check
01:34 : whether you have what you need
01:37 : you can type GCC and see if that exists
01:41 : if it says clang or something it doesn't
01:45 : have to be clang but if this error no
01:47 : input files that means you have GCC the
01:50 : program were used gonna use to compile
01:52 : our C++ code is actually called G + + so
01:57 : you can check for G + + as well yeah
02:01 : with that let's get started so did I
02:06 : make a new directory no I did not
02:08 : I'm gonna make a new directory called
02:12 : olv em first length you can call it
02:18 : whatever you want and then I'm gonna use
02:21 : code insider as my text editor and it
02:24 : doesn't matter too much which one you
02:26 : use one thing about this tutorial is is
02:38 : hey is a guided tutorial all of the code
02:42 : that you need to write is supplied to
02:47 : you however it does expect some level of
02:51 : proficiency with C++ but but if you are
02:59 : following along with me hopefully you
03:01 : can get by with just very little
03:03 : knowledge there as I go I will explain
03:08 : the C++ constructs just in case you are
03:12 : not that knowledgeable about C++ but
03:15 : just aren't interested in what we're
03:18 : doing here okay so the first thing we're
03:21 : gonna do is to create a lecture I'm
03:25 : gonna make a file and I'm gonna just
03:29 : call this I'll just call it my Lang and
03:34 : I'll suffix this file with dot C see
03:38 : some people like to use dot CPP for C++
03:42 : programs some people like to call it
03:45 : that CC I'm gonna use that CC because
03:48 : it's shorter and I'll just type in what
03:53 : the tutorial has me typing what's a
03:57 : lecture
03:58 : first of all a lecture is a is a
04:01 : preprocessor in a parser that will
04:04 : separate a string of inputs into into
04:08 : chunks so for example this program here
04:13 : this is going to be the program and it's
04:16 : got a lot of different types of things
04:18 : it's a comments it's got
04:21 : deaf keyword it's got an if keyword and
04:24 : this got this function name etc what a
04:28 : tokenizer is responsible for is to sort
04:33 : of pick out the important chunks like oh
04:37 : that's a deaf keyword that's a chunk and
04:39 : then that's a function name that's a
04:42 : chunk and then this open friend is a
04:46 : chunk by itself and then this X is
04:49 : another identifier that's a chunk so
04:53 : it's it's gonna sort of split the string
04:57 : up into these chunks and give each chunk
05:00 : a type like for example it'll give this
05:02 : type a it's the type of the DEF keyword
05:06 : and this the fit is the type of
05:08 : identifier and so forth okay so the
05:12 : first thing that we're doing in this
05:13 : tutorial is defining the different types
05:16 : of chunks which are called tokens there
05:22 : are some types of tokens that we can
05:24 : have in this programming language and
05:26 : here they are
05:29 : we have enough file tokens we have the
05:33 : DEF keyword that's that's this guy we
05:36 : have a extern keyword which i think it's
05:39 : like this keyword extern here
05:42 : identifiers identifiers are like either
05:44 : function names or variable names also
05:47 : have numbers apparently in this
05:50 : programming language called kaleidoscope
05:52 : the only values are floating point
05:56 : 64-bit floating-point numbers there
05:58 : aren't strings in this language which
06:01 : makes it kind of limited but you know
06:03 : this is a tutorial right okay so we're
06:07 : gonna make an enum which is gonna list
06:10 : out all the different types of tokens we
06:13 : have in this language I'm just gonna
06:16 : copy this
06:40 : and we need a semicolon here okay so
06:43 : this in um in reality it's really just
06:47 : represented using an integer and this
06:50 : feature here where we explicitly set the
06:54 : integer number for each you num mode
06:59 : it's a feature of C++ the reason the
07:03 : author is doing this is because it wants
07:05 : to use this enum type to double as the
07:11 : characters in the event that it that the
07:15 : token doesn't fit any of these
07:17 : prescribed types which if you ask me
07:21 : that's a really weird way to do it but
07:24 : you know let's just follow along I'm
07:29 : gonna define two global variables
07:32 : actually which is the first unsavory
07:35 : practice instance of unsavory practice
07:40 : that we've seen but yeah but basically
07:43 : whenever the parser or the lexer
07:46 : discovers an identifier string it's
07:49 : gonna save it into this string variable
07:52 : and whenever it identifies a number it's
07:56 : gonna save it in this num Val variable
08:00 : it's just not questioning it not
08:03 : question it too much let's just follow
08:05 : along
08:12 : okay in order to use the string type
08:16 : you'll need to include the knot the
08:23 : string library from C++ the author that
08:30 : the author of this tutorial didn't think
08:32 : to mention it I think because they
08:35 : probably thought that was obvious to any
08:37 : C++ developer which I yeah I agree that
08:44 : there should be obvious if you know C++
08:46 : okay now we're gonna read this function
08:49 : caught short forget token obviously I
08:53 : think it's intended to be a function
08:57 : where if you call it and it would parse
09:00 : the stream of strings or each parse the
09:04 : characters in the string until it drops
09:07 : enough characters to to recognize a
09:11 : single token and then it'll return that
09:14 : token and a token can be represented
09:16 : using an int because in can represent
09:22 : either one of the enums that are listed
09:26 : here or it can represent just a
09:30 : character a single character which they
09:34 : say unknown character in reality is not
09:36 : necessarily meant to represent unknown
09:39 : character it's meant to represent an own
09:41 : characters as well but anyway I'll talk
09:46 : through how this thing works
09:48 : as we go
09:58 : I don't like the fact that he doesn't
10:05 : use block he doesn't use these curly
10:10 : brackets to denote a block so I'm gonna
10:13 : put those in myself that's kind of a pet
10:19 : peeve of mine okay so what does this
10:24 : code doing well there's a last char
10:27 : I don't know why we initialize it to a
10:30 : empty space but it is saying while the
10:35 : last chart is a empty space we're gonna
10:38 : read a character from the input the get
10:42 : char is a function in standard c library
10:45 : i think there's gonna read one character
10:49 : from the standard input which is
10:53 : actually when the user is typing in some
10:57 : text and hits enter the text goes into
11:01 : the standard input so you're it's
11:03 : actually reading what you're typing in
11:05 : but it gets our reads just one character
11:09 : okay
11:09 : so it's gonna read one character that
11:12 : you typed in but it could also be coming
11:15 : from the file if you took a file and
11:17 : type it into this to the standard input
11:21 : of this program so it's basically rich
11:25 : one character and then stores it and
11:29 : then loops it's basically the if the
11:32 : character that was just read is a space
11:34 : it's gonna read another character it's
11:37 : gonna keep reading characters until it
11:39 : gets a character that's not a space so
11:41 : in essence it skips spaces yeah it skips
11:46 : all spaces that's what that does I think
11:50 : this paragraph explains as much let's
11:54 : keep going I think this code here
11:57 : recognizes a identifier and an
12:01 : identifier it uses the normal C
12:05 : programming language
12:06 : and also JavaScript uses this as well
12:08 : this is a standard identifier rule in in
12:18 : in programming languages is the first
12:20 : character of an identifier is is it a
12:25 : letter and then the rest of the
12:27 : characters are either letters or digits
12:31 : right so I can have name is a valid ID
12:36 : and if our name one name two are also
12:41 : available in the fires
12:43 : based on based on this rule and this is
12:46 : what we are trying to match with this
12:47 : code so let's type this in how did we
12:54 : get this thing this spotlight thing I
12:57 : did not mean to get that that was from
13:01 : my drawing program okay
13:04 : so if alpha means is it an alphabet
13:07 : character
13:17 : so this line here actually converts this
13:20 : character which is represented as an int
13:24 : in here but it converts it into a string
13:26 : because identifier string is a is
13:31 : declared as a string this line actually
13:37 : courses this integer into a string which
13:40 : is kind of unexpected but C++ does that
13:46 : I guess JavaScript does that to it
13:50 : Charles go happily cores an integer into
13:53 : a string
13:54 : although JavaScript will actually
13:56 : convert the number into the string
13:58 : representation of that number whereas
14:00 : this one actually interprets this
14:04 : character as as a character based on
14:08 : this number as an asset code okay no
14:16 : okay so it read the first letter which
14:19 : was this one of the identifiers and then
14:23 : while the next letter is elven numeric
14:29 : we're gonna keep reading characters from
14:33 : the input stream I'm going to put in my
14:36 : block even though the tutorial doesn't
14:40 : have that and then we're just gonna
14:43 : character to the end of this identifier
14:46 : string
14:48 : now if the identifier string is act
14:51 : happens to be one of the two keywords we
14:54 : have in this language and those are deaf
14:57 : and external then we're going to return
15:01 : that as a token of that corresponding
15:04 : type
15:15 : otherwise we're gonna return the
15:19 : identifier token type and and while make
15:28 : the identifier string available in this
15:31 : global variable here for four parts of
15:34 : the program that need to get that string
15:36 : okay so yeah so this is the part that
15:41 : parses the identifier or Lexus I should
15:47 : say so I'll say the first part skip
15:58 : spaces now we're going to try to match a
16:03 : number
16:21 : so if the input is a digit then well if
16:30 : it's a digit it won't have gone into
16:32 : this block so it will skip and go to
16:34 : this block so if it's a digit or it's a
16:37 : dot then we're gonna do this spit I'm
16:39 : gonna instantiate a num string its
16:43 : string to be collecting the digits and
16:46 : then at the end we're gonna use this
16:47 : stir to D to parse this string and
16:50 : convert it into an actual number there's
16:55 : a do loop here we're so gonna append the
17:00 : last chart into this num number string
17:03 : and then we're gonna grab another chart
17:08 : another character from the input we're
17:11 : gonna keep doing this until or while you
17:17 : should say we're gonna keep doing this
17:19 : while we're still getting digits or dots
17:28 : I'm sure there might be a problem with
17:31 : this code because what if you get a
17:34 : digit and it's not gonna work out but
17:41 : whatever this is a toy language it
17:44 : doesn't have to be perfect and then so
17:49 : this part parses a cup we're not done I
17:54 : mean to call this stir to D function
18:05 : and then return it as a number token
18:10 : okay okay next we're gonna have some
18:16 : code to process comments so again if we
18:21 : if we're starting out with a comment
18:24 : then it would have skipped this part
18:26 : because we the comment is started by the
18:29 : way the comment is started by this pound
18:32 : sign so common in this programming
18:34 : language looks like this so if if the
18:38 : current character in the stream is a
18:40 : pound sign then well it would have
18:43 : skipped this while loop because it's not
18:46 : a space and it would have skipped this
18:48 : if statement because it's not an alpha
18:50 : character and it would have skipped this
18:53 : if statement because it's not a digit so
18:56 : it'll keep going until it encounters
19:01 : this if statement and then here it's
19:08 : another do loop so if we see a pound
19:16 : sign we're actually gonna skip to the
19:18 : end of this line they're gonna ignore
19:20 : all the characters after the pound sign
19:22 : so so that's what this while loop does
19:26 : it's gonna keep reading chart until or
19:30 : while I should say while we're not we
19:34 : have not encountered the end of file and
19:37 : while we have not encountered a newline
19:42 : character and while we have not
19:48 : encountered a carriage return character
19:53 : any salt and jumping out of this world
19:57 : and also if the last character is not
20:06 : the enough file then we're gonna return
20:09 : get tok what it why are we recursively
20:13 : calling
20:14 : our selves basically if if this if this
20:19 : well look stopped in the file but for
20:22 : one of the last two reasons then we want
20:26 : to start looking for another token again
20:29 : because we're just gonna skip the
20:31 : comment and we don't care to return a
20:33 : comment as a token at all we're just
20:36 : skipping that so this function just get
20:39 : tok function recursively cost itself
20:43 : again here so that we will get and then
20:49 : finally we have this code that says if
20:53 : last chart is in the file then we're
20:57 : gonna return this and the file token the
21:00 : tok in a file and then finally finally
21:06 : if all of these cases fall through then
21:09 : we're just gonna return what's going on
21:20 : here we're gonna we're gonna save the
21:28 : last chart in to discharge so that we
21:30 : return it but we're gonna we're gonna
21:32 : get we're gonna get one more char why do
21:38 : we do that I'm actually a little
21:39 : confused about that so if we don't know
21:42 : anything then this char it's setting up
21:54 : the last chart for another and for the
21:58 : next call to the get tok function i
22:01 : believe is that true
22:09 : no I don't think that's true because
22:12 : last chart is a local variable
22:33 : where do we call get char again so let
22:36 : me see if I can figure this out so let's
22:39 : say it's a this is the plus character so
22:43 : it would have read last char Oh last
22:50 : chart initially it got set as the empty
22:54 : string oh it never read
23:13 : well it while is space oh but the first
23:19 : time it would be the space so the first
23:22 : time guitar is called the last chart
23:25 : would have been in the in the plus last
23:29 : her should be a plus given my string
23:32 : let's say my string was plus 1/2 we
23:36 : should have had a plus insight last
23:40 : chart here we're putting it into this
23:43 : chart and then we're getting a 1 into
23:47 : last chart why are we doing that that's
23:51 : actually quite surprising is that right
23:55 : there might be a problem with this code
24:00 : interesting okay well if there's a
24:02 : problem with the scope we'll need to
24:04 : debug it later and maybe there isn't I
24:08 : just don't know what I'm doing but uh so
24:12 : that's the actually the end of this
24:13 : chapter we have a lecture but we don't
24:16 : know if it's working actually and I feel
24:21 : compelled to test this lecture before we
24:24 : move on to the next chapter so let me do
24:26 : that so in C the entry point of your
24:30 : program is always the main function that
24:34 : that's just a convention I've you
24:37 : already main function it will be the
24:39 : entry point of your program after you
24:40 : compile it I'm going to call this get
24:45 : tok function basically until well
24:51 : probably just forever so I'm going to
24:56 : say while true
25:01 : get toke and we'll print out I think
25:07 : I'll use C++ to print stuff out and C++
25:16 : the way you print things out is by using
25:19 : the iostream and iostream has this thing
25:23 : called C out which normally you I don't
25:31 : know like this should be the more normal
25:34 : way but you can use C out like this
25:39 : because Co is part of the standard
25:41 : namespace so you can do standard : : C
25:46 : out to reference it but if you want to
25:48 : reference it just by the shorter name of
25:52 : C out what you could do is say using
25:55 : namespace standard and then everything
25:59 : that's in standard you can name them
26:02 : directly so that's what I'm gonna do and
26:04 : then here I'm gonna say token the taupe
26:12 : and then I'll do this to me and the line
26:15 : and let's run this and compile this
26:19 : program and run it and then I'll test it
26:21 : okay this is a C++ program I'm going to
26:27 : use g plus plus to compile this program
26:30 : you specify the output you specify the
26:35 : program that it generates with this - go
26:38 : flag I'm gonna call it my link bin this
26:44 : is a convention that I like to use and
26:46 : aiko the binary files a bin so it
26:52 : compiled it and now I have my link that
26:55 : bin which I can run and I think the idea
26:59 : is I type some stuff into it hit enter
27:02 : and then and then this program is gonna
27:06 : they get toke or it's already running
27:10 : get toke actually it's in the middle of
27:12 : this guitar waiting for me to type in
27:14 : characters
27:15 : come on type in say a three and then
27:19 : they got toke negative five what is
27:21 : negative five mean that's a number so
27:23 : that works that made sense if I type a
27:26 : multi digit number
27:28 : it still says that Tok negative five
27:33 : that's really cool what if it's an
27:36 : identifier like I don't know Jimmy then
27:42 : we get a token negative four negative
27:44 : four corresponds to an identifier so
27:47 : that seems correct what how do get a
27:51 : deaf if I type def then I get negative
27:54 : to make sense extra and I get negative
27:58 : three I don't know how to get it in the
28:00 : file in this kind of input user input
28:04 : scenario so I'm not going to try that
28:06 : but I think if I type in any other
28:07 : character then I just get the ASCII code
28:13 : of that character this is the ASCII code
28:17 : and I can verify that by going to the
28:20 : ASCII table calm so I talked a little
28:26 : bit about ASCII and when I was the video
28:29 : I did with a chi last week but ASCII is
28:33 : this table that gives a numeric
28:36 : character if there are on your keyboard
28:38 : more or less so if I type the character
28:43 : J for example look J that actually
28:48 : doesn't get recognized as an identifier
28:51 : but something does not matched like an
28:56 : equal sign then it actually gives you
28:58 : the ASCII code of the equal sign
29:01 : character which is 61 yeah that's what
29:04 : it printed so this lecture seems to work
29:07 : and I guess that's a good start to this
29:11 : tutorial
29:13 : yeah that does the end of chapter one of
29:16 : the LLVM tutorial
29:21 : I'll see you in the next one