Building MyPL Part 2 - Still Parser

In this drive by code session we finish build the parser for MyPL - the programming language we are making.

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : hello welcome to a drive-by code session
00:03 : welcome back this is going to be number
00:08 : four I believe in in a series of making
00:12 : a programming language if you have not
00:14 : seen the first ones I recommend that you
00:17 : go and watch those in the series before
00:20 : coming back and continuing on this one
00:23 : in order to get caught up so far we have
00:26 : written a parser for a very basic very
00:33 : limited programming language feature set
00:38 : this is the grammar for it we build the
00:41 : grammar using a tool called nearly and
00:44 : this is a file that parses some input
00:49 : supplied as a string and it'll execute
00:52 : the parser on it parse it and then show
00:56 : you the result of the parts parse J's
01:00 : and it says part of succeeded and the
01:02 : result of the parts was a number I'm
01:06 : also gonna try out a different screen
01:09 : layout where the terminal it goes on the
01:12 : right hand side and the code goes on the
01:14 : left hand side let's see how that goes
01:17 : um so this time we're gonna add the
01:22 : ability to use some white space so so
01:26 : let's say so currently the grammar
01:31 : allows a variable assignment like this
01:35 : as you can see
01:37 : however the grammar does not allow white
01:40 : space like like this if the user of the
01:44 : programming language wants to be able to
01:46 : use some white space in between the
01:49 : assignment operator he can which is kind
01:53 : of a problem because you know without
01:56 : white space your program can get
01:59 : difficult to read so how can we fix this
02:02 : well so we read this blog post called
02:07 : how to
02:08 : grammar good if you're interested in
02:11 : learning how to build parsers I
02:14 : recommend this he recommend that the
02:16 : white spaces should be represented using
02:20 : or this is one convention anyway you can
02:25 : represent a optional white space as one
02:29 : underscore in mandatory white space has
02:32 : multiple underscores and as you can see
02:35 : this is space character and then the
02:38 : star means zero or more occurrences of
02:41 : that thing well my handwriting is super
02:44 : bad right now but I'll let that go now
02:47 : that we have these guys defined we can
02:49 : start injecting these symbols into our
02:54 : production rules in the places where we
02:55 : want to allow white space so we're gonna
02:59 : say here for variable assignment between
03:03 : the identifier and the assignment
03:06 : operator there can be optional
03:08 : whitespace and then again after the
03:10 : operator there again can be optional
03:12 : whitespace so no let's try that will
03:17 : regenerate the parser so that composite
03:20 : now we run the parser with with the
03:24 : white space in between and it accepts
03:26 : that okay so that's white space
03:30 : well next let's try to support the print
03:33 : statement so in this programming
03:35 : language we can write a print statement
03:38 : like something like this you can say
03:41 : print and then a value here later on
03:46 : there will be bandit to allow arbitrary
03:50 : expressions as well so now let's just
03:53 : have a numeric value that you can print
03:55 : so we'll define a print statement as the
03:59 : word print and then some mandatory
04:03 : whitespace and then a number so given
04:08 : that let's let's regenerate the parser
04:13 : there we go and then let's just print a
04:17 : number because that's what it supports
04:19 : right now
04:23 : we can parse a print statement let's
04:25 : generate an ast for the print statement
04:28 : which will say it's an object with a
04:31 : type of print statement and its
04:33 : expression is the thing coming from this
04:38 : match over here so you can think of this
04:40 : guy as an array containing the parts of
04:46 : content the parts of the array are the
04:48 : symbols on the right-hand side of this
04:51 : rule here and so this guy here that's
04:57 : theta at 2 is that at 2 this would be at
05:04 : 1 because I think this is 0 1 oh no this
05:08 : is at - okay so theta 2 is this number
05:11 : here rebuild the parser and now we have
05:17 : this print statement represented as this
05:19 : object now let's allow the print
05:24 : statement to print arbitrarily complex
05:28 : expressions actually we at the moment we
05:32 : don't have arbitrarily complex
05:33 : expressions in terms of expressions we
05:35 : have numbers and identifiers x'
05:37 : in any case let's allow it to also print
05:40 : identifiers which are like variable
05:43 : references so so we'll say an expression
05:47 : at the current moment can either be a
05:49 : number or an identifier and everywhere
05:53 : we want to allow for an expression will
05:56 : put expression there in place of number
06:00 : and we'll use these ID functions to to
06:04 : return the first thing in the match
06:06 : because the right-hand side is only one
06:07 : symbol for these cases so we say a print
06:11 : statement can now print an expression
06:13 : which can either be a number or
06:15 : identifier regenerate the parser and we
06:19 : allow their we allow print the printing
06:25 : of an eye
06:26 : in the fire now let's see if that works
06:27 : and it does okay so now what else can we
06:33 : do let's have binary expression
06:35 : what's a binary expression well a binary
06:37 : expression looks like this
06:39 : that's a binary expression there's an
06:41 : operator here and there's a number here
06:45 : and there's a number here there's two
06:48 : operands thus binary so let's make that
06:51 : work so what what does a binary
06:53 : expression look like actually before
06:56 : that white kit is going to distinguish
07:00 : between honoré expressions and binary
07:02 : expressions under your expressions are
07:04 : not buying it only has one thing in it
07:07 : so I'm very expression is can either be
07:11 : a number or identifier definition of the
07:13 : expression used to be like this but
07:16 : we're gonna extend that to say to say an
07:21 : expression can also be a binary
07:22 : expression which is an honorary
07:26 : expression an operator with some
07:30 : assorted optional white space here and
07:33 : there and and then another under
07:36 : operator so unreal better this could be
07:40 : a plus and then another Hungary
07:42 : expression so what's an operator
07:45 : well this programming language can
07:47 : support add subtract multiply and divide
07:50 : so let's have those and white had wanted
07:55 : to be cute here and use the
07:58 : multiplication and division symbols here
08:00 : I think my son would be very happy with
08:04 : that okay because he's a math geek okay
08:09 : so now we'll represent the binary
08:12 : expression as an ast object like this
08:15 : the left-hand side comes from the 0th
08:20 : symbol from this match and the operator
08:24 : comes from the second symbol from the
08:28 : match in the right
08:29 : right how does that comes from this
08:30 : which is the fourth symbol in the match
08:33 : avoir assignment doesn't
08:35 : poor expressions yeah so this is gonna
08:38 : fail yep it fails so he's gonna fix that
08:43 : by allowing more assignments to accept
08:45 : expressions it's the right hand side of
08:48 : the assignment regenerate and now the
08:52 : VAR assignment can accept a binary
08:56 : expression and you can see this binary
08:57 : expression is self describing it has a
09:01 : left-hand side of one and the right
09:02 : hands I have to an operator of a plus
09:05 : sign and that's also it works with
09:10 : multiplication to so there's the
09:12 : multiplication what about printing
09:15 : that's the thing I wanted to see it can
09:18 : also print a binary operation see so
09:21 : this is an object over here of type
09:25 : print statement this object looks kind
09:27 : of squished here but it's an object
09:30 : that's I can assure you so it's an
09:33 : object with a type of print statement
09:35 : and an expression of the print is a
09:38 : binary expression whose left hand side
09:40 : is a which is a identifier and operator
09:45 : is the multiplication symbol and right
09:48 : hand side is the number two can it
09:50 : support complex more complex operations
09:56 : though so can you do a times 2 and then
09:59 : divide by 5 not currently so how can we
10:04 : make that work well this is where
10:07 : recursion comes in when it comes to
10:10 : grammar design so we can actually say
10:14 : the right-hand side you could do it on
10:20 : the left hand side to actually with
10:21 : nearly but in this case we're gonna do
10:25 : right hand side I mean say the right
10:27 : hand side of the operator is not an
10:31 : unknown expression but rather any
10:33 : expression which could potentially be in
10:35 : another binary expression and this by
10:38 : doing that we allowed recursion to work
10:41 : to allow these compound binary
10:45 : expressions that
10:47 : get chained one after another so what
10:50 : would happen here is the so this guy
10:56 : given a times 2/5 this would basically
11:01 : say first we have an unknown expression
11:04 : which is this guy that guy and then we
11:12 : have an operator that guy and then the
11:16 : next thing is another expression but
11:24 : this expression can be another binary
11:27 : expression oh and then so this guy too
11:32 : is this on the right operator again and
11:35 : then this division symbol now is the
11:40 : operator and then finally the 5 now is
11:44 : the expression that this time is an
11:46 : expression and it happens to be a number
11:49 : so we'll end up with a parse tree that
11:53 : looks like
11:56 : that's what we're gonna end up with
11:58 : let's see that guy in action now I mean
12:02 : okay so regenerate the parser and there
12:08 : we go we have this the expression of the
12:11 : print is a binary expression that has
12:13 : another binary expression within it for
12:15 : its right-hand side so very cool white
12:19 : kid decided to rewrite his par script to
12:24 : to generate AST files so when you give
12:28 : it a so you write your code in terms of
12:32 : in terms of files so he uses a library
12:38 : called MZ which is really handy for
12:41 : working with nodejs it makes it wraps
12:46 : all of the note G as api's using a
12:50 : promised based way of calling the API
12:54 : and we'll use async/await to do this if
12:58 : you're not familiar with async/await
13:01 : we have created a video series on that
13:04 : topic as well so you can go check that
13:07 : out if you like ok so now we're going to
13:13 : read code from a file which is going to
13:16 : in in that my Pio has its extension and
13:20 : then based on the base of the file name
13:24 : we're going to generate an output file
13:27 : that's going to end in dot ast I'm gonna
13:33 : call in to the parser and get the result
13:35 : and then write it out to the dot ast
13:38 : file I'm actually gonna hand wave over
13:41 : most of this code so basically at this
13:43 : point you can do this write a program in
13:46 : my Pia and that my PL like so and call
13:52 : parse passing in your program as to
13:56 : command line argument and it writes out
13:58 : a new file called that ast file but with
14:01 : the same base name of the file so if you
14:05 : give it example one my Pio it
14:08 : but example1 AST let's see what that
14:13 : looks like so yeah the output is the ast
14:18 : that represents this program here this
14:22 : is a VAR assignment we're gonna ast get
14:25 : is a VAR assignment cool all right
14:29 : where are we now so now let's allow
14:32 : multi-line programs it's it's pretty
14:35 : messed up that this programming language
14:38 : can only give you single line programs
14:42 : to support single line programs so how
14:44 : can we support multi line programs so so
14:47 : so far we're saying the program can be
14:50 : one of two things it can be a variable
14:52 : assignment or a print statement well
14:55 : know a program needs to be able to
14:57 : support multiple lines so we'll say this
15:02 : this is merely a statement what we call
15:05 : program before that was merely a
15:08 : statement and the program can either be
15:10 : a statement or a number of statements
15:13 : actually we're gonna define a thing
15:15 : called statement and then we're gonna
15:17 : say a program consists of a set of
15:20 : statements how does this statement thing
15:22 : work this rule
15:24 : well we're using recursion again we're
15:26 : saying statements can either be one
15:28 : statement simply only one statement or
15:31 : it could be a statement a new line and
15:34 : then some additional statements which
15:37 : cause back into itself and simply by
15:39 : using this recursion scheme you can have
15:42 : any number of statements now we're going
15:46 : to do some to some ast stuff
15:58 : okay so here here at this point in time
16:04 : we have a parser that can take any
16:09 : number of lines this program just
16:12 : happens to have two lines and generate
16:14 : an AST that is represented as an array
16:18 : of statement objects as you can see this
16:22 : one has two assignment variable
16:26 : assignments and that you can see the
16:28 : second one happens to be more complex
16:30 : one because the value of this assignment
16:32 : is a binary expression so this is what
16:36 : we have now I'm gonna try note that part
16:40 : now you have to supply the name of a
16:44 : program to parse it's gonna generate the
16:47 : ast file for your program looked at and
16:51 : now we got three things in the ast now
16:55 : okay so very good okay that's it sparse
16:59 : wild loops now so what's a wild loop a
17:03 : while loop it's gonna start with the
17:06 : word while some mandatory whitespace
17:09 : there's a binary expression that there's
17:12 : gonna be the conditional write the
17:15 : conditional that goes a while loop looks
17:18 : like
17:22 : we called this guy the body or I should
17:26 : say this whole thing this whole thing
17:28 : it's the body and the body is housed
17:32 : within these brackets this guy this guy
17:38 : that's the conditional so that's a while
17:40 : loop so this so the binary expression is
17:43 : the condition will have to extend it to
17:46 : work with comparison operators and then
17:49 : those are the statement the body
17:51 : consists of a set of statements which is
17:54 : nice that we define a thing called
17:57 : statements we can just reuse in here
18:00 : and then we have some new lines
18:04 : statement some optional white space here
18:07 : and then the closing bracket here this
18:09 : is the open bracket this is the closing
18:11 : bracket and we'll return the ast for the
18:18 : while loop as type while loop and the
18:20 : conditional comes from the second match
18:24 : of these lists of matches again think of
18:28 : these guys as an array of things and the
18:31 : body is gonna come from the 7th
18:34 : let's count so 7th so you think of this
18:38 : guy as an array right so this is 0 1 2
18:44 : yeah that's 2 goes here this is 3 4 5 6
18:52 : 7 yes 7
18:55 : that's the statements that goes into the
18:57 : body so that's how we got the 7 but we
19:01 : don't care about those other symbols we
19:02 : just care about this conditional and
19:05 : statement ok
19:09 : now we need to expand the operator list
19:12 : to allow the comparison operators and
19:16 : then now we should be able to regenerate
19:19 : the parser and be able to write a while
19:23 : loop where's my while oh I think there's
19:27 : already a program that has a while loop
19:29 : in it
19:29 : no he's gonna write it now okay so this
19:32 : is a wild loop this well it's gonna loop
19:35 : ten times by the looks of it no part of
19:39 : this program now something's not right
19:43 : let's figure out what it is
19:45 : we forgot to include while loop as one
19:48 : of the possible statements so add that
19:51 : and to sort of turn on this rule and now
19:56 : it's able to spit out and ask t4y lips
20:00 : this is really awesome so let's do a
20:04 : side-by-side here so first line is a
20:09 : variable assignment that's that and then
20:12 : the next statement is a while loop which
20:15 : starts from here and ends all the way
20:18 : there there's a conditional which a
20:22 : binary which is a binary expression
20:25 : left-hand sides and right hands at ten
20:27 : and the operator is less than so you can
20:31 : see all of that here and then the body
20:33 : of the while statement there's two
20:36 : statements the first statement is this
20:39 : variable assignment there and then the
20:42 : second statement is this print statement
20:43 : so it all makes sense
20:46 : oh this code is represented correctly by
20:51 : the looks of it by this ast and that's
20:56 : super cool so that is the end of this
20:59 : episode I hope you enjoyed it and the
21:02 : next one we're gonna finish off the
21:06 : building of my pio by building a code
21:10 : generator that takes my PL code which
21:13 : looks like this and generates
21:16 : JavaScript code in in other words we're
21:19 : gonna build a translator and it is
21:21 : commonly referred to as a transpiler
21:23 : there's gonna take the code in one
21:27 : programming language and translate it to
21:30 : JavaScript I hope to see you soon bye