Generating Friendly Parser Errors with Earley Algorithm

In this video, a follow up to the introductory video on the Earley Parsing Algorithm, I explain how Nearley.js produces user-friendly error messages whenever a parser error is encountered.

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : hello there are in this video I'm going
00:02 : to talk about how you can't with the
00:05 : early parsing algorithm it's possible to
00:09 : build a parser that gives you
00:12 : user-friendly error messages user in the
00:15 : case when there is a syntax error so
00:18 : this video is going to build on top of
00:21 : the video that I made that introduces
00:24 : the early parsing algorithm so if you
00:27 : like to get an introduction to that I
00:29 : would recommend that you find that video
00:32 : and watch it first one of the things I
00:36 : said in video is that with early one of
00:40 : the advantages of the early parsing
00:42 : algorithm is that it makes it possible
00:44 : to straightforwardly give very user
00:50 : friendly error reporting and this is
00:53 : actually one of the reasons that I got
00:55 : interested in the early parsing
00:58 : algorithm I actually had studied several
01:01 : several different parsing algorithms and
01:04 : parser generators and I liked nearly j/s
01:08 : in particular because it used the early
01:11 : algorithm which I studied and I realized
01:15 : this was the one that allowed me to
01:20 : straightforwardly implement user
01:22 : friendly error error messages and so a
01:27 : while back
01:29 : this was July of 2019
01:32 : I wrote up I first sent an email to the
01:37 : creator of nearly Jes asking him would
01:41 : he be interested in a feature like this
01:45 : where if the user of the parser and the
01:52 : parser would be the front end to either
01:54 : a programming language or some sort of
01:57 : parser it could be a JSON parser or
01:59 : whatnot when there is a syntax error or
02:03 : a parse error you would be able to show
02:07 : the user essentially what the parser is
02:10 : thinking at the
02:11 : I'm that it encounter an error so this
02:17 : is the example that I gave if you got
02:20 : this input of JSON which is erroneous
02:25 : the the early parser would actually be
02:29 : able to tell you what it's thinking so
02:31 : it's in this case it says instead of a
02:34 : string this one which is a string token
02:42 : instead of a string token the parser was
02:45 : actually expecting to see either a
02:48 : closing curly bracket or a comma and it
02:54 : actually explains why it thinks that it
02:59 : expects a closing curly bracket because
03:02 : it was in the process of matching an
03:06 : object as first a Open bracket and then
03:12 : a list of object entries and then it's
03:15 : at the point where it's expecting a
03:17 : closing curly bracket and why is it in
03:22 : like how did it get two dips this point
03:25 : well is from this previous rule where it
03:27 : was matching an object and then and then
03:32 : that in turn was from this previous rule
03:34 : whereas matching and array items and
03:41 : then which in turn was from this rule
03:45 : where in we're basically inside a series
03:51 : of array items which basically here this
03:54 : opening square bracket that started from
03:57 : here and you can actually see the tokens
03:59 : that were matched like this one was
04:03 : based on here
04:05 : this object entry list is actually
04:08 : currently being matched and we're seeing
04:14 : we're in the middle of this object here
04:16 : and this opening curly bracket is here
04:22 : and it's actually has matched
04:25 : these guys and we have currently
04:29 : once you've matched name : Marty age : 8
04:34 : we're actually have a complete object
04:37 : entry list and a closing bracket would
04:40 : close out the object and so it's
04:45 : expecting a closing curly bracket to
04:49 : close out this object here and it's also
04:52 : expecting a comma because a comma would
04:56 : allow you to add another key value entry
05:00 : to this object and the hope is that upon
05:04 : seeing this explanation of what the
05:06 : parser is thinking the user was able to
05:10 : realize his mistake in this case the
05:12 : fact that he forgot a comma okay so
05:16 : that's the error reporting and this is a
05:20 : feature that I asked the trader of
05:23 : nearly je s whether he would be
05:25 : interested he said he would and it
05:28 : resulted in this pull request which made
05:30 : it into nearly je s so if you check out
05:32 : the latest version of nearly je s you
05:35 : would get this error reporting and I'm
05:40 : gonna show you now how that algorithm or
05:44 : how that error reporting actually works
05:47 : so let's go back to the the example I
05:52 : showed in the first video where we use
05:55 : this grammar again it's very simple
05:59 : grammar which can match addition
06:03 : operations and and we compile this
06:08 : grammar last time into JavaScript so if
06:11 : we want to test a an input with this
06:14 : grammar and we just have to do this npx
06:19 : nearly test the name of the
06:24 : javascript grammar file and then - i and
06:29 : then i can put in an input last time we
06:31 : tested the input one plus one and that
06:34 : gave us this table this parsing table or
06:37 : the parsing chart a to refresh my memory
06:40 : the chart at index zero means this is
06:43 : the set of rules or set of states I more
06:49 : correctly but the states are sort of
06:51 : like these stateful rules that have a
06:55 : progress namely this dot right this is a
06:58 : cursor and basically at the zeroth state
07:04 : you set up these rules to start start
07:08 : progressing and as your matching tokens
07:13 : from the input you're going to try to
07:15 : move these dots up within the rule to to
07:19 : sort of advance these the progress of
07:23 : each individual rule and we already did
07:26 : this whole thing by hand so I'm not
07:28 : going to repeat that but basically this
07:31 : the 0th column is when no inputs have
07:35 : been read the first column is when we've
07:38 : read the first input in this case the
07:43 : string one and this the second column is
07:46 : when we're reading the plus symbol and
07:49 : the third column is when we're reading
07:51 : the second one symbol like that okay now
07:58 : what if we put in some wrong input such
08:01 : as instead of one plus one we're going
08:04 : to put in one plus n which at the moment
08:12 : that's not possible in this grammar
08:14 : because it just doesn't allow for
08:18 : alphabet letters so if we did that then
08:22 : this one would get crossed out and we'll
08:25 : get an letter n instead and this become
08:31 : invalid okay and so at this point when
08:36 : when the parser gets this input n what
08:40 : is it going to try to do it's gonna try
08:42 : to look at the rules in the previous
08:46 : column to try to find a match a rule
08:49 : where the next thing that's coming which
08:53 : is like to think the the thing to the
08:56 : right of the dot matches the input and
08:59 : in this case we're going to look through
09:01 : each one so this and it's only gonna try
09:04 : for the ones where the thing to the
09:06 : right of the dot is a terminal symbol
09:08 : term is not a terminal symbol it's a
09:11 : non-terminal symbol so it's not gonna
09:15 : try that and number is not a terminal
09:17 : symbol either so the only thing that is
09:19 : a terminal symbol is that which says it
09:22 : needs to be a digit and that's not gonna
09:25 : match the n and for that reason it the
09:29 : parser needs to fail here because
09:31 : there's no rule that allows a character
09:35 : n so then what does the parser do well
09:39 : the the error reporting scheme and I've
09:43 : shown you what it actually does is
09:46 : instead of trying to trying to sort of
09:52 : explain why n it's not allowed it
09:56 : actually shows you all the things that
09:58 : it thinks should be allowed next so all
10:01 : the things that it's expecting so what
10:05 : are the oops so what are the possible
10:09 : all the possible characters that the
10:11 : parts are expecting well we just need to
10:14 : iterate through these rules and find
10:16 : other rules where the next thing coming
10:20 : after the dot is a terminal symbol and
10:23 : that is the third row here so given this
10:30 : we can say I'm not I'm not expecting the
10:40 : character n
10:42 : instead I was expecting the character
10:52 : well not care but the character class a
10:57 : character matching zero the character
11:07 : within zero and nine okay and then so
11:13 : and then the parser is actually going to
11:16 : try to explain how it got this answer
11:19 : and the way it's gonna do that is by
11:22 : trying to just first show you this rule
11:25 : so it'll show you this rule it can
11:33 : actually render the dot first it
11:36 : displays this rule but then it actually
11:39 : wants to show you how this rule how we
11:43 : got to this rule in the first place and
11:45 : that would be the rule coming before
11:49 : this rule that generated the rule that
11:53 : needs to match a number and if the dot
11:56 : is at the very beginning the way to do
12:00 : that is to just search within this same
12:05 : column tell them to for a rule where
12:09 : it's waiting for a number and in this
12:13 : column there are two of them I'm gonna
12:16 : go with a different color so you can see
12:18 : so there are two of them this one and
12:20 : this one they're both looking for a
12:23 : number next and the error reporter will
12:27 : just pick one of them instead of trying
12:29 : all the possible different combination
12:32 : it will just pick one of them it doesn't
12:35 : actually care so let's pick the shorter
12:38 : one of the two
12:39 : so it'll right turn
12:46 : like that so essentially what this does
12:48 : is explains that well where we're trying
12:52 : to match a number because we were trying
12:54 : to match a term and a term was
12:57 : determined to be it to be a single
13:01 : number although there are a couple of
13:04 : possible solutions to that but we chose
13:07 : the one where a term expands to a single
13:10 : number and then but it keeps doing that
13:13 : so how do we arrive at term it does the
13:17 : same thing it does the same thing it
13:18 : looks in the same column because the dot
13:20 : is at the beginning of this rule
13:23 : it looks again in the same column for a
13:27 : rule where the next thing that's
13:30 : expected is turn the thing on the left
13:33 : hand side and it finds it here this time
13:37 : this is the first entry it finds it here
13:42 : so we'll pop it down here and this is
13:51 : the recursive entry where a term wants
13:57 : another term within it and this is
14:00 : coming from index 0 this time so so in
14:05 : this case that that is no longer at the
14:07 : very beginning of this rule and when
14:09 : that's the case we know that this rule
14:13 : actually originated in a earlier column
14:17 : of the table from which column we can
14:20 : find out from this from index from index
14:24 : brings us to the 0th column of the table
14:28 : and that's where we're gonna start to
14:30 : search now we're within the 0th column
14:32 : do we have this same rule starting and
14:37 : the answer is that one so this one is
14:41 : the one that matches but we're actually
14:44 : not even going to copy that over because
14:48 : this is the same rule so I think this is
14:51 : this is done like if we had copy that
14:54 : over it just looked like the redundant
14:58 : three and here like that and I think
15:06 : that's not super useful to to the users
15:09 : so we're just gonna leave that at that
15:12 : okay so so that's a very simple very
15:14 : short example of what the error reporter
15:18 : is doing and this is what the error
15:21 : message actually looks like if we gave
15:24 : 2d to the parser this erroneous input as
15:28 : another example I have example to where
15:34 : this grammar can match terms more
15:39 : complex terms inside of apprentices due
15:43 : to this rule here so it can match things
15:45 : like this for example so let's let's try
15:53 : go to the command line and try to parse
15:57 : something like this can I use the
16:01 : example to grammar at this time oh I
16:04 : think this I should come second so it
16:09 : can parse something like this and this
16:14 : is the chart and it is a substantially
16:16 : larger chart than the other one because
16:18 : it's more complicated and that makes
16:20 : sense now what if we had messed up the
16:24 : input so let's see if we if we say put a
16:29 : letter in here what happened well it's
16:33 : gonna tell you that character n is
16:36 : unexpected is that I was expecting to
16:38 : see one of the following it could have
16:42 : taken a open parenthesis here so instead
16:49 : of an N maybe you remember it hasn't
16:53 : seen anything it could have taken
16:55 : another open parenthesis to maybe at yet
17:00 : another group here like that so that's a
17:04 : possibility and it'll explain why
17:09 : that's possible because we're in the
17:12 : middle of matching an underneath here so
17:16 : like a nunnery is expecting at this
17:20 : position and maybe an honoree is a
17:24 : parenthesis and then another trunk and
17:26 : then a closed parenthesis where did it
17:28 : get the idea of trying to match an under
17:31 : a well it was trying to match a term and
17:33 : a term can be under a and then the plus
17:36 : and then a term now where did it get the
17:39 : idea of matching a turn well it was
17:41 : trying to match a time here it was
17:44 : trying to match it on here because it is
17:46 : in the middle of this one you can see
17:49 : the dot here the dot here it was
17:54 : actually in the middle here right after
17:57 : having matched this plus sign you can
17:59 : see this plus sign has been consumed
18:01 : it's coming after the dot so after it
18:05 : has seen an innate and then a plus sign
18:07 : the next thing it wants to match is a
18:09 : term that's how we got that's how we got
18:12 : to the point where I want it to match
18:14 : this term so that's one possibility
18:17 : another possibility is it we want to
18:20 : match a digit a character matching the
18:23 : character card class between zero and
18:26 : nine and then and then again it explains
18:30 : how why it thinks that now if we if we
18:35 : go back to the version of the input that
18:38 : actually worked and we review the the
18:42 : parsing table we can actually see why we
18:46 : got those two expected characters
18:48 : because we can count how many input
18:51 : characters we're in at the point where
18:54 : an error occurred right so so because
18:58 : what we did to change change this info
19:01 : was we changed a three to an N okay so
19:05 : and the one is at index 1 the plus is
19:12 : index to the open paren is index 3 the 2
19:16 : is index 4 and that the plus is index 5
19:19 : so the time where we encounter
19:22 : we should have had the fifth column here
19:28 : ready to go by the time we encountered N
19:31 : and of course the other entry we're
19:34 : gonna ignore because we're looking at an
19:37 : alternate history at this point so when
19:40 : we're getting in basically what the
19:45 : parser is gonna do is search in the
19:47 : previous column in this column column
19:50 : five for other rules that could possibly
19:53 : match the input n and again it couldn't
19:56 : find any but the only rules were it was
19:59 : looking for a terminal symbol were this
20:04 : one and this one so one of them is
20:09 : trying to match a left friend the other
20:11 : one is trying to metric digit such the
20:14 : two possible expected characters in the
20:17 : resulting output okay so I'm going to
20:20 : wrap this video up here I hope this
20:22 : explanation of how the error reporting
20:25 : works in nearly Jas made sense enough if
20:30 : you're a user of nearly Jas and you're
20:34 : reading these error output we would like
20:38 : your feedback send me a youtube comment
20:40 : or something or or anything reach out to
20:44 : me or Karthik because we do have an
20:49 : interest in making the user error
20:53 : messages helpful so your feedback would
20:58 : would help our job in doing that that's
21:02 : all I've got for you thank you for
21:03 : watching