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

Published on Aug 20th 2019Duration: 20:51Watch on YouTube

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: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: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
• 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