Building MyPL Part 1

In this drive by code session I replay WaiKit’s code session where he builds a parser for a programming language called MyPL. This is part 3 in a series about building programming languages. I recommend watching the first 2 in the series before this one.

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : hello and welcome to a drive-by code
00:02 : session this is part three of the how to
00:05 : make a programming language series if
00:09 : you missed the first two I recommend
00:11 : that you go and watch those before
00:14 : continuing on with this video this this
00:20 : episode is going to feature a nearly J S
00:23 : which is a parser generator with which
00:26 : you write a grammar and then you convert
00:30 : the grammar into a JavaScript parser and
00:35 : wake it and I have been researching how
00:38 : to build parsers and various parser
00:41 : generator tools like nearly Jas and we
00:44 : found this to be one of the best for for
00:48 : the at least in the JavaScript universe
00:51 : the JavaScript ecosystem and
00:53 : incidentally nearly is also a NPM staff
00:57 : pick quite a high honor so let's get
01:01 : into code so as usual why could draw the
01:05 : code and I'm just going to replay what
01:07 : he did and explain so the first thing he
01:12 : does is initialize an NPM project or
01:17 : nodejs project by making a package.json
01:21 : file using the NPM and NIT come in and
01:25 : he installs nearly and you can see
01:28 : nearly there in the list of dependencies
01:32 : now he starts out writing a grammar and
01:35 : what grammar what kind of grammar is
01:38 : this well this is in computer science
01:40 : lingo the sake this is a context-free
01:46 : grammar C F G and a context-free grammar
01:53 : consists of a number of production rules
01:56 : so what you see here is a production
01:59 : rule which consists of a left-hand side
02:02 : an arrow and a right-hand side this rule
02:05 : defines the symbol that's on the
02:08 : left-hand side this is
02:10 : this is a symbol on the left hand side
02:14 : there's one symbol on the right hand
02:15 : side there can be one or more symbols
02:18 : this one happens to have one this symbol
02:22 : is a special symbol it's matches some
02:25 : characters and this is syntax from the
02:30 : nearly style of grammar this is saying a
02:35 : number is one or more this plus stands
02:41 : for one or more it's one or more digits
02:47 : or characters between 0 and 9 and you
02:52 : might recognize this + from regular
02:56 : expressions however this does not have
02:59 : the full power of regular expressions so
03:02 : you this cannot do everything that
03:04 : regular expressions can do this colon is
03:07 : a syntax or operator that allows the
03:11 : plus sign that follows so with this is
03:14 : enough to have a valid grammar so we can
03:19 : ask nearly or the nearly C command which
03:24 : stands for the nearly compiler that's a
03:26 : nearly compiler to take this grammar
03:29 : file and output a JavaScript file which
03:33 : we'll call my PLA yes if you look at my
03:36 : pjs it's actually fairly short file but
03:41 : this is a JavaScript representation of
03:43 : this grammar file we're gonna put this
03:49 : compile command into the scripts
03:54 : definition in the package.json so that
03:56 : next time we can just do npm run gen
04:00 : parser to rebuild the my pjs file from
04:05 : the grammar file next we'll make a parse
04:10 : Jas and this is how you build a parser
04:14 : with nearly and these are in the
04:17 : instructions on the nearly website so
04:19 : you can also use that as a reference
04:21 : so first you required in the early
04:24 : library then you also required them IPO
04:26 : that yes that was generated in the
04:28 : previous step and then you plug them
04:31 : together like so to grade an instance of
04:34 : a parser and you have a parser you feed
04:37 : a string into it like so and then the
04:39 : parser will have a results property on
04:43 : it that contains the results of the
04:47 : parse so to run this file and then we
04:51 : received the results of the parse and
04:53 : this the result of the Parsis actually
04:56 : will end up being coming your ast as we
05:01 : defined and described in the last
05:04 : episode for now this ast looks like a
05:08 : very very nested series of arrays we'll
05:13 : fix that just a little bit if you change
05:17 : the input to ABC then the parser is
05:20 : going to barf at you because the
05:22 : language or the grammar that defines the
05:26 : language as it stands does not support
05:31 : the string ABC it only supports digits
05:37 : which it is gonna improve the error
05:40 : message so if you this is a error
05:45 : message a little more easy to read it's
05:47 : saying unexpected a because the language
05:50 : itself does not understand the character
05:52 : a if we switch it back to a number then
05:55 : the parser is happy he'll make it more
06:00 : explicit that the parse succeeded when
06:03 : it does now and now next thing is let's
06:05 : support decimal numbers so at current
06:11 : state the parser is going to barf at
06:14 : decimal numbers because again the
06:16 : grammar doesn't understand the character
06:19 : dot so we need to make it understand
06:21 : that so let's call this number let's
06:24 : call that digits and we'll say a number
06:28 : redefine number as some digits followed
06:31 : by a dot and then followed by some more
06:35 : so now the grammar is able to support
06:38 : parsing decimal numbers so we'll
06:40 : regenerate the parser and rerun parse
06:44 : and now now it the parser is able to
06:49 : parse a decimal number next let's
06:55 : support variable assignment syntax so
06:58 : let's say a variable assignment is first
07:01 : an identifier which is like a variable
07:03 : name and then colon equals and then a
07:06 : number and what's an identifier well
07:08 : we'll define it on the next line an
07:10 : identifier is zero or one or more
07:15 : alphabet letters from A to Z so now the
07:22 : parser should be able to parse variable
07:26 : assignments although there's a mistake
07:28 : here so if we regenerate the parser
07:31 : first to bring this grammar into this my
07:34 : prgs so the parser is updated and then
07:38 : we'll parse and this there's a mistake
07:41 : because as we saw a assignment operator
07:45 : has a colon in front of it and why could
07:48 : forgot about that so fix that put a
07:50 : colon there and now the parser succeeds
07:53 : at this point the top level grammar is
07:57 : variable assignment
07:58 : so this parser can actually only parse
08:02 : variable assignments let's say this
08:06 : program can parse variable assignments
08:08 : in numbers so this is how you do that
08:12 : this is new syntax for the grammar
08:15 : syntax first we had the arrow sign and
08:18 : now we have the vertical pipe which
08:21 : means or so this is saying the top level
08:24 : input or what it means to be a program
08:28 : in my pl is a program is either a
08:31 : variable assignment or a number so let's
08:35 : regenerate this parser and
08:38 : we will try to parse it and although it
08:42 : succeeds we have a little problem number
08:45 : currently can only be decimal numbers
08:49 : can only have a decimal number so we'll
08:50 : also use the bar to say a number can
08:54 : actually be a decimal number or it could
08:56 : be just be an integer
08:57 : it's just represented by one series of
09:00 : digits and with that fixed we regenerate
09:03 : the parser parse and then we get some
09:07 : values in the parse okay let's let's go
09:12 : to the next part which is know that
09:15 : given we have a grammar we have a
09:18 : grammar that I mean this is a very
09:21 : simple
09:21 : this is a very small subset of what a
09:25 : whole programming language would be but
09:28 : each of these symbols we want to
09:31 : represent it in the AST the abstract
09:34 : syntax tree and we are going to use
09:38 : JavaScript to do that so nearly has
09:40 : built in JavaScript interoperability and
09:44 : you do that by by writing a curly
09:49 : bracket and then % and then close this
09:53 : javascript block with % in Cordy bracket
09:56 : and in the middle you can write some
09:58 : JavaScript you can even use yes 6 or use
10:04 : s7 syntax if you like so what you want
10:08 : to write inside these brackets is a
10:12 : JavaScript function which takes an array
10:16 : of matches and returns anything you want
10:20 : you're trying to return some value than
10:23 : you that you want to use to represent
10:27 : what it means to be the symbol that
10:30 : you're defining with this rule so in
10:32 : this case data will represent this guy
10:42 : there's only one symbol here it'll be
10:46 : array inside of an array because the the
10:49 : inner
10:50 : a is an array because of this plus sign
10:53 : which means one or more so you end up
10:57 : having for the foot a string one two
11:01 : three for example you'll end up having
11:04 : an array of like so so this is data here
11:08 : this is data oops yeah this guy is data
11:12 : so what we're saying is we we yeah
11:15 : there's only one match we know that
11:17 : we're just gonna get the first one or
11:19 : the zeroth one to get this guy so this
11:23 : is state zero and then because we just
11:27 : want these digits join together we'll
11:29 : use array that join to join them
11:31 : together and there is the full result
11:35 : here should be the string one two three
11:39 : and that's really what we want for the
11:41 : digits so let's go ahead and do that I'm
11:45 : sure gonna skip over some of the things
11:48 : go to the next part so oh yeah we ran
11:50 : that and then we in in the four to
11:55 : represent digits we just get the string
11:57 : of the digits now how do we want to
11:59 : represent numbers though well we can say
12:05 : to represent the number is the same
12:08 : array of digits so this digit is again
12:11 : you'll get an array and then in this
12:14 : array is whatever digits returned will
12:19 : go into this array which currently is
12:22 : something like one two so we want to
12:26 : sort of unpack this array so that the
12:31 : thing that represents the number is just
12:33 : a string rather than wrap inside of an
12:36 : array so we'll do that however there's a
12:42 : shorthand to doing that because this
12:44 : pattern is so common nearly gives you an
12:48 : ID function to which just means simply
12:52 : that unpacked the first item of an array
12:56 : so and if you generate that you see that
13:01 : the number of nested arrays is another
13:04 : level less now so we're gonna use this
13:08 : ID function for each rule where the
13:11 : right hand side only has one symbol so
13:15 : like so oh just a little bit of
13:17 : formatting here and now the top level of
13:22 : the parse tree is just the digits now
13:25 : however we haven't correctly supported
13:29 : decimal numbers yeah that only happens
13:33 : for the ones where the right hand side
13:36 : has one symbol so how do we handle that
13:38 : one let's do a decimal number and
13:43 : currently a decimal number is
13:45 : represented as an array of the parts
13:47 : okay
13:49 : so we'll write a function here that
13:53 : takes the data array and now in this
13:58 : case the data array is gonna look like
14:00 : this it's gonna be an array that has
14:06 : three parts so now so we're going to say
14:11 : I'm gonna take the different parts in
14:14 : the array concatenate them together with
14:18 : the dot I don't already know the middle
14:20 : part is gonna be the dot so just gonna
14:21 : hard-coded that concatenate them
14:24 : together and use the number function to
14:26 : parse them into a JavaScript number and
14:29 : while we're doing that we might as well
14:31 : do that for the integer as well so let's
14:35 : regenerate the parser and parse and now
14:39 : we actually get an integer
14:41 : representation in the AST tree instead
14:45 : of a string of digits and test that for
14:50 : integers also and that works as well now
14:53 : what about the variable assignment for a
14:56 : variable assignment we actually like to
14:58 : represent that as a JavaScript object
15:01 : something like this
15:05 : I see how to do that so again we have a
15:09 : function that takes a data array what is
15:12 : it another return is gonna return an
15:14 : object and again this data got this data
15:21 : is going to be an array where its
15:26 : members are the matches on the right
15:29 : hand side here so so we're gonna say the
15:36 : type is gonna be the string or
15:39 : assignment and the VAR name is gonna
15:41 : come from the zeroth element of that
15:43 : array the value is gonna come from the
15:47 : last the second element from the array
15:50 : so regen the parser and parse and now
15:54 : the STS represents this ver assignment
15:58 : with this object now cool at this point
16:03 : we're about halfway done building this
16:05 : parser so I'm going to take another
16:07 : episode to finish up building this
16:11 : parser so that would be the next one in
16:14 : this series and then after that we'll
16:17 : start building a Java Script generator
16:19 : which takes the ast that was produced by
16:22 : the parser and generates some working
16:26 : JavaScript so I hope to see you in the
16:30 : next episode

Building MyPL Part 1 - Parser

Transcript