Moo.js Tokenizer with Nearley.js

In this video I’ll introduce how to use the Moo.js lexer/tokenizer with Nearley.js. A lexer is a processing step commonly used to process the input string before the parser. It helps increase the performance of the parser, and as in the case of Moo.js, it also allows the parser to report errors with line number information.

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : hello there we're going to continue with
00:02 : the how to make a programming language
00:03 : series we're going to get back to nearly
00:07 : Jas this episode is going to talk about
00:11 : a specific feature of nearly Jas which
00:14 : allows you to plug in a custom custom
00:18 : tokenizer
00:19 : which is sometimes also called a lexer
00:23 : and this is their page which explains
00:28 : how to do that though tokenizer z' aka
00:32 : lectures you I mentioned the name
00:38 : lectures even though they say tokenizer
00:40 : z' in the documentation because you
00:42 : might hear the term lecture from other
00:47 : other sources that you're researching
00:51 : actually it does use the word lexical
00:54 : information here so I'm just gonna use
00:58 : these two words interchangeably and you
01:01 : should understand them as such now what
01:04 : is ste tokenizer so a tokenizer is a
01:09 : program that takes your string input
01:12 : let's say this was your program oh I
01:15 : have the double quotes here and on the
01:17 : inside let's forget that happen so this
01:20 : is your string input and and we're gonna
01:26 : write a parser to to make sense of this
01:30 : program currently we are where we're
01:36 : just having the parser look at every
01:39 : every character of this string one after
01:43 : another so for example in nearly Jas if
01:46 : you wrote the string literal if then
01:52 : it'll basically if if it's looking at
01:55 : this part of the string at the moment
01:57 : you know it'll basically do a match
01:59 : between what is at the current location
02:03 : of the parser and and the rule is trying
02:08 : to define it all had to match it up and
02:10 : and sort of
02:12 : come up with the matches directly in
02:15 : string.format
02:16 : that's okay however it's not quite as
02:20 : efficient as it could be and
02:22 : traditionally people who were making
02:26 : parsers they actually use a two-phase
02:31 : process so the input before getting into
02:35 : the parser would actually go through a
02:40 : box called the lexer aka tokenizer and
02:45 : then the input out of the lexer would be
02:49 : a stream of tokens and then the token
02:52 : stream in turn would get handed off to
02:56 : the parser so thus far we've sort of
03:00 : omitted the lexer part but in this
03:04 : episode we're gonna bring it back and
03:06 : the reason we're gonna bring it back is
03:10 : because it helps mostly because it helps
03:14 : with the performance of the parser
03:17 : there's a few other benefits of using a
03:21 : luxr which I will cover but before that
03:24 : I'm gonna perhaps paint a bit a slightly
03:28 : better picture of what a lexer does what
03:31 : the lexer does is Goethe goes through
03:33 : this input stream one character at a
03:37 : time and it's gonna chop it up into
03:41 : these things called
03:43 : tokens which are just bits of this
03:45 : string but with a little additional
03:47 : lexical information in them so basically
03:51 : out from this string we would get
03:53 : something like a token for the if
03:56 : keyword another token for the left paren
04:02 : and another one for the and etc etc but
04:08 : each one of these are not simply strings
04:11 : because each one of these are actually
04:14 : tokens they contain additional
04:17 : information such as the line number
04:23 : even column number and look what type of
04:29 : thing is which is in this case it's a
04:34 : it's a keyword it if the if word is a
04:38 : keyword and in this and for the left
04:43 : paren you you also get a line number
04:45 : column number and the type of this might
04:48 : just be called left printing and so
04:51 : forth
04:51 : so contain within each of these tokens
04:54 : is some additional metadata about each
04:58 : bit of string which the parser can then
05:02 : actually make good use of and because
05:05 : these strings have been chopped
05:07 : such as like these these this identifier
05:11 : print has been chunked into one one
05:15 : piece the parser doesn't have to deal
05:18 : with the individual characters and that
05:20 : is also one reason why they're this
05:23 : helps with the parsing performance okay
05:26 : so that is the lecture that is the what
05:29 : the lecture is conceptually and now
05:32 : let's look at an actual lecture one
05:35 : thing that nearly Jes helps us with here
05:39 : is it actually recommends a
05:43 : implementation implementation of a lexer
05:45 : so that you don't even have to write
05:47 : your own lecture you only have to
05:49 : configure the lecture not write at
05:51 : yourself and the one that it recommends
05:54 : is called mu which is also written in
05:56 : JavaScript with which you can configure
06:02 : a lexer very easily using syntax like
06:06 : this whenever you're learning something
06:08 : new and it's integrated with another
06:12 : thing I feel like it's harder to get at
06:14 : the heart of what something yes so what
06:16 : I'm gonna do first is actually take this
06:19 : mu library by itself and play around
06:22 : with it and show you how it works and
06:25 : then after that we're gonna integrate it
06:27 : with nearly J gasp so let's go ahead and
06:30 : do that
06:30 : the first thing I'm gonna do is take
06:32 : this initial code example that
06:35 : jas I love the theme of this project by
06:41 : the way we should probably npm install
06:43 : UJS there it is
06:46 : and then we're going to make a new
06:49 : javascript file I'm gonna call it mood
06:52 : play and then we're gonna drop this code
06:54 : example directly from their readme page
06:58 : in here so this first part of this
07:02 : example configures a lexer I'll talk
07:07 : about what these things mean and now
07:09 : once you have a instance of the lexer
07:11 : which is what that guy is you can call
07:13 : lecture reset and give it a string and
07:18 : this would be your input string okay so
07:23 : this this line passes this input string
07:28 : while 10 cows move to the lexer and then
07:33 : after that what you do with the lecture
07:36 : is you call it dot next on it and each
07:38 : time you call dot Knicks the next method
07:40 : will return you a token which is an
07:43 : object basically and it should look
07:46 : something like this let's try this that
07:50 : didn't do anything because we didn't
07:51 : actually consult that log the return
07:54 : value of that next so let's try that
07:57 : again
07:57 : so now you can see we have printed to
08:03 : the screen four objects each one is a
08:07 : representation of the token and each one
08:10 : has a type so the type the type of the
08:13 : first one this wild word is a keyword so
08:18 : and you can also see that there's line
08:21 : number information so there's a line
08:23 : number and a column number the line
08:25 : breaks I believe is telling you how many
08:28 : how many line breaks are within this
08:31 : piece of string which for this one
08:34 : there's zero offset is the character
08:39 : offset from the very beginning of the
08:41 : input so in this case is zero but for
08:44 : the next one that's five because the
08:48 : ws stands for a whitespace and I'll show
08:52 : you where these types are coming from
08:53 : well basically they're coming from this
08:55 : configuration object and you can see the
09:00 : offset of this white space from the
09:03 : beginning is five here because of this
09:06 : while word and now at this point you can
09:10 : probably connect the dots and realize
09:12 : that the type of each token is
09:16 : determined by this key of this
09:19 : dictionary in this configuration
09:22 : dictionary so and on the right-hand side
09:28 : of each one of these key value pairs is
09:32 : either a regular expression like that or
09:38 : a array like that which is it's sort of
09:43 : like a regular expression that ORS
09:45 : each one of these together so you
09:48 : perhaps you could have written that
09:50 : eternally like that as a regular
09:55 : expression if you wished there's some
09:57 : additional syntax if you need more
10:00 : configuration options for each one of
10:03 : these so in so whenever you need more
10:06 : configuration options in this case they
10:09 : need it for line breaks so basically the
10:11 : documentation of MU says whenever you're
10:14 : planning to match line breaks with one
10:18 : of these natural rules you have to set
10:21 : line breaks too true to tell it that you
10:24 : are intending to match line breaks and
10:26 : this is a case when that is so whenever
10:29 : you do that you need to expand this
10:33 : value to an object put the matter in
10:37 : here key by the word match and then add
10:41 : the additional options there so that's
10:46 : basically that let me show you a
10:50 : slightly simpler example this time I'm
10:53 : gonna use the example from here from the
10:56 : nearly Jas page I'm just gonna
10:59 : copy this and we overwrite this previous
11:07 : example and the input I'm gonna give it
11:12 : is I have three cows looking at this
11:16 : configuration I can see that it matches
11:19 : numbers it matches words which are any
11:25 : number of characters between a and Z
11:27 : lowercase there's also a times I'm gonna
11:33 : ignore that one so I'm just gonna write
11:35 : the sentence I have three cows and I'm
11:37 : gonna expect it's a number and three
11:39 : words and some white spaces perhaps and
11:44 : actually what you can do with the lexer
11:48 : is you can keep asking for tokens by
11:51 : calling next until next returns a
11:56 : undefined or a no I don't know which one
11:58 : and then that's what signals the end of
12:01 : the token stream okay so right at this I
12:04 : ran that so now we get to see all of the
12:07 : tokens so this looks like what I
12:11 : expected so first I have a word I then a
12:14 : white space that's this one here and
12:18 : then I have a word half white space and
12:21 : then I have a number three and that
12:23 : white space and then a word cows okay
12:27 : it's how the lexer aka tokenizer works
12:31 : more or less Moo has actually quite a
12:35 : bit of features and I'm not gonna cover
12:37 : all of them but I do want to cover one
12:40 : of them which is the value transform
12:43 : which they documented here so as you can
12:47 : see each one of these token objects has
12:50 : both a text and I value the text
12:53 : represents the exact string that was
12:56 : matched that represents this token then
13:00 : the value is normally the exact same
13:02 : value as text unless you decide to
13:06 : transform it to something else and the
13:08 : way you can do that is by using a
13:10 : you transformer so you can basically say
13:13 : I actually four numbers for example
13:16 : that's a perfect candidate for numbers I
13:19 : actually want to represent the value of
13:21 : the number token as the actual numeric
13:24 : value of that number so the way you
13:26 : would do that is first take this match
13:29 : right here
13:30 : and wrap it inside this object and put
13:36 : it inside the property named match and
13:40 : then the value transformer should be
13:43 : named value and then the value of value
13:48 : haha the value of value should be a
13:50 : function that takes a string and returns
13:53 : something and in this case number so
13:56 : this this number function conveniently
13:59 : will parse a string that presumably is a
14:02 : number so yeah so if we had done that
14:06 : then this number token here this number
14:09 : token here its value will become become
14:12 : an actual JavaScript number let's see
14:16 : that happening yeah and there it is so
14:23 : this is number token has the value of 3
14:27 : which is no longer quoted which tells me
14:31 : that it's actually a number so now the
14:34 : next step is actually going to convert
14:40 : this arithmetic example that we have
14:44 : that which we've been walking through in
14:47 : the previous episodes I'm gonna convert
14:49 : that to use a tokenizer and previously
14:54 : the nearly parser was written in a way
15:00 : using either regular expression matters
15:04 : or string literal mattress like that
15:08 : okay and now we're gonna instead have
15:12 : this parser plug in this lecture into it
15:17 : and then whenever a mattress like this
15:21 : are written its
15:23 : actually gonna match based on this token
15:26 : of streams that that the lexer has given
15:30 : you but how does that work but the way
15:32 : you actually match the tokens there's
15:36 : actually two ways one is you can match
15:39 : it based on the type of the token or
15:43 : just that guy you can say I want to
15:46 : match a newline if you won't do that you
15:49 : put a 10% in front of them in from the
15:53 : type name another way of matching a
15:56 : token is by matching it the literal
15:59 : string so just which actually looks just
16:03 : like before
16:04 : so in the cases where we had these
16:08 : literal strings that were matching
16:12 : strings could actually in a lot of cases
16:16 : leave it like this and it would still
16:19 : work as long as the text value of the
16:23 : token matches up with that string
16:26 : literal exactly and I actually think did
16:32 : that works with regular expressions as
16:34 : well so if you had a regular expression
16:36 : that matched up with the text field of a
16:40 : token I believe that also works even
16:42 : though it doesn't say that in the
16:44 : documentation so so we're gonna go ahead
16:48 : and give that a try but the first thing
16:50 : I'm going to do is write or configure a
16:54 : lexer so that it it can handle the
16:59 : arithmetic syntax that we have so far
17:02 : and that arithmetic syntax so far has
17:09 : things like these so we can do additions
17:13 : we can do a function call for simple
17:16 : built-in functions we can do multiply
17:20 : and divide using this very pretty
17:23 : multiply and the division symbols and we
17:28 : can have parentheses here so what we're
17:32 : going to need to do is sort of break
17:34 : this up into tokens all right so I'm
17:38 : gonna actually cut this up in here why
17:44 : spaces are actually tokens as well okay
17:48 : so that's a lot of cuts so basically
17:50 : here we have I'm gonna say it will have
17:52 : a left paren this is a number this is a
18:01 : y space this is a plus that's a white
18:08 : space again and so for etc etc so each
18:11 : of the right this is how I'm gonna cut
18:13 : up this input string into tokens let's
18:18 : do that so I'm gonna go to this file and
18:21 : change this configure a trick to do what
18:24 : I want basically okay so I have the left
18:29 : paren and right prat which is gonna then
18:31 : these are is going to be string literal
18:33 : matches
18:33 : I'm gonna tell MU the lecture library to
18:37 : whenever it sees a left paren make a
18:40 : token with the type of alprin the time
18:47 : symbol and the divide symbol and the
18:50 : plus and minus symbols and then I'm
18:53 : gonna for all the function names for the
18:56 : built in function names I'm gonna make
18:57 : them string literal matches and if any
19:01 : of these six names are matched it's
19:05 : going to generate a token with the type
19:08 : of built-in functions so let's try that
19:10 : to try to execute this lecture by itself
19:14 : first before actually integrating it
19:17 : with nearly Jas okay so there there it
19:23 : is we put in one plus two so we get a
19:27 : token number token with the value one
19:30 : and then some white space and then a
19:32 : plus token and then some white space and
19:37 : a number token with the value
19:39 : - so that looks great let's try another
19:43 : example a more complicated one okay so
19:47 : this one we get an l / n token for the
19:53 : left parenthesis and then we've got a
19:55 : number with a value of 1 and then at
19:57 : white space plus token white space and
20:01 : number 2 and then I write bran white
20:05 : space again a times token white space
20:09 : again and then a built-in function and
20:11 : then their left paren and then a number
20:14 : and I write prime again one thing I want
20:16 : to mention though is at organiser
20:18 : doesn't do the higher-level syntax
20:23 : matching which means that at this point
20:26 : you can actually give a lecture
20:29 : something that's syntactically invalid
20:32 : such as like we forgot to close the pram
20:36 : but the lecture is actually none the
20:39 : wiser
20:40 : about this so if I do move play here the
20:44 : lecture from the Lexus perspective
20:46 : there's no error here because it doesn't
20:49 : do the higher-level validation so now
20:53 : let's try to actually integrate the
20:55 : lecture into nearly Jas so this is what
20:59 : you do you you you you make a special
21:02 : block like this similar to one of these
21:05 : blocks where you put in custom
21:08 : JavaScript except this is a top-level
21:10 : javascript block which you're asking
21:14 : nearly Jas to put at the top sort of
21:18 : like a global place of the resulting
21:22 : javascript file and in this case you
21:25 : gonna need to put an add sign in front
21:27 : of this block okay so at this point you
21:32 : can declare your you need to require the
21:36 : MU library and then declare a lexer like
21:39 : that and then you need to tell nearly
21:42 : Jes which global variable has your lexer
21:46 : been initialized in using this add lexer
21:50 : syntax so this act
21:52 : lexer syntax is a special syntax and
21:56 : then the next word lecture is referring
21:59 : to the global variable that you have set
22:01 : up so which is to say that you could
22:06 : choose to name that something different
22:09 : like I don't know fubar and if you done
22:13 : that you would change that here so now
22:16 : we have the lexer setup and but I I
22:20 : expect this this is not the end of this
22:25 : work as Rex something will not work
22:28 : properly but let's just run it though in
22:32 : any case and see what happens so we're
22:34 : going to regenerate the parser and
22:36 : regenerating a parser actually caused
22:39 : the JavaScript version of the parser to
22:43 : update with all of this new stuff so now
22:47 : let's just try to run the parser again
22:49 : and see what happens and when we run
22:53 : this parser file it parses this input
22:56 : which has been hard-coded here as an
22:59 : example and it runs through the parser
23:03 : the parser generates an AST tree
23:06 : abstraction dextry and saves it into
23:09 : this AST that JSON file so let's take a
23:12 : look at what's in that file right now
23:14 : before it looked like this and
23:17 : afterwards we got a lot more information
23:21 : so you can see this shape this shape
23:25 : with the line number information and the
23:27 : offset and the text and the value that's
23:29 : a token that's coming from the MU J s
23:33 : based tokenizer so something is working
23:36 : if we took a closer look at this the the
23:39 : operation parts of the AST it has these
23:44 : tokens in them but the numbers don't
23:47 : appear to have this the move tokens in
23:51 : them and we need to fix that and the
23:54 : reason the numbers are not working I
23:57 : believe the way that this math
23:59 : arithmetic grammar has been defined it
24:03 : does this low-level
24:06 : parsing of the number which it does not
24:09 : need to do anymore what we've actually
24:11 : done is taken over the parsing of the
24:15 : number part using the lexer using mu j s
24:19 : and it actually ends up being a lot
24:21 : simpler to write this way
24:24 : actually it doesn't handle decimal
24:26 : points though although we're not using
24:28 : decimal points at the moment but in any
24:31 : case we're going to switch over to
24:33 : basically handling the parsing of the
24:36 : number using mu J s using a good regular
24:40 : expression here to simplify the
24:43 : definition of the grammar itself
24:46 : so after mu J s is done processing it
24:51 : will already give me number type tokens
24:54 : and I'm just gonna plug that in and this
24:57 : digit and digits symbol it's only used
25:00 : for this number symbol so I'm gonna
25:03 : actually get rid of all of this code
25:04 : reference the number token remember this
25:09 : percent symbol the percent symbol is
25:13 : used to tell that to tell nearly that I
25:17 : want to use I want to match the token of
25:20 : type number so regenerate the parser
25:25 : running it okay running it and we're
25:28 : getting these numbered hogan's except
25:30 : they've been wrapped inside of this
25:32 : extra array which we don't want but
25:34 : that's quite easy to fix we just use
25:36 : this this ID function that's which it's
25:41 : a convenience function provided by
25:43 : nearly yes we've covered in the previous
25:45 : episodes so so know well we should have
25:52 : these numbers unwrapped so left hand
25:55 : side is a number token in the right
25:57 : hands is a number token and that's good
26:01 : on the next thing we we can convert over
26:04 : is the white space so the white space we
26:08 : no longer need to use a regular
26:09 : expression to do it because there's a
26:12 : regular expression in the move lecture
26:15 : to do that for us so we can just convert
26:17 : this
26:18 : point to the west placetype so and I
26:24 : just realized I made a mistake here
26:26 : earlier by writing capital WS instead of
26:30 : lowercase WS it took me some some
26:33 : debugging time to figure this out but
26:35 : when I figured this out this parser is
26:37 : working just like before so let's test
26:40 : this that the ast after is generated so
26:46 : yeah the whitespace tokens should
26:49 : actually not making it into here at all
26:52 : because we're not interested in that
26:54 : information in in the AST but what is
26:58 : beneficial now with this information
27:01 : well there's two things right about two
27:03 : main things in my opinion about using a
27:06 : letter that's beneficial one is the
27:09 : performance enhancement when you're
27:11 : working with large programs large
27:14 : program with a lot of symbols in it
27:16 : lexer can work faster can do the
27:19 : lower-level stuff faster so we can speed
27:24 : up the parser that way but a second
27:27 : benefit that we get early and this is
27:30 : very important to me is we get this line
27:32 : number information so that when there
27:34 : are errors whether it's a syntax checker
27:37 : error or it's a program semantics
27:41 : checker or it's a linter checker what
27:43 : kind of whatever kind of error
27:46 : you wanna display to the user you can
27:49 : actually attach with that error the
27:52 : location that originated that error and
27:56 : that is extremely helpful for the
27:58 : usability of your parser okay I'm gonna
28:01 : stop this video here thank you for
28:04 : watching if you're following along with
28:06 : these videos and you're working on
28:09 : implementing your own parser and you
28:12 : have questions or run into issues by all
28:15 : means you can ask me questions by
28:17 : writing a youtube comment thank you for
28:20 : watching I hope you see you