How to Make a Parser using Nearley.js

In this drive by code session we continue making a JSON parser. After having make a working parser for a subset of the functionality in JSON, we’ll introduce the ability to embed JavaScript code in the grammar to customize the result of a parse. Again, Waikit wrote the code, and I’ll replay them and explain what he did. Enjoy!

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : hello welcome to a drive-by code session
00:02 : we're continuing from our last video
00:08 : which was the introductory video to
00:10 : using nearly is to build a parser and
00:15 : let me give you a recap on where we act
00:19 : if you missed that video I recommend
00:22 : that you stop this video go watch that
00:25 : one and then come back okay so this is
00:30 : what we built we built a subset of a
00:32 : JSON parser it handles some portion of
00:37 : what a JSON parser needs to handle so
00:41 : for example if we give to this parser an
00:45 : array honest JSON encoding of an array
00:50 : with two numbers in it we run this file
00:55 : then it is able to parse it the result
01:01 : of the parse here the parser after the
01:05 : parse the parser will output some
01:08 : results that result is a representation
01:13 : of what it parsed we have basically hand
01:19 : waved over what that is and how that
01:22 : works and that's what this episode is
01:25 : going to be about okay so before we get
01:30 : into that though I want to give you a
01:32 : visual illustration of what actually
01:34 : happens when you take an input such as
01:40 : this array how is that represented or
01:46 : perhaps how is that parsed by the parser
01:50 : well the parser uses a bunch of rules or
01:53 : these rules don't the one that we wrote
01:56 : let me move the rules for the number up
02:00 : a little bit higher the order of the
02:04 : rules mostly don't matter except for the
02:07 : fact that the very first rule is what
02:09 : really starts with okay okay so let's
02:16 : say let's say we have this string input
02:21 : I'll put double quotes around it so that
02:24 : you know it's a string well how how does
02:32 : this get parsed well you might see that
02:35 : oh there's a number here the 1 and based
02:40 : on this rule or I should say a digit
02:43 : perhaps so the digit 1 gets recognized
02:48 : as a digit so internally in the parser
02:53 : that's what happens a 1 gets kind of
02:55 : internally transformed to a digit symbol
02:58 : and then and then further a digit symbol
03:02 : can be converted to a digit symbol and
03:09 : then a digits can become a number and
03:16 : then a number based on this rule and can
03:20 : get converted to a value and these sort
03:26 : of conversion maybe they're not
03:27 : conversions per se but they're
03:29 : derivations this is how you this is how
03:32 : a very low-level thing a 1 character
03:37 : gets sort of in increasingly more higher
03:42 : level and abstract in becoming these
03:48 : higher-level concepts like numbers and
03:50 : values now how does it get eventually
03:53 : resolved to an array well let's keep
03:55 : going let's do this number two which
03:58 : will go through the same kind of
04:00 : derivation here digit and then two
04:03 : digits and then two number and then two
04:08 : value okay so now we can start with this
04:13 : array parsing in order to get back to
04:17 : the array we need to satisfy array
04:20 : thumbs so let's see how we can get
04:22 : well a value simply a value is array
04:25 : items and array items can also be a
04:28 : value in a comma and then some more
04:30 : array items well we do already have a
04:32 : value this guy and a comma and this
04:41 : comma here and then I need another rate
04:47 : items but I value can derive an array
04:50 : items which is what we need to satisfy
05:00 : this rule here and we have all things we
05:02 : have a value a comma and our items so
05:07 : those three things gives another array
05:13 : items and then array items now now
05:19 : enclosed in these brackets
05:29 : well finally gives us an array so these
05:35 : three guys gave us an array and then
05:37 : array gives us a value and finally a
05:44 : value gives us the top-level input and
05:49 : we're done so we kind of work backwards
05:52 : from the lowest level to the highest
05:55 : level and this is this visual
05:59 : representation is is called a parse tree
06:03 : and now we can we can soft create some
06:08 : representation of this parse tree and we
06:15 : can we can choose whatever
06:17 : representation we want for this parse
06:19 : tree and and forth for this exercise
06:25 : we're gonna say the parser is going to
06:28 : generate the the JavaScript
06:31 : representation of that what that JSON
06:35 : so what we're after is that this one
06:40 : here gets us the JavaScript number one
06:45 : the two gets us a JavaScript number two
06:47 : and then this array gets us a jobs good
06:50 : array okay so that's what we're after
06:54 : let's go do that right okay so okay so
07:06 : we're gonna do that step by step and
07:11 : we're gonna start with the easy ones
07:12 : first so to make our lives a little
07:15 : easier we're gonna start trying to make
07:18 : bullying's work so if we write again Y
07:23 : kid did this coding session I'm three
07:25 : playing it so oops I'm not supposed to
07:29 : do that all right
07:31 : okay so if we if we run the script right
07:35 : now
07:35 : it parse is successful but what we'd
07:38 : like to do now is for this results to
07:42 : give us a meaningful thing that
07:45 : represents this what's being parsed here
07:49 : which in this case it should be the
07:51 : boolean JavaScript value true so what do
07:56 : we do well in nearly you can you can
08:02 : embed JavaScript in this grammar and the
08:06 : way you embed it is you use this escape
08:09 : sequence sort of or escape block that
08:13 : starts out with a um you make a slightly
08:18 : larger okay it starts out with a open
08:23 : curly bracket a % and it closes with
08:27 : another % and another in a closing curly
08:30 : bracket within it what you're gonna do
08:32 : is write a function that returns some
08:35 : JavaScript value and your if you're
08:39 : using a version of node that supports
08:42 : the newer ACMA script features then you
08:46 : can use
08:47 : suggest such as this arrow function
08:50 : syntax here I'm saying to return this
08:54 : true string literal that's been parsed
08:58 : I'm gonna just return the JavaScript
09:01 : value of true okay so now we and he put
09:08 : this on a separate line which is wise I
09:11 : think because otherwise if you do this
09:14 : to longer lines and we start getting
09:16 : messy and and he does that for false
09:20 : again and after you've modified the
09:23 : grammar file you have to regenerate the
09:25 : JavaScript version of their parser for
09:27 : the grammar I should say north blowing
09:34 : oh yeah so now ignore this line here
09:38 : don't worry about that now the par
09:41 : success but there is a true value inside
09:44 : these results but why is there like
09:48 : three levels of nested arrays in here
09:51 : well the first level the first level is
09:55 : expected but because parser sometimes
10:01 : may have multiple results in the case of
10:03 : ambiguous grammars which is like the
10:07 : same string can be parsed multiple
10:11 : different ways by the parser those are
10:14 : in general undesirable and but they can
10:18 : happen but we're not gonna worry about
10:20 : that right now but um now why are there
10:24 : two more levels of nested arrays in
10:26 : there well it's because that's how many
10:29 : levels of derivations there were to
10:32 : parse this boolean value okay so I mean
10:38 : let me draw that out so if you have this
10:41 : ring true then okay then that derives
10:53 : the symbol boolean and then a boolean
10:58 : here derives the symbol value finally
11:05 : the value derives the input symbol so
11:12 : and we said this guy when when this true
11:17 : matches based on this boolean rule we're
11:23 : saying in order to represent a boolean
11:27 : here because this is the rule that
11:28 : defines what a boolean is we're saying
11:31 : if you see the literal truth then I want
11:34 : to represent this boolean with the
11:38 : JavaScript value of true so in a sense
11:41 : we're like attaching this value to the
11:43 : boolean okay now when when we activate
11:50 : this rule here to derive a value from a
11:55 : boolean the way early or the way nearly
12:00 : works is it'll take the symbols that are
12:05 : matched on the right hand side and in
12:07 : this case there's only one of them and
12:10 : put it in a ray and then and then that
12:13 : this guy gets promoted to be represented
12:19 : in by the value unless you perform a
12:24 : transformation so so basically the value
12:30 : that got promoted to rip or that yeah
12:34 : the JavaScript value that got promoted
12:36 : to the value symbol is true inside an
12:40 : array and then this happens again with
12:42 : this rule here
12:44 : this outer array is wrapped around the
12:48 : thing that got passed to it to represent
12:51 : value and therefore we got
12:57 : - array wrappers around this true value
13:01 : which looks a little bit weird and the
13:04 : way that you can sort of unbox it which
13:08 : i think would make sense to unbox these
13:10 : arrays in this situation and the way you
13:14 : do it is like this you take the data
13:22 : that is represented which again it it
13:27 : it's gonna look like an array with just
13:31 : one thing in it because there's only one
13:33 : symbol on the right hand side of this
13:35 : rule here and and you just unbox it yeah
13:41 : because the data is an array you're just
13:43 : gonna get the zeroth element out of it
13:45 : and then we'll do the same thing for
13:47 : this rule as well well unbox the first
13:52 : symbol that the order value within the
13:56 : first symbol of the right hand side
13:58 : which is the value and then we'll say
14:02 : that is the thing that represents the
14:04 : input now so now if we regenerate the
14:07 : parser and run it then we just get one
14:11 : true again this outermost array is
14:14 : expected because the result of the
14:17 : parser that there's can potentially be
14:20 : multiple parses coming from the parser
14:23 : so this is cool
14:25 : now because this pattern is so common
14:29 : and a lot of cases where you have just
14:32 : one symbol on the right hand side of the
14:34 : rule you probably want to do it because
14:37 : this is so common nearly gives you a
14:39 : convenience function called ID that does
14:44 : exactly that so you can write this in a
14:47 : lot shorter way and it does the same
14:49 : thing as you can see so we're actually
14:54 : gonna do this for most of the rules
14:59 : almost all the rules where on the right
15:02 : hand side there is only one symbol
15:07 : so he finds all the room although there
15:10 : are some special cases where that's not
15:13 : what we want and I'll show you that
15:15 : later so these cases see where they're
15:19 : the right hand side there's only one
15:20 : symbol we're gonna say use the ID
15:24 : function which just unpack stat or right
15:27 : but for the ones where there are
15:29 : multiple symbols on the right hand side
15:30 : we're not gonna do that okay so for the
15:34 : no as well we'll just say for the oh
15:37 : this one we're not gonna this is a
15:40 : literal so we handle it like the boolean
15:43 : ones like the true and false ones and
15:45 : you're not even caring whatever what the
15:48 : data is in this case if you did receive
15:51 : the data here then the data would be the
15:55 : string in an array okay okay so now
16:07 : we're gonna handle the array now so for
16:11 : the array to represent an array we want
16:14 : to use an array a JavaScript array to
16:17 : represent an array that seems logical
16:20 : so we're saying if we match this empty
16:22 : array we're gonna return a JavaScript
16:24 : empty array and then if we get some
16:29 : array items we're gonna return the
16:33 : representation that was returned by
16:35 : array items and and to help you
16:38 : visualize this so this is an array our
16:47 : data is an array that contains three
16:50 : things one is the first symbol which is
16:53 : the open bracket the second one is irate
16:56 : items or I guess I should have said the
17:00 : zeroth one is the open bracket then the
17:04 : first one is array items and this closed
17:07 : bracket is the second one so the data
17:10 : that's gonna come is going to come from
17:13 : the array items so therefore
17:18 : it's the one index that one but we
17:21 : haven't really done anything with the
17:23 : data associated with array item oh we
17:26 : have done this one but this is wrong
17:28 : actually we need to fix it so let's see
17:32 : what we're gonna do here so because
17:35 : we're saying array items we're gonna
17:37 : make it return on a right there's
17:39 : actually he made a error here he forgot
17:43 : to close this bracket over here so there
17:49 : needs to be a closing bracket here he's
17:51 : gonna fix that later so if you match if
17:58 : you match one value or there's like
18:03 : there's one item one value within the
18:06 : array we're gonna return an array that
18:09 : wraps around it so this is very close to
18:13 : what id does but not exactly because if
18:16 : we want to wrapped here an extra array
18:19 : around the inside and actually now that
18:24 : I'm think about it maybe this is exactly
18:26 : what it would have done if we leave this
18:29 : out but that's cool and then if if
18:34 : there's one value and then a comma and
18:37 : then another array items which could
18:39 : have come from the previous match of
18:42 : array items which we know is an array of
18:44 : items then we're gonna make a new array
18:48 : and then put the 0th one here so so this
18:56 : guy is 0 this is 1 this is 2 so we know
19:02 : two data index 2 this is gonna be a race
19:08 : so we use the spread operator to
19:10 : basically copy the contents of disarray
19:15 : we know this guy is an array so we take
19:19 : this array and copy it into this this
19:23 : new array that we're making so that's
19:25 : the plan let's see if it works
19:34 : no because there's a syntax error here
19:38 : as I mentioned so I think he has to fix
19:41 : it yeah yeah he fixed it and regenerate
19:46 : the parser again and now we get an array
19:49 : of 1 2 & 3 but there are strings now so
19:54 : but we're expecting numbers only so
19:58 : let's see how we can convert them to
20:01 : numbers oh he wants to test it for
20:06 : true/false and now first because those
20:08 : are already working and looks like they
20:10 : are so this is great to false and no
20:14 : inside of an array next perhaps he wants
20:20 : to tack whole numbers now yes so we have
20:23 : array that has a 12 and a 3 in it so to
20:33 : convert a string because when when data
20:38 : when string information is in coming
20:42 : from the parser and you want to convert
20:43 : it to a number in JavaScript the a good
20:48 : way is just using this number function
20:51 : and the data is gonna come in as an
20:56 : array of stuff here
20:58 : I think array of strings although it
21:02 : depends on how we represent each thing
21:04 : right here this ID let's see this ID
21:09 : will cost digit to be represented by a
21:11 : string this one as well so I think here
21:17 : he's saying it's just gonna join join
21:25 : all the data together where the first
21:28 : one is a string the second one I think
21:30 : might be in a raid oh oh oh we got 12
21:36 : now
21:41 : on second thought like the data
21:45 : conversion should probably be done at
21:47 : the number level because when you're
21:49 : concatenating digits it's it's more
21:54 : cumbersome to like convert to a number
21:57 : and then convert back into a string to
22:00 : concatenate them so in the digits phase
22:04 : let's just leave them in strings so each
22:06 : process concatenates them so I'll make
22:10 : it more clear what I mean here so let's
22:13 : say you have a string 1 & 2 and this guy
22:19 : gets matched as a digit and so there's
22:23 : this guy and then a digit digit gets
22:31 : promoted to digits here based on this
22:34 : rule here and then the both of them get
22:41 : combined based on this rule a digit plus
22:44 : a digit is also a digit
22:48 : digits so at at this stage you have a 1
22:54 : a string 1 a string 2 and and he at this
23:01 : stage you still have string 2 and at
23:04 : this at this step of the combination you
23:07 : should get combined string 1 and 2 to
23:13 : the string 1 2 to represent digits and
23:16 : then the plan is in the next step where
23:20 : a digits gets promoted to a number
23:25 : that's the point where we actually parse
23:28 : this string of numbers into a JavaScript
23:32 : number so we remove the quotes here
23:35 : using this conversion function number so
23:39 : that's the plan I think that makes more
23:42 : sense
23:43 : let's go for that and then when it's a
23:46 : decimal number we do the same thing
23:48 : except we at the decimal point in before
23:53 : the number conversion okay and now we
23:57 : have an array of numbers the numbers 12
24:01 : and 3 and that works okay
24:05 : and let's see it works for decimal
24:08 : numbers as well awesome now let's do
24:11 : strings strings might be a little heart
24:13 : and currently it looks like this which
24:15 : doesn't look like a string
24:16 : it looks like quote an array inside and
24:20 : then another quote so how do we do
24:23 : strings why tip tell us okay so so a
24:28 : string has been matched using this
24:31 : scheme here based on these three rules
24:34 : currently the first rule is a string is
24:38 : a double quote followed by some
24:40 : characters followed by another double
24:42 : quote and then what's a character or
24:44 : what's a characters plural a character
24:48 : can either just be one character or it
24:51 : could be a character followed by more
24:52 : characters so that's the recursion trick
24:55 : and then what's a character a character
24:57 : is any character that is not a double
25:01 : quote obviously there's problems with
25:03 : that such as this language cannot
25:06 : support having double quotes in strings
25:08 : but we'll we'll fix that in a separate
25:11 : episode it's over now we just cannot
25:14 : have double quotes inside of a string
25:17 : and that's fine and this ID is saying
25:21 : the thing that we're gonna devalue we're
25:24 : gonna use to represent this character is
25:26 : just whatever the string that has the
25:29 : character in it and then here let's
25:35 : figure out how we're gonna represent
25:37 : characters obviously strings so I'm
25:39 : gonna see string concatenation here yeah
25:43 : this is wrong this should be data at one
25:47 : so he's gonna have to fix this so
25:50 : because this you can look at this is an
25:54 : array and then this is index
25:57 : zero this is one so he wants to turn
26:00 : kept the first character to the next
26:03 : characters first characters in that zero
26:05 : but the next characters it should have
26:07 : been index one so he I think he messed
26:11 : up there yeah he gets this age undefined
26:17 : it should have been hollow but you get
26:20 : age undefined because you in index two
26:23 : of data is undefined so he fixes that
26:25 : cool has to regenerate the parser and
26:28 : now I get the string hello okay so now
26:34 : the parser should support all of these
26:37 : values now and it does very cool okay so
26:42 : that's where I want to stop in a future
26:49 : episode we'll keep going and we'll we'll
26:51 : talk about how to do white spaces and
26:54 : also how do how to parse strings
26:57 : correctly with with escape sequences to
27:02 : allow the inclusion of double quotes for
27:05 : example yeah see you next time

How to Make a Parser using Nearley.js - Part 2

Transcript