How to Make a Parser using Nearley.js

In this drive by code session we’ll show you what a context-free grammar is and how to use it and Nearley to build parsers. JSON is used as the example language we’ll build the parser for.

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : hello there welcome to a drive-by code
00:03 : session this time we're going to gonna
00:07 : talk about how to build a parser using
00:12 : nearly Jas and we'll talk about the
00:17 : different concepts dealing with building
00:20 : a parser so a grammar what what does it
00:26 : mean what what is a grandma in the
00:29 : context of building a parser and also
00:33 : practically speaking how to use the
00:36 : nearly grammar generator or not grammar
00:39 : parser generator tool to do that so
00:46 : we're going to be using JSON as the
00:49 : example we'll build a JSON parser
00:53 : basically probably not the whole thing
00:55 : due to that I want to keep the videos
00:58 : kind of short but we'll build part of it
01:02 : and perhaps leave the remaining pieces
01:05 : the undone parts as a homework
01:08 : assignment for you okay let's get
01:12 : started
01:13 : and as usual like it did these coding
01:18 : sessions beforehand and I'm going to be
01:20 : replaying what he did and explaining
01:23 : them so let's get into it so the first
01:27 : thing he does is NPM Annette - why which
01:31 : is a handy for you ought to know to get
01:35 : the project started that generates a
01:37 : package.json file oops I typed in the
01:42 : wrong place
01:45 : ok the next thing he does is installed a
01:49 : nearly parser generator tool and I guess
01:56 : the reason it's called a parser
01:58 : generator or I call it the parser
02:00 : generator is because it allows you to
02:03 : write a grammar in a in the nearly
02:08 : prescribed syntax and then
02:11 : they parser for you so you don't
02:13 : actually have to write the parser I'll
02:16 : show you how that works so so now you
02:20 : can see nearly is one of the
02:22 : dependencies in this project now the
02:25 : next thing we'll do it just start
02:27 : writing this file which is gonna has the
02:33 : any suffix which stands for nearly and
02:37 : this is a grammar file so this what we
02:42 : are writing here is a grandma and in
02:45 : computer science they might hear the
02:51 : term grandma associated with something
02:55 : called CFG which stands for context-free
03:04 : grammar so so when we're talking about
03:09 : grammar we're usually talking about
03:11 : context-free grammars and um which is a
03:19 : subset of grammars that are easier to
03:22 : make parsers for so we'll be using
03:25 : nearly to do that writing a grammar is
03:29 : relatively straightforward I hope you
03:33 : will find that to be true and near you
03:36 : will take that grammar that you write
03:38 : and generate a working parser in
03:42 : JavaScript for you so let's look at what
03:46 : the first version of this grammar is
03:48 : gonna all right so this it's the first
03:51 : version of this grammar and this guy
03:54 : here with written is called a production
03:57 : rule so production rule the production
04:05 : rule is defining a symbol the symbol is
04:09 : called digit so this defines what the
04:14 : digit symbol means in this language
04:18 : and it's saying a digit is defined to be
04:21 : a zero code this this arrow here I'm
04:28 : gonna say that means so this means
04:39 : define to be and then these vertical
04:47 : bars this just means or so there's an
04:50 : operator so it is it could be any one of
04:52 : those things is move on so now this is
04:58 : actually good enough as a grandma it's
05:02 : not very useful it just matches one
05:04 : single digit but let me show you how you
05:09 : compile a grammar do a JavaScript file
05:12 : and that's how so you used a nearly C
05:15 : tool which stands for nearly compiler C
05:19 : stands for compiler it compiles this
05:21 : JSON dot ini' file and it outputs a json
05:26 : dot JS file you can look into this JSON
05:29 : that GS file it's actually it's just a
05:34 : JavaScript representation of this
05:38 : grammar here written in this format in
05:42 : order to execute this or utilize this
05:45 : parser though you need to kind of
05:49 : bootstrap a little parser script and
05:52 : which I'll do here so this this is a
05:56 : template code or example code taken
05:59 : straight from the nearly getting started
06:01 : Docs so so why can't copy that and then
06:08 : he's gonna tweak a couple of things this
06:10 : needs to be referencing the JSON jst was
06:14 : just generated and then when we feed it
06:18 : something we want to feed it to
06:20 : something that this grandma can parse or
06:25 : this parser generated by the grand
06:27 : Martin Parr
06:28 : he's gonna put this parsing inside of a
06:32 : try-catch so that it outputs the error
06:35 : message more cleanly okay so I run this
06:43 : it takes the string that is fed into the
06:46 : parser which the parser was created or a
06:50 : new instance of this parser has created
06:53 : using this syntax here and then we feed
06:56 : a string into the parser and the output
07:01 : of the parser is a bunch of results
07:03 : which it can potentially have multiple
07:06 : results in the case of ambiguous
07:08 : grammars we're we're not gonna worry
07:12 : about that too much at this point
07:14 : so and in this case the there is only
07:18 : one result and that result is an array
07:21 : with a string one inside of it
07:24 : this guy inside the array that will end
07:28 : up or this the result of the parse this
07:33 : is the result of the parse and is often
07:40 : called the AST or abstract syntax tree
07:43 : but for now we're gonna not worry about
07:46 : that aspect either and just more
07:50 : concentrate on building the grammar
07:52 : all right let's keep going so now if we
07:55 : feed a string into the parser which it
07:58 : doesn't understand which ABC is an
08:01 : example of that it'll tell you that the
08:05 : church for a is unexpected instead I was
08:09 : expecting to see one of the following
08:11 : either a 0 a 1 or 2 all the way up until
08:15 : 9 based on this rule the digit rule that
08:20 : does the only rule that we have is
08:23 : expecting one of these characters
08:25 : basically so it doesn't recognize an a
08:28 : because it's not anywhere and a
08:32 : character is not defined to be matchable
08:35 : anywhere within this grammar and
08:37 : therefore it causes a
08:39 : index error let's keep going now we
08:48 : should be able to match multiple digits
08:49 : so at the moment it would not do that
08:56 : because this grammar only matches a
08:58 : single digit so we're gonna make it
09:02 : match multiple digits by using recursion
09:06 : um so this rule is called we're gonna
09:11 : define with this rule we're going to
09:12 : define the symbol digit and we're saying
09:17 : a digit can either be one single digit
09:19 : or it could be one single digit followed
09:21 : by more digits which can in turn be a
09:24 : digit so and this works by record them
09:30 : so let's say you had just one single
09:33 : digit well that can't be matched as a
09:37 : single digit so one basically gets
09:43 : resolved as a single digit but a single
09:46 : digit can be resolved as multiple digits
09:50 : and therefore a one can be resolved as
09:54 : multiple digits well what about the
09:58 : string 1 2 well the string 1 again is
10:03 : going to resolve to it digit just the
10:09 : character to also gets resolved as a
10:12 : digit no no how does this get a resolved
10:18 : as digits well this guy here this one
10:23 : digit will get resolved as digits
10:29 : and then based on the second rule one
10:32 : digit followed by another digits so
10:36 : these two together maybe use a different
10:39 : colors here these two guys together also
10:44 : becomes just a single digits
10:47 : our single digits that sounds very funny
10:50 : but yeah
10:51 : the combination of one digit and some
10:53 : more digits
10:54 : it is digits so that's how the character
10:59 : one two and if you can imagine if you
11:03 : add more characters here like three well
11:10 : let me actually have in front of it like
11:14 : here if it were you have mortgage
11:17 : another digit that becomes another digit
11:23 : which can get combined with this digits
11:26 : and you still have digits so that's how
11:30 : recursion works with grammars and this
11:33 : is what we're utilizing to match any
11:36 : number of a sequence of characters so
11:41 : okay so we updated this grammar to try
11:44 : to match multiple digits and now to do
11:49 : it and I'm gonna say in nearly I nearly
11:53 : always takes the topmost rule that or
11:57 : this symbol associated with the topmost
11:59 : rule as the thing to start matching the
12:05 : input on we're gonna make that explicit
12:08 : by saying hey the input and this input I
12:11 : guess we we chose to name it input with
12:15 : the name did anything we want it some
12:17 : some people like to call this start
12:19 : we're gonna call this input sorry about
12:24 : that
12:25 : so we're saying the input is consists of
12:29 : a bunch of digits basically and now that
12:31 : we've modified the grammar we're going
12:33 : to rerun the nearly C command but this
12:39 : time we're gonna put it in the school
12:42 : section with the package.json file to
12:45 : make that more convenient to run we're
12:49 : gonna call this come in gen parser so
12:51 : now this time we're gonna run npm run
12:55 : gen parser yeah npm run gen Parsa sorry
13:03 : did the output get a little messed up
13:05 : but me let me actually run it for you
13:09 : here NPM runs and parser so to show it
13:16 : how it actually looks so that's what it
13:18 : runs when you run npm run gen parser
13:20 : just switch back to replate terminal and
13:23 : now europe you can run the parse script
13:27 : again so it's able to match multiple
13:30 : digits okay so that's multiple digits
13:34 : we'll put some put a more emphatic
13:39 : output seeing the parse was successful
13:42 : versus the parse failed okay
13:46 : again if you give that input that it
13:52 : doesn't understand you know ABC it still
13:57 : doesn't understand it they will give you
14:00 : an error message alright let's keep
14:03 : going okay what about decimal points
14:08 : well let's make it match decimal points
14:10 : we'll say a number can be some digits
14:16 : followed by a dot and then some more
14:18 : digits but it could also just be some
14:22 : digits if that that number happens to be
14:25 : not be a decimal number with a decimal
14:28 : point so this should allow us to match
14:31 : numbers with decimal points in it
14:36 : ya know one sec so at this point so we
14:52 : have a number and we should be able to
14:55 : match numbers with decimal points I'm
14:59 : gonna try that actually
15:01 : so send the parser and so yeah so now
15:08 : it's the part is successful given a
15:12 : decimal number
15:13 : now there's our shortcut in nearly that
15:16 : we can utilize which is called the
15:18 : character class it's which works just
15:21 : like the character classes in regular
15:23 : expressions if you know those so if you
15:27 : have a set of different characters that
15:31 : you want to match you can use a
15:32 : character set or two character class I
15:35 : should say to represent that and that
15:38 : looks like this so this guy again is a
15:47 : character class and again it looks just
15:52 : like the read the character classes in
15:55 : regular expressions so if you already
15:58 : know that from regular expressions good
16:01 : for you
16:03 : and now the grammar looks a shorter more
16:06 : succinct and it works the same way so I
16:13 : think he's gonna test it out so yeah
16:15 : this is white get back to white like it
16:19 : does a gem parser and he parses so now
16:23 : this parse is successful for the 12 it
16:28 : should ok it still fails with ABC
16:33 : there's another trick you can use in
16:35 : nearly which is the plus sign which I
16:41 : think it's indeed something called the
16:44 : this is a syntax that also works in
16:47 : regular expressions
16:49 : but is actually a syntax stolen from
16:52 : something called EB and F and this plus
17:00 : sign means one or more one or more
17:05 : occurrences of whatever that is and you
17:09 : need this colon here to activate this
17:11 : plus sign so this is saying a digits is
17:15 : one or more digits and that you can
17:21 : think of that as the shorthand for for
17:26 : that recursion for this recursion trick
17:29 : that we use instead of doing that you
17:33 : could just do that and you you run this
17:36 : and it should work test before me see
17:45 : yeah and it actually internally nearly
17:49 : has generated an extra rule for you and
17:53 : actually see it so there's these two
17:58 : rules were generated internally by
18:01 : nearly based on based on this plus
18:06 : symbol here to support this plus symbol
18:09 : works which essentially does the
18:11 : recursion trick that we did manually in
18:14 : the previous step
18:16 : I kinda don't like the display output of
18:20 : this symbol it this symbol looks a
18:22 : little gnarly so maybe like switching
18:29 : back to the more explicit form it's
18:33 : nicer in terms of the error output okay
18:36 : so now we got things we've got numbers
18:41 : working what's another thing we need to
18:43 : get working so we got numbers let's get
18:48 : boolean sorting so how do you get boy in
18:50 : the world let's define boolean so a
18:54 : boolean can either beat the the string
18:58 : literal true or the string literal false
19:01 : and so we run the parser again we'll see
19:06 : that the parsers is able to parse the
19:11 : word true as well as false now par
19:16 : success now if you if you give it a word
19:21 : that it doesn't understand like hello
19:23 : it's gonna barf at you and it'll kind of
19:26 : tell you what it's thinking at the point
19:32 : that it got confused during the parse so
19:35 : it says there's a syntax error and
19:37 : unexpected age visually it got confused
19:40 : when it saw this first letter age
19:44 : because instead of 1/8 the parser was
19:48 : expecting to see one of the following 80
19:51 : based on this rule that is trying to
19:54 : match the word true so nearly also
19:57 : generated this rule that was based on
20:01 : this string of characters TR UE and
20:06 : again you can see from this generated
20:09 : grammar here that in order to match
20:13 : whenever you write a string literal that
20:16 : has multiple characters in it nearly
20:18 : actually generates a rule that matches
20:22 : multiple character literals one after
20:27 : another and you can see that in this
20:29 : output here it's expecting either a true
20:32 : to match the word true the word false or
20:36 : a character matching this character
20:40 : class like a character between 0 and 9
20:43 : so it's cool to understand the internals
20:47 : of the of nearly so that's one way you
20:51 : can get insight into it by looking at
20:54 : the error messages so we got boolean
20:57 : working now let's get nulls to work so
21:01 : our JSON JSON format supports you know
21:06 : numbers strings boolean's nulls a raisin
21:11 : chicks so I know is just the string no
21:18 : so let's test that out parse so we gonna
21:25 : feed it word no but why doesn't it work
21:30 : I see unexpected n instead I was
21:34 : expecting to see one of the following
21:36 : true tea for true F for false
21:40 : let's see anything referencing this null
21:45 : string literal and the reason why is
21:50 : this no is actually a special word in
21:55 : nearly so this guy doesn't work out and
21:58 : trying to redefine it also doesn't work
22:00 : the word no in the nearly language
22:04 : actually means the absence of a match so
22:09 : like this should match the empty string
22:11 : so in order to fix it for our situation
22:15 : we're gonna have to name this symbol
22:17 : something other than the word know so
22:20 : maybe we'll say like underscore or
22:23 : dollar no let's go a dollar now so oh I
22:30 : think I think white kid actually called
22:33 : it mine oh okay I'll follow his what he
22:37 : did here so what it says rename it to
22:39 : mine and now no is able to be part so
22:44 : watch out for that if you're using the
22:47 : early you can't use the word no perhaps
22:51 : they should give a little better message
22:53 : indication add error message indication
22:55 : for that when you're trying to use it
22:57 : okay now strings let's try to match
23:01 : strings so string what how do you define
23:04 : a string a string is a single a double
23:09 : quote in some characters and then
23:12 : another double call and to match the
23:16 : characters again we'll use this
23:17 : recursion trick to match one or more
23:20 : character so their characters can either
23:24 : be one character
23:25 : or a character and then more care person
23:27 : and then what's a character a character
23:30 : we're gonna use the character class
23:33 : syntax to match a single character so
23:38 : this is saying this is a character class
23:41 : here and this caret here that means not
23:50 : or does not match so it and and this guy
24:02 : here that is a double quote and it oops
24:08 : this this is a double quote and in
24:14 : nearly a double quote must be escaped
24:16 : with this slash so basically this
24:19 : character class here based on that this
24:23 : character class matches any character
24:32 : that is not a double quote okay this so
24:42 : character is any character that's not a
24:44 : double quote um there's gonna be
24:47 : exceptions to this know the bully with
24:49 : the escape characters we'll deal with
24:53 : that later that gets slightly
24:56 : complicated and we'll skip that for now
24:59 : but this is a like a simple basic way of
25:05 : representing strings error message
25:10 : coming out of nearly it doesn't like
25:11 : this single quote for representing
25:14 : strings I think so we're gonna fix it by
25:17 : using double quotes but escaping the
25:21 : double quote within dumb and let's see
25:24 : if that works okay so I'm gonna try to
25:30 : match the ABC the string ABC
25:35 : and does work cool so that there we have
25:41 : it that is strings what about a race
25:45 : okay so a race and we'll actually rename
25:53 : the input symbol to value symbol which
25:56 : to allow us to use the values within an
26:00 : array because we have a writ match or
26:02 : race with matches or match values within
26:05 : an array so we'll say the input is a
26:09 : value but an array can be well array
26:13 : starts with the Open bracket closes with
26:16 : the closed bracket and then within an
26:19 : array there's array items and then array
26:22 : items can be either one value which
26:29 : recursos back to here so because we can
26:32 : have an array of any of these things
26:35 : array of numbers array of boolean or a
26:37 : mixture of those various things array
26:41 : that has an all in it stringing it even
26:43 : an array of a race right so an array
26:46 : item can be value in which case it would
26:51 : just be an array with one value in it or
26:55 : or it can be a value then a comma
26:59 : followed by a comma and then more array
27:01 : items so let's generate the parser again
27:05 : and now we'll try to match an array and
27:13 : it works let's try an array with a
27:17 : number in it this time that also works
27:20 : array with two numbers that work also
27:24 : works but an enum and I write an empty
27:26 : array doesn't work with this and
27:30 : you look at the error
27:33 : she try to understand what's going on
27:35 : it's saying well I expect it it got
27:39 : confused when it saw the closing bracket
27:42 : because instead of that is expecting
27:45 : either this double quote about this is a
27:49 : gnarly representation of a double quote
27:51 : but it is a double quote based on if if
27:55 : it happens to be a string here you can
27:58 : kind of follow the train of thought of
28:01 : the parser here the parser is saying I
28:04 : try to match an input then what if the
28:09 : value is an array well then the array is
28:13 : gonna start with a Open bracket which it
28:16 : did fine which is what a lot whoops
28:19 : would allow it to advance this read
28:22 : cursor here to after this
28:25 : open brackets and then now it's trying
28:29 : to match array items it's an array item
28:31 : array items is a single value and a
28:34 : single value could be a string so the
28:36 : parser saying if the value in the array
28:38 : was a string then I'm looking for a
28:42 : double quote here but there's another
28:44 : possibility well if the value inside the
28:47 : array is another array then I'm looking
28:49 : for an Open bracket what if the value is
28:52 : a boolean it and it is the true as this
28:56 : is the true literal then I'm looking for
28:59 : a tee all these possibilities and for no
29:03 : and a character matching a digit if the
29:08 : item was number but none of it allows
29:14 : for if allows for an empty array
29:18 : basically see looking back at the
29:22 : grammar here it's true that this grammar
29:27 : doesn't allow for empty arrays because
29:29 : an array items has to be at least a
29:33 : single value which has to be one of
29:36 : these things there's nothing that allows
29:39 : it the
29:41 : the array items to be nothing so with
29:50 : that um for you the viewer if you want
29:54 : to try to figure out a solution for that
29:56 : I like to post this challenge to you so
30:00 : if you like to take a few moments to
30:03 : figure out the solution for this how can
30:06 : we make this grammar match an empty
30:09 : array you can pause the video to take a
30:13 : bit of time to do that if you want while
30:16 : you're doing that I'll give you a couple
30:17 : of seconds okay so if you decided to do
30:23 : that
30:23 : congratulations yeah I hope you got the
30:27 : right answer
30:29 : so if you said I'm gonna review the
30:33 : answer right now so if you said just at
30:36 : the possibility of not remember we
30:38 : talked about know how no is a special
30:40 : keyword in the nearly grammar okay
30:43 : actually use null here so if we said
30:45 : it's possible for this array items to be
30:49 : known then that actually allows for the
30:54 : stuff the stuff inside between the
30:58 : brackets to be simply an empty string
31:00 : let's try that did we forget to yeah he
31:17 : probably forgot to generate okay alright
31:20 : he just forgot to generate the parcel so
31:22 : that works we're able to parse parse on
31:27 : empty array now however there's a
31:29 : secondary problem with this approach
31:33 : which is that now it allows for trailing
31:40 : commas so let's see that so yeah so yeah
31:46 : a trailing comma is able to be matched
31:48 : why is the trailing comma able to be
31:51 : matched because after
31:54 : so if you have this one two three
32:00 : actually let me do fewer just one two
32:04 : and then a trailing comma this trailing
32:07 : comma is gonna match with this one and
32:10 : then the array items after that could be
32:14 : a null so there could be this empty
32:17 : string after this trailing comma which
32:22 : does get matched as array items so how
32:27 : can we change this grammar to eliminate
32:32 : the possibility of matching a trailing
32:35 : comma and visually we want to make we
32:38 : make the trailing comma invalid and only
32:41 : this valid I'll if you want I'll let you
32:45 : take another moment to think about it
32:47 : again I'll give you a couple of seconds
32:52 : okay if you if you decided to do it
32:56 : congratulations
32:57 : you made good use of your of your brain
33:01 : cells but if you just want to enjoy the
33:06 : show
33:07 : the answer is remove null from the
33:13 : possibilities of matching an array items
33:16 : and instead make the conditional on the
33:22 : array allow the array to be simply an
33:26 : open bracket or and then followed by a
33:29 : closed bracket so this is the grammar
33:32 : that will basically parse a race
33:36 : correctly based on the JSON
33:40 : specification so now with a trailing
33:43 : comma the parser gives you an error
33:46 : let's read this error so so it's
33:51 : actually confused when it sees the
33:53 : closing bracket when I sees because it
33:57 : is the comma is still correct after the
34:00 : comma is just expecting another value so
34:03 : and it tells you that it says
34:07 : I'm not expecting the closing bracket of
34:11 : the array instead I was expecting a
34:13 : double quote for a string maybe a string
34:17 : is coming next after the comma or if the
34:22 : next value in the array is a nested
34:24 : array I could see a Open bracket or if
34:28 : it were or this it could be an MD empty
34:34 : array nested empty array inside this
34:36 : array based on this rule where the where
34:40 : the array is just an open bracket
34:43 : followed by a closing bracket or it
34:45 : could be a tee based on a true literal
34:48 : or it could be F based on the false
34:51 : literal and so on and so on and so on
34:53 : so now after we modify this grammar
34:56 : trailing commas are no longer allowed
34:59 : and and that's pretty cool but if you
35:04 : get rid of the trailing comma then it
35:07 : should parsed correctly let me see if
35:10 : that's true yeah they're processed
35:11 : correctly so um that's that's this where
35:17 : I want to stop here um so so far we
35:20 : covered how the parse numbers boolean's
35:25 : nulls strings and arrays we haven't done
35:30 : the entire JSON I originally may do that
35:32 : in the future or just go more into how
35:37 : to use merely in general I plan to like
35:43 : it and I we plan to produce more content
35:46 : based on nearly and making parsers so I
35:50 : hope that you stay tuned thank you for
35:53 : watching

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

Transcript