Make Your Own Language 2: The Parser

This is the second 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. In this episode, we begin building the parser for the programming language, starting with variable assignment syntax.

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : hello there and welcome back to small
00:02 : lang uh the programming language that
00:04 : you build yourself i'm hoping that this
00:08 : would be
00:08 : the first programming language that you
00:10 : build with the guidance of these videos
00:12 : yeah so this is part two of the series
00:16 : in part one we built a lecture
00:20 : which is able to go through all of this
00:23 : program lex this file that's the proper
00:26 : verb
00:27 : for this and convert this input
00:31 : as a string into a series tokens what do
00:34 : the tokens look like well they look like
00:36 : this
00:36 : each token is an object with a type
00:39 : identifier and a value
00:41 : and the type identifiers sort of give
00:43 : you like a tag
00:45 : for what type of thing this is like a
00:48 : right parenthesis is an r prime
00:51 : a number is a number an identifier is a
00:55 : word like fib
00:56 : so you can see that oh this is an
00:58 : identifier
00:59 : this is an assigned token this is a left
01:02 : brand this is another identifier and so
01:05 : forth is grouped
01:06 : your strings into these small chunks of
01:09 : strings
01:10 : and these tokens are the things that
01:13 : we're going to be
01:14 : feeding into our parser which is what
01:17 : we're going to
01:17 : make in this session here um
01:21 : more specifically we're going to start
01:24 : building our parser to the point of
01:27 : being able to
01:28 : parse a statement a variable assignment
01:31 : statement
01:32 : like this so let's go ahead and get
01:34 : started um
01:36 : we're going to be using nearly js to do
01:38 : this this is nearly js
01:41 : in my series on how to make a
01:43 : programming language
01:44 : i actually have quite a bit of detail
01:48 : explaining how to use nearly js so if
01:50 : you
01:51 : are wanting more details about this
01:54 : then go check out those videos here
01:57 : we're going to make a grammar
01:58 : that is able to parse this so i'm going
02:01 : to call that grammar file
02:02 : small dot n e small is the name of our
02:06 : programming language and any
02:08 : is a shorthand for nearly okay and in
02:11 : this grammar file we're gonna
02:13 : write a set of rules and we're gonna
02:17 : define what a statement is
02:20 : and at the moment since the only thing
02:22 : we're trying to match
02:24 : is a variable assignment i'm going to
02:27 : say
02:28 : a statement can be a variable assignment
02:31 : a var assign now i'm going to define
02:34 : what var
02:34 : sign is a var sign is first
02:38 : one of these what is this this is an
02:40 : identifier
02:41 : if you have a name that's not been
02:44 : quoted that's an identifier
02:47 : and then we're gonna have some optional
02:50 : white space in nearly js they recommend
02:54 : you use this convention where optional
02:56 : white space
02:57 : is signified using a one underscore
03:01 : and a mandatory white space is signified
03:03 : using two underscores
03:04 : we have an assign operator which is that
03:07 : you
03:07 : can either identify the
03:11 : assign operator using this percent sign
03:15 : before the name the type of the token
03:19 : or if in the case where the string
03:23 : is going to be always the same string
03:25 : literal
03:26 : you can actually just name the string
03:29 : literal
03:29 : surrounded by double quotes which is
03:31 : what i prefer to do
03:33 : in the case that i can do it with
03:36 : identifier i can't do that
03:37 : actually i made a mistake before this
03:41 : identifier needs a percent sign before
03:43 : it
03:44 : oops to identify a token you can either
03:47 : identify by the type in which case you
03:50 : need a percent sign before it
03:52 : or identify it by a string literal which
03:55 : is possible
03:56 : if the string that's matched is always
03:59 : going to be the same
04:00 : string well okay there are some
04:03 : cases where you can use the string
04:05 : literal to match even something
04:08 : where the right hand side of this can
04:10 : change but uh we're not we're probably
04:12 : not going to do that
04:12 : in in our language variable assignment
04:15 : is
04:16 : going to start with an identifier
04:17 : optional white space
04:19 : an assigned token optional white space
04:22 : again and then some expression which
04:25 : could at the moment it could either be a
04:28 : string
04:28 : or a number so let me define something
04:31 : that's called an
04:32 : expression or expert and i'll say that
04:35 : an expert
04:36 : is either a string token or
04:39 : it can be a number token so vertical bar
04:42 : is
04:42 : how you notate the or in
04:45 : in nearly js so with this grammar i
04:48 : think we're actually able to
04:50 : build a parser probably let me try it
04:53 : nearly small.ne
04:57 : and we'll have it output a file that's
04:59 : called small.js
05:02 : oh i forgot to define this optional
05:05 : white space
05:05 : so let me go ahead and do that i'm going
05:08 : to say
05:09 : optional wave space is one white space
05:12 : token
05:13 : which was defined here actually zero or
05:17 : one
05:18 : zero or more of them if i use colon and
05:20 : then the star
05:21 : this star symbol works just like regular
05:24 : expressions
05:25 : this means zero or more of the
05:29 : thing before it so this is zero or more
05:32 : white spaces if i want to define a
05:35 : mandatory white space i would do this
05:38 : i'll say
05:39 : one or more the plus sign means one or
05:42 : more
05:43 : of the thing before it i'm gonna try to
05:46 : generate my parser again and it did it
05:49 : we have a
05:50 : small.js which looks like this
05:53 : usually you're not looking in this file
05:56 : although there are some cases
05:58 : you where you might want to actually
06:00 : debug the contents of this file but
06:02 : usually not
06:03 : we have a grammar that nearly is able to
06:06 : understand now
06:08 : but we'll still need to make tweaks to
06:10 : this guy now i want to actually copy
06:12 : this command out and put it in
06:14 : our package.json i'm going to delete
06:17 : this
06:17 : test because at the moment we don't have
06:19 : tests yet
06:20 : i'm going to make a script called gen
06:23 : parser
06:24 : and i'm going to paste this nearly c
06:26 : command that i use to
06:28 : compile this nearly file into a
06:30 : javascript file put it into this gen
06:32 : parser script
06:34 : so that later on i can say npm run
06:37 : gen parser and it'll do that for me
06:40 : uh rather than typing in this long old
06:42 : thing so anyway now we're gonna
06:44 : use the output of this guy
06:47 : this small.js we're going to use it to
06:50 : actually
06:50 : parse a file such as this one let's go
06:54 : to nearly js
06:55 : and go to their getting started guide
06:57 : this is how i always do it because i
06:59 : still don't have this
07:01 : memorized so i'm going to make a file
07:03 : called
07:05 : parse.js and paste this in
07:08 : this grammar is going to come from our
07:11 : small.js which we just
07:12 : generated nearly that stays the same
07:16 : and now we're getting a parser i'm gonna
07:19 : feed
07:20 : the code into it after feeding the code
07:22 : into it the parser
07:24 : if successful will have some result and
07:26 : we're gonna print that out
07:27 : at this point i actually want to write
07:30 : some code
07:31 : that will allow this to read in a
07:34 : file from the command line run it
07:36 : through this parser
07:38 : and then spit out another file
07:41 : which is a json formatted file that
07:44 : contains
07:45 : the result of the parse which will
07:48 : eventually become
07:49 : our ast aka the abstract syntax tree
07:54 : okay
07:55 : so again i'm going to use the mz library
07:58 : to allow us easy access to the file
08:01 : system
08:01 : and i will write code in this async
08:04 : await
08:05 : manner using async functions
08:09 : like so now we're going to read in the
08:12 : code
08:12 : let's grab the file name from
08:16 : process.org
08:17 : v index 2. why index 2
08:20 : well if you run this command
08:22 : nodeparse.js
08:24 : say ex1 small well
08:27 : note is gonna be index zero parse.js is
08:31 : gonna be index one and
08:32 : ex1.small is gonna be at index two
08:35 : that's why index two now we're gonna say
08:38 : well
08:39 : if you didn't give me a file name please
08:42 : provide a small
08:45 : file and we will
08:48 : return out of here but if they did
08:51 : provide one we're gonna read that file
08:53 : in
08:54 : here's the code await the result of
08:58 : fs.read file that file name
09:02 : and convert this buffer to a string
09:05 : there's our code we're feeding it into
09:07 : this parser
09:08 : let's print out the result for now
09:11 : okay there is a result it says
09:14 : identifier
09:16 : is not defined oh i forgot an important
09:21 : step i forgot to plug in
09:23 : my lecture into my parser let's go ahead
09:26 : over to our nearly js website part about
09:30 : tokenizers
09:31 : how to have nearly js interact with
09:34 : mu and the way you do it is you put
09:37 : this chunk of code at the beginning of
09:40 : your parser
09:42 : and then you plug in your lecture this
09:44 : way
09:45 : this lecture is going to reference this
09:47 : variable you can actually call this
09:48 : variable whatever you want
09:50 : and then you can call this guy whatever
09:51 : you want
09:54 : you could basically you could take this
09:57 : chunk of code
09:58 : and paste it
10:01 : in your parser here this block of code
10:05 : has to start with
10:07 : at open curly and then press send
10:10 : and then you close it with percent close
10:12 : curly
10:14 : i don't actually want to paste in the
10:16 : code for my lecture here i want it to
10:18 : stay
10:19 : in my lecture.js file so i'm going to
10:21 : change this lex4js to be
10:24 : more of a library instead of a script so
10:27 : this main function which i called i'm
10:29 : not going to call this main function
10:31 : anymore
10:32 : and instead i'm going to export this
10:34 : lecture out
10:36 : to a calling script by doing
10:41 : module.exports this is commonjs
10:44 : style of exporting an object from
10:47 : a file i'm going to export this
10:50 : lecture object as the default export
10:55 : using this syntax and then actually this
10:59 : parser file is able to require it
11:02 : so we have the lecture in a variable now
11:04 : now we're able to use this
11:06 : syntax this add lecture syntax to plug
11:09 : in this
11:10 : lecture so this lecture is referring to
11:12 : this flexor you could
11:14 : call this something else like mylexer
11:17 : and that should work now it previously
11:20 : this
11:20 : totally bombed because i forgot to plug
11:23 : in my lecture and now if i did it right
11:27 : it should work so but in order for it to
11:31 : work
11:31 : i have to recompile regenerate
11:35 : my parser
11:39 : now let's parse it and now we have an
11:41 : actual
11:42 : working result coming from the parts
11:45 : which is actually really great um
11:48 : but we can't sort of see all of the
11:50 : details within it
11:51 : let's do this let's let's uh print the
11:55 : output
11:56 : into a json formatted file
11:59 : suffix by dot ast i'll
12:02 : make a variable called output file name
12:06 : to get the output file name we'll just
12:09 : replace
12:11 : the that small with
12:14 : dot ast so given a dot small file
12:18 : will generate a dot ast file there's a
12:21 : possibility that the parser could give
12:23 : you multiple
12:24 : results which will make the grammar an
12:26 : ambiguous grammar
12:28 : and that's usually an undesirable thing
12:32 : we're only going to pick out the first
12:34 : result and then we're going to say
12:35 : if parser has more than one result
12:38 : that's actually a problem
12:41 : and i'm gonna for now i'm just gonna say
12:44 : uh error ambiguous
12:48 : grammar detected it's actually helpful
12:51 : to
12:52 : to have a record of all the results
12:55 : to to debug the problem when there's an
12:58 : ambiguous grammar
12:59 : but i'm gonna save that for later i'm
13:02 : just for now i'm just gonna say
13:03 : error ambiguous grammar detected and
13:06 : then
13:07 : but i'll say else if
13:11 : parser that results that length
13:14 : is one then this is perfect
13:18 : then we just have one result
13:21 : we'll call that guy the ast
13:25 : and we're going to save it into this
13:28 : file
13:29 : let me grab this line and put it in here
13:31 : and then say
13:32 : await fs dot write file
13:36 : output file name and then
13:40 : json.stringify so jsonstringify
13:43 : if you want it to format the string with
13:46 : some indentation this is what you do
13:48 : the second argument doesn't matter you
13:50 : just give it
13:51 : no there's there's actually a rhyme and
13:54 : reason for the second parameter
13:56 : but we're not using it in this case and
13:58 : then
13:59 : else if parser doesn't give any results
14:03 : which that actually means the parse has
14:06 : not completed
14:08 : maybe the parser is in the middle of
14:11 : finishing the parsing of a program but
14:13 : the program is not complete
14:16 : um so
14:19 : here i'll just say error no parse
14:22 : found and that's what i'll say oh and
14:25 : after writing the file i
14:27 : will want to print out wrote
14:30 : and then the name of the output file so
14:33 : i believe that is
14:34 : our parse.js let's try to run it
14:39 : so i did write ex1.ast
14:43 : and that's our output it contains
14:46 : each token that came from the lecture
14:48 : and it's sort of uh
14:49 : collected them and put them in various
14:52 : arrays and that's what we're seeing here
14:56 : now we would have some uh white space
14:59 : tokens here we have
15:00 : an identifier token and we have a sign
15:02 : token which makes sense because there
15:04 : was an equal sign
15:05 : another white space token and then a
15:08 : string which also makes sense
15:10 : now our job is to
15:13 : update our grammar so that each of these
15:16 : production rules sort of returns a
15:20 : clean object that represents
15:23 : that syntax element and we're going to
15:26 : call these things
15:26 : ast nodes how do you do that first let
15:29 : me say
15:30 : something about how nearly js sort of
15:32 : packs these tokens in
15:35 : and returns them back to you so whenever
15:38 : there's a rule and nearly js matches
15:42 : that rule like it it finds something
15:44 : that satisfies this rule for example
15:46 : expert
15:47 : it's like oh i found a string token so
15:50 : that matches expert
15:52 : it takes the right hand side symbols
15:55 : or in this case there's only one single
15:58 : symbol it doesn't matter
15:59 : it takes each thing in the right hand
16:02 : side
16:03 : and packs it into an array let's say the
16:05 : string was
16:06 : jackie and it has type of
16:09 : string right so this guy is the token
16:12 : and it is a string token it's gonna
16:15 : stick it in an array because who knows
16:18 : like there might be
16:20 : more tokens as in is the case with this
16:23 : one
16:24 : there's actually five separate tokens
16:27 : i'm going to pack it in an array and
16:29 : pass it into
16:30 : the next level attach this array
16:34 : to the var sign and then at the next
16:37 : level
16:38 : this far assign will be wrapped inside
16:40 : of another array again
16:42 : which means we'll actually get we
16:44 : actually get
16:45 : an array that contains
16:48 : this this array and this array will
16:52 : actually contain
16:54 : bits from lower down like this is a
16:58 : white space
16:59 : oh this there's an array here so this
17:01 : guy goes into here
17:04 : and as well as here and then this guy
17:08 : this guy since this comes from here and
17:10 : this is packed into an array
17:12 : we just have many levels of nested
17:15 : arrays
17:15 : uh to sort of get out of these
17:19 : like very tedious packing of symbols
17:22 : inside of arrays what you do is write a
17:23 : converter
17:25 : like this uh you can write it
17:28 : in javascript i usually like to use a
17:31 : arrow function
17:32 : syntax although you can use normal
17:33 : functions as well
17:35 : your converter function will take in
17:37 : that data which is this
17:38 : array so in this case you you're going
17:41 : to know oh
17:43 : this this is an array of one element
17:45 : because there's only one symbol to the
17:47 : right hand side of this rule
17:48 : if i want the first thing in the array i
17:50 : will say
17:52 : data index 0
17:56 : gets me the string right so if you want
17:59 : the expression to represent just this
18:02 : string
18:03 : and not have to wrap it into an array we
18:05 : would say return
18:06 : data index 0. and
18:10 : presumably i would want to do that for
18:12 : number as well
18:14 : and actually for most of the cases where
18:16 : the right hand side there's only one
18:18 : symbol you would want to do this so this
18:21 : is such a common case that nearly
18:23 : js supplies a shorthand for this
18:27 : which is the id function this is like
18:30 : don't change anything the identifier
18:32 : function it
18:34 : kind of has that feeling of just like
18:36 : whatever that is
18:38 : pass it on so that's what i'm gonna do
18:40 : i'm gonna
18:41 : slap this little thing at the end of
18:44 : each rule
18:45 : most of the rules where the right hand
18:47 : side is just one symbol
18:49 : okay so that's done but for this case
18:51 : it's not true
18:52 : that the right hand side has just one
18:54 : symbol it actually has
18:56 : five symbols so in this case i'm going
18:58 : to have a more
19:00 : custom function that will
19:03 : return an object that to me
19:06 : properly represents what this is and
19:09 : what i want to represent
19:11 : a vora sign as is an object
19:14 : that has a type identifier
19:18 : that says var sign and it tells it
19:21 : like what is the name of the var
19:24 : variable i'll call it var name
19:27 : and and it also has the value
19:31 : to be stored into the variable now where
19:34 : how do i get the var name
19:35 : well remember this guy is an array
19:39 : with five elements in it so if i want to
19:41 : get
19:42 : at this guy here well i want index zero
19:45 : this is one this is two
19:49 : this is three and this is 4.
19:52 : so to get at this guy to get the value i
19:55 : would want
19:56 : index 4. so what i want is data index 0
19:59 : and data index
20:01 : okay and at this point i pretty much
20:04 : have
20:05 : a converter for every symbol
20:08 : except for the white spaces and for the
20:10 : white spaces i don't care
20:12 : because i'm not getting information from
20:14 : the white spaces anyway
20:15 : so i'm going to leave those guys alone
20:17 : i'm going to re regenerate the parser
20:24 : and i'm going to run my parse script
20:26 : again
20:27 : and it will regenerate this dot ast file
20:30 : let's look at what it looks like
20:31 : now now it says the top level is an
20:35 : object which has the type of
20:38 : var sign and it has a var name of which
20:41 : is an identifier
20:43 : whose value is name and its value
20:46 : is something of type string and its
20:49 : value
20:50 : is uh jackie cool i'm going to conclude
20:53 : this
20:54 : uh episode here we've built a parse.js
20:58 : script which is able to parse
21:01 : this first example program