Make Your Own Language 1: The Lexer

This is the first episode of a series where you build your first programming language, using these videos as a guide. We’ve setup the syntax for a small programming language. You can clone this project and start getting to work. The project repository is https://github.com/airportyh/smallang.

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : hello there this is Toby and this is the
00:02 : beginning of a series where we code a
00:06 : programming language from scratch the
00:09 : programming language is called Smalling
00:11 : a little bit of preface so previously I
00:14 : have created a set of videos called how
00:18 : to make a programming language there is
00:19 : currently 19 videos in this video series
00:23 : which you can find on my website Toby ho
00:26 : comm all of the videos are completely
00:29 : free available on YouTube the one thing
00:32 : that I have found that is missing is a
00:36 : walkthrough of a complete programming
00:39 : language built from end to end which is
00:42 : what this series is meant to address so
00:45 : what I want to do is sort of set up a
00:49 : specification for a very small
00:51 : programming language that you can build
00:53 : on your own with guidance from this set
00:57 : of videos I have a code example here of
01:00 : what this programming language is going
01:02 : to look like syntax wise it's quite
01:05 : similar to JavaScript it has this arrow
01:08 : function syntax which I'm gonna call
01:11 : lambda functions in the tradition of
01:13 : Lisp this programming language is very
01:15 : small because it follows the tradition
01:19 : of Lisp in leveraging the expressive
01:22 : power of lambda functions I broke it
01:25 : down into these series of steps that
01:28 : will be following starting from the
01:31 : parser the lexer making AST files
01:36 : building the parser for these various
01:39 : syntaxes and then building the generator
01:42 : for the various sin taxes we won't
01:44 : necessarily go in this order we might
01:47 : jump around a little bit from episode to
01:51 : episode but this is basically more or
01:54 : less the set of steps that we will be
01:57 : following if you have been following
02:00 : this series then I think you should have
02:03 : a familiarity with the architecture of a
02:07 : programming language if you do not
02:09 : please go ahead and
02:11 : take a watch of the at least the first
02:13 : video in this series to get some
02:16 : background on that if you want to follow
02:18 : this project if you want to build this
02:20 : programming language this is the URL for
02:22 : the project so with that let's get into
02:26 : it let's get into the code so the first
02:28 : thing we're gonna do is set up the
02:30 : project set up the NPM project as we
02:32 : will be using javascript to build this
02:34 : thing let's get started with NPM in it
02:37 : whether - why come in that gets us a
02:42 : package.json file and then immediately
02:45 : after that we're gonna install mujhey as
02:48 : as well as nearly Jas I'll say npm
02:51 : install mu and nearly as well - - safe
02:56 : and then we have both of the
02:58 : dependencies installed now the first
03:02 : thing i want to do is set up a lexer
03:05 : using mu J yes what is a lexer well in a
03:09 : previous episode I have covered what
03:12 : lectures are in this mu J s tokenizer
03:14 : with nearly j s so if you want more
03:18 : detail about lectures after this episode
03:21 : then that's where you go but I will give
03:23 : you a high-level explanation here Lee
03:27 : let's say I'm gonna print the result of
03:30 : one plus one if this guy was in the
03:33 : string the job of the lecture is to
03:35 : divide these characters up and group
03:38 : them into little chunks that that makes
03:42 : sense so typically the word Trent would
03:46 : be grouped into one trunk so you would
03:48 : get a token that is print and typically
03:51 : the parentheses get their own chunk so
03:55 : you get another token there's the left
03:58 : brand and then add would be in its own
04:00 : chunk typically words like print and ad
04:04 : I recognize as identifiers or called
04:08 : identifiers and then numbers typically
04:10 : are their individual chunks like so
04:14 : let's say this was 1 2 3 then 1 2 3 goes
04:17 : in its own chunk and then we have to
04:20 : write brands here those go in
04:22 : their own child as well so these guys
04:25 : here would be the tokens and that's the
04:30 : job of our lexer is divided up the
04:33 : string input into this these separate
04:35 : tokens and usually tokens have types
04:40 : that tells you what kind of thing it is
04:43 : so typically a word like print or ad
04:46 : they will be off type identifier and
04:50 : symbols like left print and ripe ran
04:53 : they get their own type so this would be
04:56 : like Elle bran for short this would be
05:00 : type are bran and so forth and once this
05:04 : job has been done by the lecture we got
05:07 : these little chunks of input we feed
05:09 : these guys these tokens into the parser
05:12 : and then the parser has an easier time
05:14 : parsing this input because these little
05:17 : chunks have been already sort of typed
05:20 : and the parser can use that information
05:23 : oh and these numbers by the way they
05:25 : would have the type of num so that's
05:29 : what the lexer does and muj is is a tool
05:32 : that actually makes this quite easy and
05:35 : we'll see that so we're the installed
05:37 : new GS and we're actually just gonna
05:39 : copy their hello world example and sort
05:42 : of still steal that as at least the
05:45 : beginnings of our lexer so I make a file
05:48 : called lecture dot - yes and the way you
05:51 : use this mu J's lecture is you feed it
05:55 : some input and the way you feed it input
05:58 : is by using this reset method which is a
06:02 : peculiar name for saying read input but
06:06 : that's okay
06:08 : so now this example lecture is going to
06:11 : handle whitespace for us which is either
06:15 : a space or a tab token it's cause
06:19 : they're gonna handle comments for us
06:21 : which is two slashes followed by
06:24 : anything and then I guess this is the
06:27 : end of the string we have numbers which
06:30 : i think is only integers I don't see any
06:33 : decimal points here being
06:35 : matched by the regular expression and
06:37 : there's string tokens left ran and ripe
06:40 : ran some keywords and newline our
06:45 : language actually doesn't have keywords
06:47 : so I'm gonna delete this but our
06:50 : language does have these other things
06:52 : actually it has more things than that
06:55 : but let's just test out this lexer so
06:58 : let's say this lecture should handle
07:01 : something like there's a number I mean
07:03 : is a uptick string so we can have real
07:06 : strings in there 1 2 3
07:09 : ABC it can it can handle parenthesis and
07:13 : so on so if you feed the lexer this
07:16 : input it should group these chunks
07:19 : together this should be a number chunk
07:22 : this should be a alprin this should be
07:25 : ripe and etc so once you call you reset
07:28 : to feed it a string then you call next
07:31 : and each time you call next you actually
07:33 : get a token object back which is gonna
07:36 : have a type of some value and a value of
07:41 : some value I'm gonna say while true
07:45 : token it's gonna be lecture dot next and
07:50 : then I'll print out that token I guess
07:55 : if there is no more token then we'll
07:59 : break out of this loop otherwise then
08:03 : we'll print out the token so let's run
08:04 : this file and it runs and it's able to
08:11 : parse well I shouldn't say parse because
08:14 : the parser is the next step
08:15 : Bolex it elects this input and group it
08:19 : into as you can see the first token is
08:23 : the number 1 2 3 followed by a WS which
08:28 : stands for whitespace followed by a help
08:32 : Ram a left parenthesis followed by a
08:35 : string ABC followed by a R prime which
08:39 : is our right parenthesis so this lecture
08:42 : works what we want to do
08:45 : to add the other tokens that we're gonna
08:49 : need for our language so let's just took
08:51 : a take a look at what tokens were going
08:54 : to need for our small programming
08:58 : language we're going to need something
09:03 : to match these words these identifiers
09:07 : identifiers can either be function names
09:10 : in a function call or variable names in
09:13 : a variable assignment or a variable
09:15 : reference so I'm gonna add that it I'm
09:19 : gonna add something called the
09:20 : identifier and I'll write a regular
09:23 : expression to match it typically an
09:26 : identifier the first character of
09:28 : identifier is a alphabet letter
09:33 : lowercase a to Z or uppercase a to Z
09:37 : followed by the same but also allow for
09:42 : the possibility of underscore or a digit
09:45 : as the second character up to the last
09:49 : character and how use eight star sign to
09:52 : to mean zero or more of these guys to
09:57 : give you some example an identifier
09:59 : would be like a pole would be an
10:04 : identifier it starts with an alphabet
10:06 : letter followed by four more alphabet
10:09 : letters all of them fit into this but we
10:12 : also have numbers any one of these guys
10:14 : could be numbers so that is also a valid
10:17 : identifier okay so that's what it
10:19 : identifier is what mu J s will do with
10:22 : this information is if it matches this
10:25 : regular expression during its lexing
10:28 : process it'll take the string that match
10:32 : this regular expression you end up
10:33 : getting a token that has the type of
10:37 : identifier and the value that matches
10:39 : that actually let's just go ahead and
10:41 : make it do that so I'll put an apple as
10:43 : well as apple with this funky numeric
10:48 : notation and have our electoral exit let
10:52 : me get rid of the others
10:54 : yeah I have identify which is Apple a
10:58 : white space and that identifier which is
11:00 : a nine nine one three so our identifier
11:04 : works we already have the left paren and
11:06 : the right Tran we have identifiers we
11:09 : have string literals we do need we do
11:14 : need this equal sign for the assignment
11:17 : operator as well as this equal greater
11:20 : than for the fat arrow I'll call the
11:23 : equal sign a sign and I'll have a fat
11:27 : arrow the ordering matters here because
11:31 : if it had matched the single equal sign
11:33 : the lexer actually has no way of
11:35 : matching this greater than sign and
11:38 : it'll get confused I'll actually show
11:39 : you that so if we gave it a fat arrow
11:42 : like this yeah when it saw this greater
11:47 : than sign it got confused because it saw
11:49 : this equal sign and assign it to an
11:52 : assign token so this doesn't work and
11:55 : it's left over with a greater than sign
11:57 : which it has doesn't have another rule
11:59 : that can match just a greater than sign
12:01 : so if you want we want this to work I've
12:04 : got to put the fat arrow b40 a sign and
12:09 : that's retort out for us we get a fat
12:11 : arrow and we let's say we have a sign
12:16 : token here has the next thing and then
12:18 : now it's able to match the assign total
12:20 : alternatively what we could also do is
12:23 : instead of having a fat arrow just have
12:27 : a greater than token like that and then
12:31 : leave it up to the parser in the next
12:33 : step to piece together this assign token
12:36 : and the greater than token I think for
12:39 : our purposes I think this is a simpler
12:42 : solution to have a fat arrow first and
12:44 : then the assign tokens second so we do
12:47 : have the comment which there example
12:49 : already supplies nothing to be done we
12:52 : totally stole all of code from muji yes
12:56 : actually think that's all the token
12:58 : types that this language needs so what
13:01 : I'm gonna do is actually write a simple
13:03 : function to
13:05 : test this I'm gonna read in this file
13:07 : and feed out of it into this lecture and
13:11 : see if it is able to lacks all of it
13:14 : correct maker main function using the
13:18 : async/await syntax I'll bring this code
13:22 : into that function
13:30 : I'm gonna use the FS module okay I'll
13:33 : put in the semicolon I'm actually gonna
13:36 : go ahead and install the MZ model which
13:39 : is a module that I like for dealing with
13:43 : the file system that gives me a promise
13:46 : if I'd library for the file system
13:49 : because say code is equal to wait FS
13:54 : read file example that's more which is
13:59 : program I have on the right hand side
14:01 : after reading in this file we'll get a
14:05 : buffer object which will turn into a
14:07 : JavaScript string and there is the code
14:09 : I'll take this code and feed it into our
14:12 : lexer with lecture that reset let me get
14:17 : rid of this lecture that reset so now I
14:21 : believe we have FET the lexer all of the
14:24 : code and we're gonna call lecture that
14:27 : next and how each token if all of that
14:30 : works without a failure then we can
14:33 : conclude that our lessor is able to
14:35 : handle of the input in this program no
14:41 : oh we forget about the braces these
14:45 : curly braces so let's add token types
14:48 : for the curly braces where the braces
14:50 : are similar through parentheses so I put
14:52 : them next to them I'll call this left
14:54 : brace I'll brace and our brace
15:00 : and yeah it was able to Lex all of this
15:02 : file and match all the characters to one
15:07 : of the predefined tokens and each token
15:10 : as you can see is an object that has a
15:12 : type as defined by this lecture here mu
15:16 : J s based lecture has a value and a text
15:20 : field currently all of the values are
15:22 : the same as the text field there is an
15:24 : option of converting the value to be it
15:27 : something different if you like that
15:30 : that's a configuration you can make to
15:33 : the lexer which we're currently not
15:35 : using there are line numbers line and
15:38 : column numbers for each token which will
15:42 : actually be very helpful in error
15:44 : reporting which is one of the future
15:48 : topics I plan to cover in this channel
15:51 : so there we have it we have a working
15:53 : lecture in the next episode we will
15:55 : continue on and start building the
15:58 : parser