Make Your Own Language 3: Parsing Function Calls

This is the third episode of a series where you build your first programming language, using these videos as a guide. We’ve setup the syntax for a small programming language. You can clone this project and start getting to work. The project repository is https://github.com/airportyh/smallang. In this episode, we write implement the ability parser function calls in the parser and modify the parser to be able to handle multiple lines of code.

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : hello there this is toby and welcome
00:01 : back to this
00:03 : series where we create a small
00:06 : programming language
00:07 : called small lang we're going to create
00:09 : it uh step by step
00:10 : and uh you're going to follow along last
00:13 : time
00:15 : we have created a parser
00:18 : we built the parser using the nearly js
00:21 : tool
00:21 : this is the nearly file that we have
00:24 : created
00:25 : and we're able to compile this file into
00:28 : a javascript
00:30 : version of the grammar which then
00:33 : we wrote a parse js which is able to
00:36 : take a file in the small programming
00:40 : language
00:41 : parse it and then output another file
00:44 : called the ast file the acronym
00:48 : ast stands for abstract syntax tree
00:52 : which is a very detailed description
00:55 : of the syntax of your program basically
00:58 : this
00:59 : object here is a description
01:02 : of this one line of code right it's
01:05 : saying what is this one line of code
01:07 : well
01:07 : it is a variable assignment a virus sign
01:11 : it's assigning to this variable name
01:14 : which is an identifier with the value of
01:16 : name
01:17 : and it's assigning to it the value over
01:20 : here
01:20 : which is something of type string whose
01:23 : value
01:24 : is the string jackie so this is a very
01:26 : detailed
01:27 : description of this one line of code and
01:30 : for every line of code
01:32 : that we're going to write in this
01:34 : programming language
01:35 : there has better be a detailed
01:38 : description of that code
01:40 : in the form of an ast okay so in this
01:43 : episode we're gonna do the same thing
01:45 : uh but we're gonna do it for the
01:47 : function
01:48 : call syntax you you have the name of the
01:50 : function
01:52 : left parenthesis and then a list of
01:55 : values and then a
01:56 : right parenthesis uh i decided to omit
02:00 : the comma in this language a sort of
02:02 : subtle stylistic choice
02:04 : there i made you can follow my lead or
02:07 : you can disregard it and
02:09 : decide to add in commas if you want
02:12 : that's up to you
02:13 : so the goal for this episode is to be
02:16 : able to parse
02:17 : this file and come up with an ast
02:21 : if you're feeling confident i would
02:24 : actually recommend that you
02:26 : try to do this on your own and then only
02:29 : using my
02:30 : video as a reference later on
02:34 : or if you prefer to just follow me step
02:36 : by step that's totally fine as well
02:38 : okay let's go into it let's say it was
02:40 : just like this
02:42 : simpler to begin with previously a
02:44 : statement could only be a var
02:46 : sign now we're saying well a statement
02:48 : can also be a function call which i'm
02:51 : going to abbreviate as phone call
02:53 : i know some people really don't like
02:55 : abbreviations
02:56 : uh i'm okay with them i it
03:00 : helps me go faster and i'm sticking with
03:02 : it
03:03 : you feel free to deviate from what i do
03:06 : if it's not your preference
03:07 : i'm going to add a definition for phone
03:09 : call
03:10 : after that and a phone call starts with
03:14 : an identifier
03:15 : and i usually programming languages do
03:18 : allow
03:18 : optional white space in between here
03:21 : although
03:22 : i tend to not put it there but i will
03:25 : allow it and now we're going to have a
03:28 : left friend which i'm going to
03:29 : write the string literal for and then
03:31 : we're gonna have a
03:32 : argument list which i'm gonna shorten it
03:35 : to arc less
03:37 : we might have optional white space on
03:39 : either side of the argument list
03:41 : and that's a function call let's write
03:42 : our converter here
03:44 : for our function call while we're at it
03:47 : so we're going to get a
03:48 : data into our converter and then
03:52 : i want to return an object that properly
03:55 : represents
03:55 : this function call i'm going to say that
03:58 : it's going to have a type of phone call
04:00 : and it's gonna have a fun name
04:03 : it's gonna have a function name which
04:06 : i'm gonna get from this identifier token
04:09 : which is gonna be at data
04:11 : index 0 and i want to grab this argument
04:14 : list
04:15 : maybe coded arguments what index is that
04:18 : n
04:18 : well we have to count we have to count
04:21 : because remember this guy is
04:24 : an array each symbol
04:27 : is an element in the array here
04:31 : and this is going to be 0 this is 1 this
04:34 : is 2
04:35 : 3 4. so argus is 4.
04:39 : um and then we're going to define what
04:41 : arc list is
04:42 : there's multiple ways to do a repeating
04:45 : thing here
04:46 : and i might show the various way way
04:48 : number one is to use
04:50 : recursion and if you use recursion
04:53 : left recursion is much preferred you can
04:56 : say
04:57 : well an argus is an expression
05:01 : or is an arc list of some
05:04 : mandatory white space and then another
05:06 : expression so this allows
05:08 : multiple arguments to resolve into this
05:11 : arc list so that means if you have an
05:14 : argument list like let's say
05:16 : you have a function called like at one
05:19 : one
05:19 : well the one becomes an expression based
05:22 : on this rule here and then
05:24 : this expression gets resolved as being
05:27 : an argument
05:28 : and then there's a white space here and
05:31 : then
05:32 : this one gets resolved into an
05:34 : expression
05:35 : now this rule is able to put this
05:38 : and this and this together whole thing
05:41 : together
05:42 : and make that another arc list and
05:45 : that's how we can
05:46 : use recursion to repeatedly
05:49 : list a bunch of things to repeat things
05:53 : yeah alternative way to do it is to do
05:57 : write recursion however right recursion
06:01 : is much less performant with the early
06:03 : parsing algorithm which is the one that
06:06 : nearly js uses so if you're using nearly
06:08 : js
06:09 : then left recursion should always be
06:11 : preferred
06:12 : however if you're using a different
06:15 : parser tool
06:17 : you should be aware that the opposite
06:19 : may very well be true
06:21 : in another tool i'm gonna go with this
06:23 : solution and then
06:24 : later on i might actually talk about
06:27 : alternative way of doing it
06:30 : so i'm gonna add converters for both of
06:33 : these guys
06:34 : actually for the expert i'm just going
06:35 : to use id because there's only one
06:38 : symbol here
06:38 : no no actually i reverse my decision
06:43 : for expert even for expert i want to
06:45 : write a converter less
06:47 : because what i would like to do is have
06:49 : an array
06:50 : represent an arg list which makes sense
06:52 : because it's in list
06:54 : so actually we want the array so i'm
06:55 : going to say i'm going to take the data
06:58 : which is an array that contains just
07:00 : that guy and i return another
07:02 : array that contains just the 0th
07:05 : element which is that expression but in
07:08 : the case where we're having recursion
07:10 : and combining something that's already
07:13 : an array with something that's not an
07:14 : array
07:16 : i'm going to basically combine the two
07:18 : into a single array
07:21 : by first spreading the result of that
07:24 : onto this array
07:26 : which this spread operator if you're not
07:28 : familiar just takes all the
07:30 : of the contents of that array which
07:32 : we're assuming
07:33 : data index 0 is an array because that
07:36 : does satisfy it and we're going to make
07:38 : this
07:38 : satisfy it so this is an array we're
07:41 : copying all of them
07:42 : onto this outer array but then we're
07:44 : going to add on this guy
07:46 : which is going to be data index 2.
07:49 : okay so that's our arg list and that's
07:52 : what we're giving into
07:53 : the argument list for a function call
07:56 : and we're saying a statement can be a
07:59 : variable assign or a function call so i
08:01 : think we have enough
08:02 : to parse this program i believe
08:06 : i'm going to regenerate the parser
08:11 : and then now i'm gonna run the parse.js
08:14 : on this
08:15 : second example example two
08:18 : that's small and it parsed it and
08:19 : generated this
08:21 : example to ast and here it is this is a
08:24 : phone call
08:25 : with the fun name of an identifier that
08:28 : has the value of print
08:30 : and the argument list looks like that
08:32 : has one argument in it
08:33 : it says hello world let's change it to
08:36 : have two
08:36 : arguments parse perhaps again
08:41 : and now it has two arguments and that
08:43 : looks good to me
08:45 : uh what if it has no argument what
08:47 : happens then
08:49 : we have a parse error and that's a
08:51 : problem the syntax
08:53 : of this arc list doesn't allow a
08:56 : nothing that's kind of a problem how do
08:58 : you match or nothing well in nearly js
09:00 : you can match a nothing
09:03 : with a null symbol so we could actually
09:06 : do this we could actually say
09:08 : well it's a null and we've done this
09:12 : we might not even need this because a
09:15 : null
09:15 : would just be matched as an arc list and
09:18 : then there would be some
09:20 : white space and then an expert it'll
09:22 : it'll take this
09:24 : empty array and put it here so i'm
09:26 : thinking we may not even need this
09:28 : let's see if this works i'm going to
09:30 : regenerate the parser
09:34 : oh i forgot to write this arrow function
09:37 : that needs to wrap around this return
09:39 : statement
09:41 : regenerate the parser and run it now it
09:43 : actually
09:44 : does work it has zero arguments and if
09:47 : we go back to the two arguments case
09:50 : does it also work no now it doesn't work
09:53 : again
09:54 : why is that let's try to diagnose this
09:56 : problem
09:57 : saying i was confused when i saw a
10:00 : string token here
10:02 : instead i was expecting a white space
10:05 : token
10:05 : oh i see no by the way matches the empty
10:09 : string
10:09 : so there's nothing here and it already
10:12 : matched
10:13 : null so it says oh nothing is already an
10:16 : arc less
10:17 : but then it was looking for this
10:19 : mandatory
10:20 : white space here which it never found so
10:23 : if
10:24 : we put some white space here then this
10:26 : would parse
10:27 : yeah and it did but that's not what we
10:29 : want we want
10:30 : this to be allowed as well so how we're
10:33 : gonna fix that let's think about it
10:35 : um so one way i have done this in the
10:37 : past
10:38 : is first revert to the version where
10:41 : i have this arc list which basically
10:44 : has one or more arguments and then
10:48 : allow another version of this function
10:50 : call that just has an
10:52 : empty list so i'm going to make a copy
10:54 : of this
10:55 : and allow this version to just not have
10:58 : an
10:58 : argument list and then just say the
11:01 : argument
11:02 : is an empty array so this way does work
11:06 : i'll run the parser generate the parser
11:08 : again and see that
11:09 : this does work so it should satisfy
11:13 : all cases where it has two arguments
11:18 : has one argument there's the one
11:20 : argument and
11:21 : has zero arguments yep
11:24 : all three cases work there's i think
11:26 : it's a slightly less
11:28 : tedious way to do this which is i can
11:31 : make part of this optional by
11:34 : surrounding
11:35 : these two things which are the optional
11:37 : bits and then
11:38 : do a colon and a question mark a
11:41 : question mark is similar to
11:43 : regular expressions question mark syntax
11:46 : it says
11:46 : that guy is optional and if we done this
11:50 : then the thing inside this guy is
11:53 : again wrapped inside of an array
11:56 : which can be kind of confusing because
11:58 : we already have this
12:00 : massive array wrapping going on
12:04 : here but we're gonna wrap the two things
12:07 : inside in yet another array
12:10 : which is this but this array may or may
12:14 : not exist
12:14 : because this guy is optional so the the
12:17 : thing in here
12:18 : might be null or undefined uh but if
12:22 : it's not null or undefined then it's an
12:24 : array
12:25 : with two things in it so that's what you
12:27 : have to be
12:28 : aware of if you're using this optional
12:30 : syntax so i'm going to show you
12:32 : this working you pick the technique that
12:35 : you prefer
12:36 : let's see this is index zero this is one
12:39 : this is two this is three and this whole
12:42 : thing now is index
12:43 : four but index four may not exist so i'm
12:46 : gonna say well if it
12:48 : does exist then i'm gonna get
12:51 : at the zeros index within the sub
12:55 : array that is the thing
12:58 : in index 4 which is that guy but if
13:00 : index
13:01 : 4 does not exist i want the argument
13:05 : simply to be an empty array so
13:08 : yeah so now i don't have to repeat this
13:10 : big old block
13:11 : twice now i'm gonna regenerate the
13:13 : parser
13:17 : parse it again see that this works for
13:21 : all three cases so there's the one
13:25 : argument
13:27 : and there's the three arguments okay so
13:30 : that is good um finally i'm going to
13:33 : allow
13:34 : for multiple lines so what if
13:37 : i have a name which is bob
13:41 : and i want to say hello to
13:44 : bob referenced by that variable name
13:47 : well currently this won't parse because
13:50 : we
13:50 : don't have the syntax to allow for
13:53 : multiple statements yet how do we allow
13:55 : for multiple statements
13:57 : well again we can use the left recursion
14:00 : trick
14:01 : let me call this statements plural
14:03 : statements can either be a
14:04 : single statement or it can be
14:08 : a bunch of statements a new line token
14:12 : and then another statement this
14:13 : definition will be
14:15 : slightly limiting but let's go with this
14:17 : first and then we'll
14:18 : fix the shortcomings of this a little
14:20 : bit later
14:22 : but uh let's regenerate the parser i
14:25 : believe
14:25 : now oh i see
14:29 : unexpected identifier token name but it
14:32 : was expecting a string
14:34 : or a number just not an identifier i
14:37 : think that's because
14:39 : uh we haven't allowed an expression to
14:42 : be an identifier which we really should
14:44 : allow
14:45 : so we'll do that regenerate the parser
14:48 : and parse it again
14:49 : and there it is we forgot to
14:53 : write the converter for our statements
14:56 : we'll
14:56 : do a similar thing to this arc list
15:00 : here where we pick this data have both
15:04 : rules return an array in both case this
15:07 : case returns an array in that case
15:09 : returns an array with this
15:11 : combinator so this is going to take in
15:14 : the data
15:15 : here we'll return a array that just
15:19 : contains this
15:20 : one element here and here we'll write
15:23 : another converter
15:25 : and here again we want to return an
15:27 : array but this time combining this guy
15:29 : in this guy
15:31 : here we'll use the spread operator to
15:33 : take this guy
15:34 : and copy it into this helter array and
15:37 : then
15:39 : we take this guy and also put it into
15:41 : this array
15:42 : now let's regenerate the parser and
15:45 : re-parse it
15:46 : and now we have the ast and now we're
15:48 : able to have
15:50 : multiple statements in the same program
15:53 : the program is now represented as an
15:55 : array of
15:56 : objects each object representing a
15:59 : statement
16:00 : in the program okay so we're getting
16:02 : somewhere here
16:04 : we are able to parse a very simple
16:06 : program
16:07 : that looks like this and i think in the
16:10 : next video we'll actually start getting
16:13 : into building a generator
16:15 : that will take this ast structure
16:18 : and generating some working javascript
16:21 : could
16:21 : that represents this program so i'll see
16:24 : you next