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.

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