Make a Parser with Nearley.js - Part 8

In this episode, Waikit and I show you how to have your parser produce an AST - short for Abstract Syntax Tree. Also, I will answer a YouTube comment! Enjoy.

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : hello there welcome this is a drive by
00:03 : code session it's been a while since
00:06 : I've done one of these so I might be a
00:08 : little rusty I'm going to continue our
00:12 : video series about how to make a
00:15 : computer programming language so we're
00:20 : getting towards the sort of later part
00:25 : of how to use nearly Jas to build out a
00:30 : parser first before I start I want to
00:36 : tell the viewer the of the two or three
00:41 : of you about a project that I have
00:44 : started is called the fun programming
00:47 : language or the fun Lang fun prog Lang
00:51 : if you will the different programming
00:54 : language is a very small programming
00:58 : language is a proof of concept
00:59 : programming language the purpose of it
01:03 : is to teach developers functional
01:05 : programming it allows you to use a pure
01:09 : functional syntax using the fun keyword
01:13 : or a imperative style programming using
01:17 : the proc keyword but the secondary or
01:21 : perhaps the primary purpose of building
01:24 : out this language is to have like for
01:27 : people like yourself who are trying to
01:30 : learn how to implement a programming
01:32 : language yourself this is a project
01:35 : where you can like have a working
01:38 : example which you can dig into the
01:41 : source code tweak it muck with it break
01:45 : it and use it as a learning tool so if
01:50 : you're interested in checking this out
01:51 : that's the URL it's github.com slash
01:55 : airport way h / fun - Lang and also I've
02:03 : been getting some amount
02:05 : of comments on these videos and and
02:11 : that's quite assured to know that there
02:14 : are some of you that are actually
02:15 : watching these videos I want to read one
02:18 : of these comments and address the
02:21 : question that this viewer had the
02:24 : viewers name is nasty mixture nasty
02:30 : mixture and he made this comment one
02:33 : week ago he on the video about handling
02:39 : whitespace okay in the video about
02:42 : handling whitespace he asked how do you
02:44 : handle new lines in your grammar
02:48 : evidently in my example I didn't handle
02:51 : new lines I do believe in JSON JSON
02:58 : handles new lines and the fact that I
03:01 : didn't is a glaring omission so my
03:05 : answer to them is that you can just put
03:07 : in like new line string literals in your
03:13 : rules that's one way I'm gonna
03:15 : demonstrate it a little bit in my in the
03:20 : math arrests to make arithmetic parser
03:24 : that we were working on so this is the
03:26 : math I risk to make arithmetic parser
03:30 : which is at this point is able to add
03:33 : subtract multiply and divide so but it
03:36 : can also do these simple functions like
03:39 : power and it's got a number of built-in
03:42 : functions including square square root
03:46 : sine cosine absolute value and power so
03:50 : you can call these functions we were
03:51 : doing some powers of two's here it can
03:55 : also do addition subtraction and even
04:01 : parentheses I believe at this point it
04:03 : can do that so let me try out this is to
04:05 : read replay time out let me try I'm
04:08 : sorry running this parse script
04:14 : ok I think that worked I think the power
04:18 : of 2 to the 12 is 2 less than this
04:22 : number so that seems to work let me
04:25 : change it to 2 to the 4th ok yeah that
04:29 : would have been 16 plus 2 so that seems
04:32 : to work question now is how do we add
04:34 : the ability to have newline characters
04:37 : inside this string so let's do that hmm
04:44 : okay so I have a string now it's got
04:46 : some new lines in it and I made even
04:48 : jams on new lines in the middle of this
04:51 : this expression here like that because I
04:55 : want a format format it nicer or
04:58 : whatever and if we try to parse it right
05:00 : now we're gonna get an error because the
05:02 : grammar at present doesn't hand on the
05:05 : own lines
05:05 : I do have an existing place where I
05:08 : handle this optional whitespace it's
05:14 : made optional because of this star
05:16 : operator this means 0 or more
05:23 : occurrences of whatever that is and the
05:29 : whatever that is that's a character
05:31 : class that includes the space character
05:34 : and the tab character so if I wanted to
05:37 : add new lines to the mix so I have to do
05:40 : is really at the newline character into
05:43 : that character set and it should it
05:49 : should be good so now I want to
05:50 : regenerate the parser using NPM runs and
05:54 : versa and if you very unfamiliar with of
05:59 : the stuff we've done you should
06:03 : definitely go back and watch the
06:05 : previous videos in this series so so gen
06:09 : parser takes this math Tanny file and
06:14 : generates a JavaScript version of that
06:19 : guy and then
06:22 : then our parsed grip is able to use is
06:27 : able to use this generated JavaScript
06:29 : version of that guy to make a parser so
06:34 : now if we run parse again so that didn't
06:42 : work I have a suspicion it's maybe
06:45 : because the of the beginning whitespace
06:50 : and the ending whitespace I probably
06:52 : don't have a rule that says the input
06:55 : can allow for beginning whitespace and
06:57 : ending whitespace so let me test that
07:00 : theory by removing the beginning and
07:04 : ending whitespace from it and then
07:07 : indeed that works now if I don't want to
07:09 : allow for beginning and ending
07:12 : whitespace then what I want to do is say
07:16 : the beginning input can optionally have
07:20 : beginning and ending whitespace however
07:23 : I need to fix this transformer function
07:25 : now because if I if I left it as this
07:30 : and let it use the ID function it would
07:33 : actually pick the first match symbol
07:36 : which is a whitespace and pass it on to
07:38 : the next part we're just not gonna work
07:42 : out so I actually need to write a
07:48 : transformer function that takes the data
07:52 : which is the array that contains these
07:56 : three things so you can imagine this as
08:00 : an array that has whitespace an additive
08:05 : and then another whitespace so the thing
08:07 : I want is index 1 so so I want to return
08:16 : the thing at index 1
08:23 : regenerate the parser again run the
08:26 : script and now it works ooh let me put
08:31 : the beginning and trailing whitespace to
08:35 : see that yeah it works even with the
08:37 : beginning and trailing whitespace now
08:38 : okay so so that's how you can handle
08:42 : whitespace
08:46 : you could also optionally if you want it
08:49 : to match match literally a instead of
08:56 : using a character class you could use a
08:58 : string literal like that as well in your
09:00 : rules okay so that's what I have to say
09:04 : about matching newline characters let's
09:08 : get back into what we're doing so in
09:10 : this episode the plan is we're gonna try
09:15 : to whereas currently the code evaluates
09:20 : the result as part of the parsing
09:24 : process so what I mean by that is if you
09:28 : have an expression like 1 plus 1 the
09:35 : parser is a string you send that through
09:40 : the parser and the parser it is gonna
09:43 : give you the result number two okay
09:47 : we're gonna change this process so that
09:50 : the parser instead of generating a end
09:56 : result for us it's going to generate us
10:00 : a tree which looks like this
10:09 : so so and we're gonna call this guy das
10:15 : T which stands for a abstract syntax
10:22 : tree which I have sort of mentioned
10:25 : briefly in one of the first videos in
10:30 : this series and the abstract syntax tree
10:33 : is very important for programming
10:36 : languages because it's a representation
10:38 : which computer programs can use to to
10:44 : basically reason about the program or do
10:47 : stuff concrete do concrete things with
10:50 : the program the SC is basically a
10:52 : representation of what the program is
10:56 : when you wrote it so this this tree is a
11:00 : representation of this program 1 plus 1
11:03 : for example and the reason we might want
11:07 : to do this instead of just calculating
11:09 : the result outright is because we may
11:15 : want to translate this 1 plus 1 into
11:17 : another programming language perhaps
11:20 : JavaScript but perhaps lower level
11:23 : assembly language that D that the CPU is
11:27 : able to execute directly or perhaps we
11:32 : might have other uses for the ast tree
11:34 : one use for it so I'm gonna write like
11:38 : other uses for ast right why would you
11:46 : not want to just calculate the value
11:48 : outright and instead generate this tree
11:50 : representation of your program well you
11:53 : might want to write a checker like a
11:58 : like a type checker but it it you you
12:05 : might have things to check other things
12:08 : so like like a linter is actually a
12:12 : example a lender checks that your code
12:15 : is conforming to certain rules that the
12:19 : lender deems important so so those are a
12:24 : couple of other uses for ASD so testicle
12:27 : we're gonna instead of having the
12:30 : arithmetic parser or generate the answer
12:34 : right away we're gonna have it return an
12:36 : AST so what does that mean from the
12:38 : grammar perspective well a grammar
12:40 : perspective let's say if we have again
12:42 : the string one plus one currently the
12:47 : way it the way the parser resolves this
12:53 : string is well the parser has to start
12:55 : at input the input symbol and then it's
12:59 : gonna go down words in the tree I
13:05 : resolve it as an additive and then in
13:08 : this case we're gonna have a it's gonna
13:12 : break it up into the left-hand side and
13:14 : right-hand side with this with this
13:18 : matched plus sign in the middle so
13:20 : additive is gonna have a plus sign and a
13:22 : multiplicative of shorthand this and
13:27 : another additive oh my my handwriting is
13:33 : really hurting this show I think
13:36 : and then the next additive can get
13:41 : resolved into the singular
13:43 : multiplicative and then let me spell
13:51 : this out okay and then this
13:52 : multiplicative is gonna get resolved
13:55 : over here oh not over here because this
13:59 : one would be a singular alright so it
14:04 : would actually get resolved as this
14:06 : under in here there's pondering oh this
14:10 : is getting messy now so we're gonna get
14:13 : an unerring I'll just write unerring for
14:16 : short instead of under e expression
14:18 : under a
14:20 : and then honoree it is gonna end up
14:23 : resolving to a number here so is this
14:27 : one and number two a digit and did I
14:34 : think number has to resolve to digit and
14:40 : digits I'm actually gonna skip a few
14:42 : steps then because I'm running out of
14:45 : space but the number of results the
14:49 : digit and digit digit digits two digit
14:53 : and eventually we have the ones in the
14:56 : tree so this is sort of the parse tree
14:59 : and we don't want our ast tree to
15:02 : resemble this because that's too
15:04 : complicated so what really happens in
15:07 : the parser when it's doing its thing is
15:10 : at the end when a number is resolved we
15:15 : have this transformer that transforms
15:17 : the string data that the parser has
15:20 : collected into a JavaScript number here
15:24 : we put this decimal point in the case
15:27 : that there is one but if there isn't one
15:30 : it's just with the string of digits here
15:32 : we put it together send it to the number
15:35 : function to generate a JavaScript number
15:38 : for us which in return serve attaches
15:42 : this number to this this number symbol
15:47 : in this parse tree so we're gonna attach
15:49 : the number one here and we're gonna
15:51 : attach the number one here and then in
15:54 : if we go up to the UH Narae expression
15:59 : here oh gosh let me try to remove some
16:03 : of these things okay so an honorary
16:06 : expression well what is the thing that's
16:08 : gonna get attached to this on the
16:10 : expression that is gonna also depend on
16:14 : this transform function but what it does
16:17 : in this case
16:21 : if the only expression was result from a
16:24 : number it's just going to take a ID
16:27 : which is whatever the value was from the
16:29 : level below so again the number one is
16:34 : gonna get attached and that's gonna
16:36 : happen again and again like that so the
16:43 : value that gets attached to each symbol
16:46 : in these levels it's gonna sort of
16:48 : propagate until the place where it
16:52 : combines so this additive that has both
16:55 : a left-hand side and the right-hand side
16:56 : and the plus sign that one it's gonna
17:01 : happen here so this rule is actually
17:04 : gonna combine this one with this one by
17:07 : adding them together here and because it
17:12 : will use the case that this operator
17:14 : here is a plus sign so the thing to end
17:18 : up getting attached to this additive is
17:20 : actually two and then these two will
17:23 : propagate whoops not one but two this
17:26 : two will propagate up to the top level
17:28 : input and that's how the result of the
17:31 : parts is to what we want to do is
17:33 : instead of attaching these numbers to
17:38 : these sort of symbols as we go
17:44 : we actually want these guys to be a STS
17:46 : now instead of the actual values and so
17:53 : how do we do that well let's show it to
17:55 : you in code okay
17:58 : so again I'm gonna be replaying what
18:02 : Wieck it has done so let's see what he
18:05 : does so the first thing he does is gonna
18:09 : start modifying this transform function
18:12 : for the additive in the case where
18:15 : there's both a left-hand side and the
18:18 : right-hand side it's basically going to
18:23 : return an object instead of returning a
18:27 : numerical value here and this object is
18:31 : gonna have a type
18:33 : he's gonna call it operation the up is
18:37 : the operator which is coming from here
18:40 : which is index to which this is 0 this
18:45 : is 1 this is 2 so index 2 is the
18:48 : operator there's a left hand side which
18:50 : comes from this guy and the right hand
18:52 : side comes from this guy so and then
18:55 : he's gonna remove the previous one so
18:57 : let's see what we are ending up with
19:00 : here so basically we end up with
19:02 : JavaScript object as the ast node so
19:07 : this additive ast node is going to look
19:15 : something like this type operation and
19:23 : then there's gonna be up which is a plus
19:28 : sign and then there's a left-hand side
19:34 : which I actually don't know what that
19:36 : looks like yet so I'm gonna write blank
19:40 : here and the right-hand side but the
19:43 : left-hand side and right-hand side what
19:45 : that what those are gonna be is gonna be
19:48 : determined by what is the return value
19:52 : the value attached to the the
19:55 : multiplicative like one layer down the
19:59 : parse tree and additive value one layer
20:02 : down the parse tree and it could
20:05 : actually be yet another operation that's
20:07 : on the left-hand side because there
20:09 : could be another at or subtract or
20:12 : multiply operation but it could also be
20:15 : a function call on the left-hand side as
20:17 : well so we don't know so let's keep
20:20 : going he's gonna do the same thing with
20:23 : this multiplicative and return an object
20:27 : of the same shape here now removing the
20:31 : coat that was returning a numerical
20:32 : value and now we need to look at this
20:36 : function symbol so this function rule
20:41 : handles built-in function call
20:44 : and currently we're doing these
20:47 : calculation here to actually calculate
20:50 : the square root and the square and the
20:52 : sine and cosine etc instead of that
20:55 : we're not gonna do this actual
20:58 : calculation and we're gonna replace it
21:00 : with an AST no again a normal JavaScript
21:03 : object that has a description of what
21:06 : this function call operation means so so
21:12 : say it's the the type of this node is
21:15 : gonna be function call it's gonna have a
21:18 : function name which comes from this
21:22 : zeroth element of these matches there's
21:25 : the built-in function it's gonna have
21:29 : the argument which comes from over here
21:31 : that's index three you can count that
21:34 : and then that's it we're gonna move on
21:40 : to number so how are we gonna actually
21:42 : represent numbers I'm also gonna make
21:46 : that an ASC now we're gonna just say
21:48 : it's a type number but the value will be
21:51 : the actual number and we'll do it do it
21:55 : once for the decimal number case and do
21:58 : it once for the integer number case we
22:03 : generate the parser he messed it up it
22:06 : should be NPM run oops don't type in
22:10 : here Toby NPM run Jen parser so he has
22:15 : generally regenerated the parser now
22:18 : he's gonna run this note this par script
22:21 : oh he made a syntax error I think we
22:25 : have to backtrack to where he made that
22:27 : error it was here he was missing a
22:30 : closing parenthesis over here so fix
22:33 : that regenerate the parser and now now
22:37 : the parse generates an AST tree so you
22:41 : can see this the representation of this
22:48 : calculation there's power the power or
22:53 : take take two to the 12th power
22:57 : it's maybe how we would call it or maybe
23:01 : you call it we are gonna call the power
23:03 : function with arguments two and twelve
23:06 : so this therefore this the
23:08 : representation of this code is described
23:11 : in this ast and the top-level node is a
23:16 : function call whose function name is pal
23:19 : and its arguments there are two
23:22 : arguments his intolerance is an array
23:24 : the first argument is a number which is
23:27 : 2 and the second argument it's a number
23:30 : which whose value is 12 I mean try
23:33 : something now off-script so if we did
23:38 : say 1 plus 1 our previous example parsed
23:42 : it then we get a AST which at the top
23:47 : level is an operation whose operator is
23:51 : + and the left-hand side is a number
23:53 : which is 1 right hand side is a number
23:55 : which is 1 so that's a AST okay I'm
24:00 : gonna go back and follow white kit
24:02 : script now so he's gonna try a couple of
24:05 : different things - so so yeah looks like
24:10 : the power
24:12 : oh he's gonna do this power thing plus
24:15 : the result of a multiplication and then
24:18 : the whole thing divided by 4 and you can
24:23 : see this this ast can s arbitrarily deep
24:27 : because the calculations you want to do
24:30 : can become arbitrarily complex and
24:33 : really that's a sign that whenever you
24:36 : want to represent describe Oh calculate
24:41 : something arbitrarily complex that's a
24:44 : sign that you need a language you need a
24:46 : perhaps a programming language so this
24:48 : tree now so is an operation it's a
24:55 : divide operation so it really is like
24:57 : this guy the top level tree is really
25:02 : this one this is an operation
25:07 : right it's a divided operation and then
25:09 : the left-hand side of the divide
25:11 : operation is that guy which is what is
25:14 : that it is actually a plus operation I'm
25:17 : gonna simplify this this is left-hand
25:20 : side is this right-hand side the
25:22 : right-hand side of the divide operation
25:24 : is just a number of four but the
25:26 : left-hand side is this complicated thing
25:30 : which you this is so deep that the
25:33 : terminal doesn't even want to display it
25:35 : to you and there's actually a trick I
25:37 : think white it shows it off there's a
25:40 : trick in no js2 to use something from
25:45 : the util built-in library it's util dot
25:49 : inspect and it will give you the option
25:52 : of allowing more depth in the printout
25:56 : here okay so let's see that so now you
26:02 : can see all of the tree because we are
26:04 : aligned for depth ten so yeah so
26:08 : basically so the left-hand side of this
26:13 : divide operation is this whole big old
26:17 : thing and then what is that well that is
26:22 : a plus operation and it has a left-hand
26:25 : side and a right-hand side and it's
26:27 : left-hand side is a function call
26:31 : it's two to the power of eight see two
26:35 : to the power of eight and the right-hand
26:38 : side of this thing is a multiplication
26:40 : it's a multiplication operation its
26:42 : multiplies two to three so that's two to
26:46 : three all right
26:47 : I'm making a mess now so I'm gonna stop
26:50 : so so things are working and this is a
26:56 : good state of things in terms of the
26:58 : code let's do one more thing so we're
27:02 : gonna take we're gonna make it more
27:05 : convenient for the next step in our
27:07 : process which is to save the ast into a
27:14 : file and so that so that it's easier to
27:18 : read
27:19 : and then perhaps it's formatted nicer as
27:21 : well and I like to use a library called
27:26 : MZ that it really should be MZ I think
27:30 : the recorder missed em for some weird
27:33 : reason where is yeah we're using MZ I
27:39 : really like using MZ and why kid does
27:42 : too so for doing doing IO with no dress
27:48 : um like reading from the file system as
27:51 : etc if you are would like to learn more
27:55 : about MZ and using it with async/await I
27:58 : have made a video series on using
28:03 : async/await
28:04 : as well which covers that okay so now
28:08 : we're gonna require MZ this should be M
28:12 : ZFS I believe but in order to use I
28:16 : think he made a mistake here but that's
28:18 : okay he's gonna have to fix it later but
28:21 : the way you use it with async/await
28:24 : the reason we like to use this is
28:26 : because we can use it easily with
28:28 : async/await so when we want to read a
28:32 : file for example we just await the
28:35 : result of the right or if you want to
28:38 : write a file I should say in this case
28:39 : we just await the result of the file
28:42 : right and then we can write code in this
28:45 : straight line manner and so having to
28:48 : use callbacks so this is yelling at like
28:52 : it that he is importing a unknown module
28:57 : name so it really should be MZ /f s 4m
29:00 : ZZZ promise if I'd version of the file
29:05 : system module okay so now we have
29:09 : written the ast dot JSON let's go look
29:13 : at it yes T that's ast JSON yeah so
29:21 : that's what it looks like and we went
29:24 : over the contents of this but we have a
29:27 : file now with which you can go back and
29:30 : look at it so that's really cool I'm
29:32 : going to stop
29:33 : this video here thank you for watching
29:36 : if you have watched this far please
29:38 : leave me a comment in the youtubes and I
29:42 : hope to see you next time

Make a Parser with Nearley.js - Part 8 - Making ASTs

Transcript