Make Your Own Language 4: The Generator

This is the fourth 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 a code generator that produces JavaScript, in JavaScript.

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : hello there this is Toby and welcome to
00:02 : the series where we make a programming
00:04 : language together we're making a small
00:06 : Lang you can find a project page here
00:09 : and and we're using the parser generator
00:12 : tool called nearly je s and last time we
00:15 : completed the parser for variable
00:18 : assignments function calls as well as
00:21 : multiple lines so at this moment we're
00:24 : able to parse a very simple program such
00:26 : as this in this episode we are going to
00:30 : start writing a generator
00:32 : the generators job is to take this ast
00:34 : file which is a detailed description of
00:37 : D of this programs syntax translated
00:41 : into JavaScript which can actually be
00:43 : executed and produce a result so let's
00:46 : get started in order to build a
00:49 : generator I'm going to create a new
00:51 : script generate a yes and I'm gonna make
00:56 : a sync main function and call it again
01:05 : I'm going to use the file system module
01:07 : to make this kind of thing easier for me
01:11 : I'm gonna read in a file name which is
01:14 : passed in from the command line I have
01:16 : done a similar thing in my parse script
01:19 : here so I might actually just steal this
01:21 : code from this parse script here and
01:24 : here I'll say please provide an ast file
01:27 : because it's an ast file that generates
01:30 : a JavaScript file to visualize that
01:33 : first we have a dot small file we gonna
01:35 : put that through our parse js8 aest file
01:43 : and then we're going to take that dot
01:44 : AST file and send it through our
01:47 : generate dot j s process which that's
01:52 : what we're making now and that is going
01:54 : to give us a dot J s file and then later
01:58 : we're gonna send this dot J's file
02:01 : through denote the process and that will
02:03 : actually give us results we're at step
02:07 : two out of three right now let's get
02:10 : back to it
02:11 : if they gave us the
02:12 : file now we're gonna actually read and
02:16 : est file let's do it like this
02:19 : so est-ce song will be received and to
02:24 : receive it will say a weight FS dot read
02:26 : file the file name that will get us a
02:30 : buffer object will convert that to a
02:32 : JavaScript string and then after we have
02:35 : the ast JSON we need to JSON the power
02:37 : stop to get the actual ast and then once
02:41 : we have this ASC we're ready to go
02:44 : through the ast and generate a travel
02:46 : script file I'll say that there's a
02:49 : generate function which we're going to
02:51 : make which takes the ast and spits out
02:54 : some JavaScript code and once we have
02:56 : this JavaScript code we're going to
02:58 : write it as a file we'll come up with an
03:05 : output file name a little bit after
03:09 : basically we're gonna spit out this
03:11 : JavaScript code here and then we'll say
03:14 : we wrote okay let's come up with this
03:19 : output file name now I'll just say we'll
03:22 : take the name of the ast file and
03:24 : replace the dot ast extension with a dot
03:29 : GS extension and we're done we're going
03:32 : to need a generate function for this to
03:34 : work aren't we and actually at the
03:36 : moment the ast is going to be an array I
03:41 : believe because we have represented our
03:43 : program as an array of statements so so
03:47 : because of that I'm actually gonna call
03:49 : this the statements and I'll have to
03:53 : generate actually be called generate yes
03:56 : for statements
03:59 : it'll take a statements array so now for
04:04 : the sake of testing if this script works
04:07 : I'm just gonna return a simple hello
04:10 : world program no matter what the ast
04:14 : says oh that's wrong saying okay let's
04:18 : try this generate GS
04:21 : and send it this e^x to the PST file EST
04:28 : is not too fine let's fix that 912 I
04:31 : changed it to be called statements so
04:34 : that's why it's not defined ft argument
04:38 : must be of type number o FS that right
04:42 : is a more low level function which takes
04:45 : a file descriptor argument has the first
04:48 : argument I actually meant to use race
04:52 : file which is a more high-level function
04:55 : that takes a file names so that was the
04:58 : problem
04:59 : okay it generated the JavaScript file
05:01 : which does torrent hello world we can
05:03 : even run it using no GS and there are
05:06 : this it works and we have a working
05:09 : generate well it doesn't work because it
05:12 : doesn't actually translate the ast so
05:14 : now let's make it translate yes T let's
05:16 : start small let's go back to the first
05:18 : example where we simply had one
05:21 : assignment statement and try to
05:23 : translate that one actually you need to
05:25 : reparse that because we have changed
05:28 : things since then the top-level supposed
05:31 : to be an array at this point so reaper's
05:34 : example one dot small and now example
05:39 : one's AST file has an array wrapped
05:42 : around the statement then which is what
05:44 : it should be
05:46 : so let's loop through the statements I
05:49 : use the for off syntax to do it and I'm
05:55 : gonna make a right to receive the
05:58 : results of translating each of these
06:02 : statements actually so say I'm making a
06:05 : variable called lines and then at the
06:08 : end I'll just join the lines together
06:11 : like this but inside of this for loop
06:15 : I'll make a generator yes for statements
06:19 : I'll generate a line of JavaScript by
06:24 : another function call which I'm going to
06:28 : call generator yes for statement
06:31 : singular so a statement if we look at
06:42 : our grammar a statement can either be a
06:46 : VAR sign or a phone call and then later
06:52 : on we'll encounter things like
06:54 : expression and stuff like that and
06:56 : actually I'm thinking to make it a
07:00 : little bit more convenient
07:02 : I might just sort of merge statements
07:05 : together with expressions because
07:07 : expressions oh it is not the case but
07:10 : really we should allow function calls to
07:13 : be expressions as well which we're gonna
07:15 : have to test very soon so like function
07:19 : calls really belong here
07:21 : I'll do that a little bit later but for
07:24 : now I'm thinking just have one generate
07:28 : function for both statements or
07:30 : expressions for statement or expert and
07:34 : then here because we're looping through
07:37 : this array at the moment only have to
07:40 : hand out of our sign type will just say
07:43 : if statement type is for sign then we're
07:48 : gonna generate the appropriate
07:50 : JavaScript statement for that which is
07:54 : going to look like something like Glatt
07:57 : or let's go var because I don't really
08:00 : want to deal with scoping issues for now
08:03 : in var in JavaScript is more relaxed
08:05 : about scoping rules we're gonna have the
08:10 : variable name equals GS expert and then
08:15 : a semicolon okay so now I have to get
08:17 : the variable name verbal name can be
08:19 : gotten from that guy or the statement
08:22 : I'll call this X
08:24 : or maybe just nude standing for ast note
08:28 : though this note and I would say the VAR
08:33 : name we're gonna get by a note that var
08:37 : named value so that will give us the
08:41 : variable name and that goes in here and
08:43 : then as for the JavaScript expression
08:46 : which is on this side is a string
08:48 : literal in this case but it could be a
08:51 : bunch of other things it is for now it's
08:53 : going to work if we just grab its value
08:57 : we can do the same thing here and for
09:01 : now that's going to work but later on is
09:03 : not okay so we'll take this line of
09:06 : JavaScript return it it's gonna get
09:08 : returned back here and then oh I forgot
09:12 : we're gonna push it into the lines array
09:15 : and then this will have it and the
09:17 : endian and we'll run it out back
09:19 : together so now let's try this
09:20 : I'm gonna say no generate example 1 ast
09:25 : generate GS for statement is not defined
09:29 : because I renamed it okay now it worked
09:35 : generates the example J yes and that
09:39 : looks good that looks like a valid line
09:41 : of JavaScript so if we have more of
09:43 : these
09:45 : then we redo this process first we parse
09:50 : the example file and then we regenerate
09:55 : the JavaScript file of this works okay
10:00 : great there's one thing though I want to
10:02 : address the issue that I found earlier
10:05 : which is that we should be able to call
10:10 : a function say sum equals
10:15 : and one we should be to a call a
10:18 : function and the function should be a
10:19 : valid expression as well and at the
10:22 : moment the grammar does not support that
10:26 : I'm going to reparse it and it's gonna
10:29 : fail he's gonna say oh that confused me
10:32 : I wasn't really expecting to see an open
10:35 : paren because I expected the right-hand
10:38 : side to be an expert and what's an
10:42 : expert is either string a number or just
10:44 : an identifier so I was okay up until
10:47 : this point like if you did this I would
10:50 : have been happy but this is not happy so
10:53 : to fix that we're gonna say well in an
10:55 : expert can also be a fun call the
10:57 : function call after changing the grammar
11:00 : file we have to regenerate the parser
11:03 : okay now let's try to reverse this and
11:06 : now it's happy
11:07 : it allows for the value part of the VAR
11:10 : assign to be a function call like this
11:13 : and now it is perfectly happy great now
11:17 : we're gonna do something a little bit
11:20 : more tricky because we could potentially
11:22 : have a more complex expression like
11:25 : we're stringing together a bunch of
11:28 : operations a complex expression like
11:31 : this with a bunch of nested function
11:33 : calls so you can see a bunch of nested
11:36 : function calls here there's no limit to
11:39 : how much you can nest
11:40 : you can keep nesting a million times if
11:43 : you want and we want our generator to be
11:46 : able to handle that how do we handle
11:47 : that we're gonna need to handle it with
11:49 : recursion whereas this is an ast that
11:54 : says it's an add between one and another
11:58 : function call
12:02 : so this is the ast here that I have
12:05 : depicted in the form of a tree so
12:08 : basically what we want to be able to say
12:09 : is have a generate function which we're
12:15 : calling generate tree us for statement
12:18 : or expert but I'm in this diagram I'm
12:20 : gonna shorten it to chin we're basically
12:23 : saying I want to be able to Jen
12:25 : this whole AST tree and have it spit out
12:28 : some J's right but in order to do it
12:31 : we're gonna do it recursively as in the
12:34 : gen of this whole tree it's gonna call
12:37 : the gen of this subtree and then the gen
12:41 : of this sub tree is gonna call the gen
12:43 : of this smaller subtree and then
12:46 : actually will recursively call it on the
12:48 : numbers as well we're gonna gen this
12:51 : number we're gonna gen this number we're
12:54 : gonna call gen on this number we're
12:57 : gonna call gen on this number as well at
13:00 : the leaves when the gens for the leaves
13:03 : reach render value the values get
13:06 : returned to here and then sort of
13:08 : combined mix together into this pot and
13:12 : then get returned back and then when
13:14 : these things get returned back they get
13:18 : mixed together and then return back and
13:21 : then this guy returns back they get
13:23 : mixed together and then finally return
13:25 : back so that's how this recursive scheme
13:28 : is going to work
13:30 : let's see it in the code okay
13:34 : so we're gonna say I actually can't
13:36 : assume that the node has an immediate
13:40 : value anymore because if you look at the
13:42 : ast here here we're doing note that
13:44 : value and that worked out fine for a
13:47 : string literal like this and it even
13:50 : works fine for a number like this
13:52 : however it's definitely not gonna work
13:55 : for a fun call because a phone call
13:58 : doesn't have a value a phone call has a
14:02 : fun name and arguments but it doesn't
14:05 : have a value and if we run this it's
14:08 : gonna break just run it
14:10 : no it didn't break that was actually
14:13 : unexpected I wanna see what it did oh
14:15 : just undefined oh because value would be
14:19 : the fun call object and then that value
14:22 : on this object it doesn't have that
14:24 : value so we got undefined what we're
14:27 : going to do is recursively call this
14:29 : function given this object as denote so
14:34 : this object is the value to note that
14:38 : that value but then we're gonna
14:40 : basically use the exact same function to
14:43 : go through this guy in and convert it to
14:46 : JavaScript however in order to do that
14:49 : properly we're gonna need another if
14:52 : statement that knows how to handle phone
14:54 : calls as a else if note that type equals
14:58 : a phone call then do the thing that's
15:01 : required for phone calls but however
15:03 : this is going to break for string types
15:06 : and number types now so we actually need
15:09 : more conditional statements one for each
15:12 : type of AST note that's going to come
15:15 : through
15:17 : and there may be more in the future but
15:19 : for now so that this gives me a
15:21 : notification when I tried to generate
15:23 : some ast note that I haven't written
15:26 : code handle I'm gonna throw an error
15:27 : here so now let's go back and fill in
15:31 : the blanks the string and number are
15:34 : particularly easy because that would
15:38 : just be the value field of this object
15:41 : well we should return now let's handle
15:43 : the phone call taste let's grab the
15:46 : function name which is gonna be note
15:48 : that fun named value and then we're
15:52 : gonna have a bunch of arguments each
15:54 : argument is actually another expression
15:56 : and we'll need to convert each
15:58 : individual argument into JavaScript as
16:01 : well well luckily we already have a
16:04 : convenience function that does it for us
16:06 : it's generate yes for statement or
16:08 : expert so I'm gonna loop through each
16:11 : argument in the arguments array and call
16:15 : this function for each one is shorthand
16:17 : for doing that is using array dot map
16:19 : note that arguments dot map I'll do a
16:23 : little arrow function here and then
16:25 : we'll return the result of calling this
16:28 : function with york at the end and we're
16:31 : gonna get an array of the javascript
16:34 : strings and we'll just join them
16:36 : together with a comma so the result of
16:39 : this whole thing should be an argument
16:41 : list in javascript so finally we're
16:45 : going to format a javascript function
16:47 : call which just looks like the function
16:52 : name open parenthesis and then the
16:55 : argument list and then a closed
16:59 : parenthesis okay let's try this
17:02 : and that looks good that's able to
17:05 : recursively go through any number of
17:07 : levels of nesting all the way to the
17:10 : last level which was here and then
17:13 : generate the JavaScript for each one so
17:16 : that looks great and I'm gonna stop here
17:18 : for this episode in the next one what
17:22 : we're gonna do is try to make this
17:25 : programming language somewhat useful by
17:28 : adding some useful runtime functions so
17:31 : I'll see you next time