How to Build a Parser with Nearley.js - Part 5

Continuing in the series on making parsers, this time, we build a calculator that can add, subtract, multiply and divide. In particular, we tackle the issue of operator precedence.

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : hello and welcome to week drive by toad
00:02 : session in this it in this episode we're
00:05 : going to build a parser this time we're
00:10 : gonna go more towards doing computation
00:14 : so the parser for this time is going to
00:16 : parse a simple arithmetic expression
00:20 : that can basically do add subtract
00:24 : multiply and divide so an exam example
00:27 : of that would be a 1 plus 2 1 plus 2
00:33 : times 3 and so forth so just starting
00:38 : off simple but the calculator that we're
00:42 : going to be able to actually be able to
00:43 : evaluate the the answer based on this
00:48 : expression and give you the correct
00:50 : answer in this case the answer should be
00:53 : 7 if I'm doing that correctly
00:56 : so let's get started so first thing
01:00 : we're gonna do again like it did this
01:02 : code I'm just gonna replay what he did
01:04 : and explain it so the first thing is
01:09 : we're gonna generate a new package JSON
01:12 : file and again install nearly died yes
01:17 : if you're not familiar with nearly at
01:19 : all go back to the previous videos that
01:23 : we created in this series and you will
01:26 : be able to get a good introduction to it
01:28 : I hope ok so now we're gonna make a
01:33 : grammar for this and we're gonna sort of
01:36 : repeat what we already done in past
01:37 : episodes which is a small grammar to
01:41 : match numbers so we're gonna say a
01:43 : number is a number of digits followed by
01:46 : a dot followed by some more digit or
01:48 : simply a bunch of digits what's digit
01:52 : digits is either one digit whether one
01:57 : digit or a digit followed by more digits
01:59 : and again this is called the recursion
02:02 : trick that allows us to match one or
02:05 : more of something in this case digits
02:08 : and then what's a digit they
02:10 : is a character within the range 0 to 9
02:16 : and this guy is called a character class
02:18 : and we've also covered that in past
02:21 : episodes so now with this we're gonna
02:24 : sort of take the matched strings and
02:28 : sort of sort of build up an AST or
02:33 : representation of what was matched in
02:36 : this case I ID says just take whatever
02:39 : in data insert and that is there in this
02:42 : case there's gonna be some 1 1 character
02:48 : long strings here 4 digit ID means just
02:51 : return whatever is there it's customary
02:54 : that when the right hand side of a
02:57 : production rule has only one single
03:00 : symbol in it as is the case here and
03:05 : here we're just gonna use the ID
03:07 : function to return whatever the first
03:09 : thing is but in the case word it has
03:14 : more than one symbol we need to write a
03:16 : more detailed transformer and this guy
03:19 : so these functions actually this one as
03:23 : well we call these transformer functions
03:26 : that's at least that's what I call them
03:28 : I don't know if there's a better name
03:30 : for these things but this guy is gonna
03:34 : say I got two strings one coming from
03:37 : the digit symbol one coming from the
03:39 : digit symbol I'm just gonna join them
03:41 : together to comprise the thing that I
03:43 : want this guy to represent we will write
03:49 : transformers for these these two rules
03:52 : as well number going to digits and
03:55 : number going to digits a dot and a digit
03:57 : for a number going to digits we're gonna
04:00 : take the four the match from the first
04:02 : symbol that's data at zero and use the
04:05 : number of conversion function to convert
04:08 : it to a number for the decimal number we
04:12 : will kind of use string concatenation to
04:15 : form the correct decimal number based on
04:20 : the input and then again use the
04:22 : number conversion function to give you
04:24 : an actual JavaScript number so with that
04:29 : we need to set up nearly the nearly
04:33 : compiler that's C stands for compiler
04:36 : will set up the nearly compiler to
04:38 : compile this math dot any grammar file
04:41 : to a JavaScript file will set up a
04:45 : script to do that so we can run that
04:48 : conveniently on the command line using
04:50 : NPM run gen parser and now we have a
04:53 : math address which is the JavaScript
04:56 : representation of this grammar and now
05:04 : we can start writing a parse tree s that
05:08 : utilizes this math that is to parse some
05:12 : values first let's just feed a number in
05:16 : it because that's what we have what
05:19 : we're able to parse at this point okay
05:23 : so we need to require the math dot - yes
05:27 : that was generated by the nearly
05:29 : compiler and then plug it into this
05:32 : instantiation of the nearly parser once
05:36 : you have a parser instance you can start
05:39 : feeding strings in it and we're gonna
05:40 : feed in one into it and it gets us one
05:45 : and you can see by the fact that I'm
05:49 : you're rentin it okay by the fact this
05:54 : is a this is an array that has a number
05:55 : of one-minute by the fact that it's not
05:57 : in double quotes or anything like that
05:59 : we know that it has converted into a
06:04 : number okay and it can do decimal
06:08 : numbers as well okay that's good so the
06:11 : next thing we want to do after that is
06:13 : to be able to do sums how do you match
06:15 : us some more some is a number a plus
06:18 : sign and then another number at least
06:21 : that's the simplest formulation of a
06:23 : song let's have some optional whitespace
06:29 : we did a episode on white space so we're
06:33 : gonna use that trick here to match zero
06:36 : or more white spaces which are either
06:39 : spaces or tabs and we'll inject the
06:44 : optional white space sort of sprinkle
06:46 : them into the places where we allow
06:48 : optional white spaces and so now we can
06:53 : have a summer and we'll say the input
06:55 : can either be a sum or just as a single
07:00 : number and let's also write a
07:03 : transformer for this we could choose to
07:07 : have a generate an AST which is
07:12 : represented by a javascript object and
07:14 : I'll she show you how that works so this
07:16 : is an object with a type property which
07:21 : says sum and the left-hand side and the
07:23 : right-hand side both of which I
07:25 : represented how this needs to be 4 so
07:29 : the left-hand side would be 3 4 so the
07:40 : left-hand side is gonna be this number
07:43 : which comes from the 0th index and then
07:45 : the right-hand side is gonna be this
07:47 : number which comes to the fourth index
07:49 : and so if we ran the parser if we gave
07:56 : it a sum like 1 plus 2 and we ran the
07:59 : parser compiled a parser now run it we
08:04 : get this object which is an AST abstract
08:08 : syntax tree node which represents this
08:12 : particular Sun what we could choose to
08:16 : do though instead of representing this
08:20 : this part as an ast will talk about a
08:25 : STS but in the future so I'm gonna do
08:28 : that so I'm gonna skip over a STS for
08:30 : now and instead we're gonna evaluate
08:33 : this just some right away by taking the
08:37 : number here and the number here isn't
08:38 : just using javascript
08:40 : together if we did that regenerate the
08:43 : parser run it I should get the song and
08:46 : this is very interesting
08:48 : this is like the Parker is doing the
08:51 : evaluation of the result immediately and
08:54 : there is something that there's an
08:56 : option that you have now we're able to
08:59 : have sums but that's not good enough if
09:02 : we wanted to have a more than one some
09:06 : one some and then some that some with
09:09 : another thing so two additions in a row
09:13 : this grammar is at the present not able
09:16 : to do that and we'll see why it
09:18 : complains is saying I see like another
09:22 : white space here but I'm not really
09:25 : expecting that because it's still trying
09:29 : to match a number trying to match the
09:32 : dismal point or trying to match another
09:34 : digit here and that's because the
09:37 : grammar doesn't allow to compound
09:41 : operations it only allows number plus
09:45 : sign and then a number so if you want
09:47 : more competitions to happen what you're
09:49 : gonna have to do is again usually
09:52 : recursive trick so what is this
09:54 : recursive trick here well you can say a
09:57 : sum is a number a plus sign and then
10:01 : another sum which then could have even
10:06 : more plus signs in it and this and
10:09 : because of the power of recursion you
10:11 : can actually do it endlessly you can
10:15 : have engines endless number of addition
10:17 : symbols but you have to stop somewhere
10:20 : so we also need to allow a sum to simply
10:24 : be one number and so let's see this work
10:30 : let's see if this even works so we
10:33 : compile the parser regenerate the parser
10:35 : and run this and we seen this this is
10:40 : clear off just jammed one two and three
10:42 : together it's probably because we don't
10:46 : have a transformer for this rule so
10:48 : we'll add it
10:50 : just use the ID transformer and now it
10:54 : actually does evaluate to some for us
10:57 : and I'm gonna actually try it I just
11:00 : said you could add any number of these
11:02 : so I'm actually gonna try going all the
11:08 : way up to nine see if that works
11:10 : yeah that seems to be right my head okay
11:14 : so okay so now we can extend that and
11:23 : say well and we don't even need this we
11:28 : don't need this rule even to say that
11:31 : the input could either be a sum or a
11:33 : number that because a sum can already
11:37 : simply be a single number so we actually
11:40 : don't need this rule here and end up
11:44 : with a simpler grammar and that still
11:47 : works all right what about
11:49 : multiplication if we want to generalize
11:52 : to multiplication subtraction and
11:54 : division let's extract out this plus
11:57 : sign as an operator and allow the
11:59 : operator be one of these four symbols
12:02 : and we're gonna use the special symbols
12:05 : for multiplication and division because
12:07 : if we want to look cool and instead of
12:12 : calling this some will call it operation
12:14 : now and now we'll use a switch statement
12:18 : to differentiate between the four
12:21 : different operations based on the
12:24 : operators symbol the words sum we've we
12:30 : need to fix this renaming the residue of
12:34 : our renaming and call that operation
12:39 : instead of sum so now we regenerate the
12:43 : parser there and parse and now it can
12:49 : still do its job it can do additions etc
12:53 : but it can also do multiplication so
12:56 : this
12:56 : two two times two is four try a few more
13:01 : think no division should be like that
13:04 : 2/5 is 0.4 so the different operators
13:08 : are working now okay only that there's a
13:13 : problem operator precedence so at the
13:18 : moment the grammar doesn't handle
13:21 : doesn't sort of favor multiplication
13:27 : over addition which it actually needs to
13:31 : do so given this guy at the moment what
13:38 : the grammar does is so it doesn't matter
13:45 : at the moment which of these order
13:48 : it is the grammar is actually gonna
13:52 : compute the last one of those first and
13:56 : then and then compute the compound one
14:00 : and the reason that is is because of the
14:04 : order of this rule you're saying an
14:06 : operation is good say this guy is an
14:11 : operation is saying the operation is
14:13 : first a number which that is a number
14:19 : and then an operator that's that's the
14:23 : operator and then an operation so this
14:28 : is another operation which we which we
14:33 : recurse back to itself and then this guy
14:36 : matches another number here number and
14:41 : then another operator in this case and
14:44 : then this is still another operation but
14:49 : then it uses the next rule down here
14:53 : that says oh this is a number it was a
14:58 : number first before I was in operation
15:00 : so this could be a number here so
15:03 : because of this the ordering of this
15:07 : rule will end up
15:09 : with a tree that looks like oh this is
15:13 : super messy I'm sorry let me do it again
15:17 : we'll end up with a tree that basically
15:19 : looks like this so this is operation and
15:28 : then and then this is the next sort of
15:34 : compound operation so this this inner
15:38 : operation is the one to the right well
15:41 : that's what we want is the inner
15:42 : operation to favor the multiplication
15:46 : over the addition and in order to do
15:50 : that we actually have to rewrite the
15:52 : rules I'm gonna call the multiplicate
15:55 : serve differentiate between the additive
15:59 : and the multiplicative we'll say the
16:02 : multiplicative it can either be multiply
16:04 : or divide because in in a sense a
16:07 : division is kind of just a
16:09 : multiplication with a reciprocal and
16:14 : then we'll say additive is either the
16:19 : plus operation or the - operation and
16:21 : we'll have the additive sort of defer to
16:26 : the multiplicative so basically we're
16:28 : seeing an additive thing is gonna add
16:31 : together a bunch of multiplicative
16:32 : things so if we have this this this and
16:41 : this is gonna be multiplicative they're
16:46 : gonna get matched with a multiplicative
16:50 : first
16:56 : and then the additive will actually
16:59 : combine these two guys together like
17:04 : this so having this guy start off first
17:10 : and start at a top level and then defer
17:14 : to the multiplicative we'll allow this
17:17 : to happen but of course we'll also say a
17:20 : multiplicative could also potentially
17:22 : just be a number like it could just be a
17:26 : 5 and that's what allows for the case of
17:29 : just 5 plus 5 5 plus 7 for example
17:32 : because a single number can be
17:34 : interpreted or to derive a
17:37 : multiplicative so that's the strategy
17:42 : let's make it happen
17:43 : so we'll say additive is a
17:46 : multiplicative I had plus or minus sign
17:50 : and then more additive that's to keep
17:54 : the recursion going to have another
17:57 : additive after it or it could just be a
18:00 : single multiplicative and then a
18:02 : multiplicative is a number multiply or
18:06 : divide sign and then another
18:08 : multiplicative and that's the recursion
18:10 : rule or multiplicative multiplicative
18:14 : can be simply a number so we basically
18:19 : just instead this one general operation
18:23 : we have two operations one of which sort
18:27 : of has a precedence over the other and
18:30 : then we'll write the transformers for it
18:36 : adding in the white space as well so at
18:39 : this point we have some mistakes here
18:42 : which we'll fix so this is a still a
18:45 : switch statement but only handling the
18:47 : plus and subtract cases and this one
18:50 : only handling the multiply and divide
18:54 : cases and we start the grammar out at
18:58 : additive and then an additive can be an
19:01 : addition of a bunch of multiplicative
19:04 : and this is the thing that makes it work
19:06 : and the multiplicative is multiplication
19:10 : of a bunch of numbers you can look at it
19:12 : like that so so now this part let's test
19:20 : it I'm gonna write some code to test it
19:24 : myself so let's see what's the answer
19:27 : here this is two times two should happen
19:30 : first and then at two so the death
19:32 : should give us six if we did it the
19:38 : other way around it should give us the
19:40 : same answer yes but if you did it the
19:45 : wrong order then it would have been
19:47 : eight so this seems to work
19:51 : let's do I'll just do a couple more
19:54 : tests here two divided by two so this
19:58 : should have done to the vote by two
20:00 : versus one and then add that to the
20:03 : result of two times two this should give
20:06 : us five yes okay so this parser seems to
20:12 : work and we've done a simple example of
20:16 : operator presidents and this is how you
20:19 : would do it with with the context-free
20:22 : grammar here if you have any questions
20:26 : about this if this was confusing to you
20:30 : please write me in a youtube comment the
20:35 : next steps for this grammar is to allow
20:37 : for apprentices but as well as adding
20:42 : functions to the mix and also variables
20:45 : adding variables to the mix so that's
20:47 : coming up in the future I hope to see
20:49 : you soon

How to Build a Parser with Nearley.js - Part 5 - Operator Precedence

Transcript