Make Your Own Language 7: White Space and Ambiguous Grammar

This is the seventh 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 add more proper whitespace handling to the language and run into some trouble, but nothing we can't debug our way out of.

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : hello there this is toby i'm sorry for
00:02 : the bad lighting here
00:04 : i'm coming to you from the evening
00:07 : let's continue the series where we make
00:09 : a programming language
00:11 : i'm going to finish up what i started
00:13 : last time
00:14 : last time we wrote the parser to parse a
00:18 : lambda expression and we use this guy
00:21 : as the test file so at the moment we are
00:24 : able to
00:25 : parse lambda syntax like this
00:28 : and be able to generate ast files
00:32 : to verify what i just said i'm gonna
00:35 : parse this file example four
00:38 : which is going to generate this ast file
00:41 : for us and we have a
00:43 : lambda expression here as i would expect
00:46 : what we would like to do is to get a
00:49 : program like this
00:50 : working the big thing is to
00:54 : write the code generator for lambda
00:56 : expressions
00:57 : however uh last time in terms of the
01:00 : parser
01:01 : uh i have forgot some aspect
01:04 : of the syntax so i'm going to try to fix
01:07 : that this time
01:08 : first before we go ahead and build the
01:10 : code generator
01:12 : and that aspect of the syntax is a
01:15 : white space as in in the case where
01:18 : we have a arrow function where the right
01:21 : hand side
01:22 : is simply an expression i want it to be
01:26 : possible to have this extra empty line
01:30 : here and also in some cases i would like
01:34 : to be able to have
01:35 : function expressions span multiple lines
01:37 : such as an if statement like this
01:39 : i would like the conditional and the
01:42 : consequent and alternate clauses to span
01:45 : multiple lines
01:46 : like this so even function expressions i
01:48 : would like to have the ability to
01:51 : span multiple lines and also another
01:53 : case
01:54 : these empty lines i'm pretty sure the
01:56 : grammar
01:57 : at the moment will not handle this what
01:59 : i want to do is
02:00 : to fix our grammar so that it can
02:02 : account for all of this
02:04 : white space situation and we'll add an
02:06 : extra blank line at the end
02:08 : for good measure perhaps at the
02:09 : beginning as well let's try to
02:11 : parse this file with the current parser
02:14 : and
02:16 : okay very first line we got a syntax
02:19 : error already because we have a blank
02:20 : line
02:21 : and blank lines are not supported okay
02:24 : how are we going to fix this
02:25 : well i'm going to try for a more uh
02:28 : perhaps complete solution this time what
02:31 : i'm going to do is come up with
02:33 : some additional symbols helper symbols
02:36 : to help me
02:37 : i want a version of optional white space
02:39 : that allows for
02:41 : new line characters to be within them
02:43 : and i'm gonna call that
02:45 : multi-line optional white space like
02:48 : that maybe and then for the mandatory
02:51 : white space maybe i'll
02:52 : make it like this maybe either this or
02:55 : this maybe this one
02:56 : or where it's just one side of it is
02:59 : like an
03:00 : extension of the existing white space
03:01 : symbols okay and the way we're going to
03:04 : denote that
03:05 : is the optional multi-line white space
03:08 : it's going to be
03:09 : defined similarly to the normal optional
03:12 : white space
03:13 : except the character the repeater is
03:16 : going to repeat is
03:18 : either going to be a normal white space
03:21 : or
03:22 : a new line character that's only
03:23 : different and then
03:25 : for the mandatory one you guessed it we
03:28 : just change the star to a plus
03:30 : to mean one or more versus zero or more
03:33 : i think that is it for this one but i
03:36 : want one more
03:37 : symbol the other symbol i want to have
03:40 : will help me
03:40 : solve the cases like this where i would
03:43 : like
03:44 : at least one new line separating
03:47 : this statement from this statement one
03:50 : or more new line i'll call it lb short
03:53 : for line break
03:54 : so i'll put optional white space before
03:57 : and after this guy
03:58 : in between there needs to be one or more
04:02 : of these what are these well it's a
04:05 : new line um and some
04:08 : optional white space actually if i'm
04:10 : gonna do that then i should not have the
04:12 : beginning
04:13 : because that would give us an ambiguous
04:15 : grammar if you have one of these guys
04:18 : you definitely have one or more new line
04:20 : characters
04:21 : if there's optional white space before
04:23 : the first line break
04:25 : that'll be captured here if there's one
04:27 : after the last line break that will be
04:29 : captured here
04:30 : now we are armed with these three new
04:33 : symbols
04:34 : we're going to try to go use them the
04:36 : first thing i want to fix
04:37 : is allowing these blank lines and that
04:41 : can be
04:42 : fixed by using this mandatory line break
04:45 : in place of this guy actually i'm not
04:48 : sure that will work for the very first
04:50 : statement
04:50 : but it will probably work for these in
04:53 : between ones
04:54 : we could also write this statement using
04:57 : a repeater
04:58 : as well i'm going to do that i'm going
05:01 : to use this
05:02 : repeater syntax to write this one i
05:05 : think that will simplify it
05:06 : so if we did that they'll look something
05:10 : like this
05:11 : with that and then i'll definitely want
05:14 : to change this
05:15 : this is index one now and i don't want
05:19 : the triple dot here because that's
05:21 : no longer an array let's count indexes
05:24 : this is an array it's going to hold
05:27 : another array within
05:28 : it because it's a repeater and that
05:31 : array will
05:32 : it's actually an array of arrays so this
05:35 : is 0
05:35 : 1 2. this array is
05:39 : three so this is theta three is correct
05:41 : except i'm gonna
05:42 : need to unbox this inner array of arrays
05:46 : i'll call this guy repeated and i'll
05:48 : call this guy
05:49 : rest statements there's gonna be
05:53 : like any number of these inner
05:56 : arrays with that have four elements in
05:58 : it so say repeated
06:01 : map chunks i don't know what's a good
06:04 : name for this
06:05 : zero one two okay these are the rest of
06:08 : the statements i'm gonna spread them on
06:10 : i need to generate a
06:12 : parser first now i'm gonna run
06:15 : one of the previous programs that i know
06:18 : works this one doesn't work yet because
06:21 : i haven't completed lambda
06:23 : lambda function feature yet let me try
06:25 : example three
06:26 : that does work great that's good enough
06:29 : for me so now now that i have this
06:31 : written
06:31 : in this way i'm thinking i can
06:35 : change this one into a mandatory line
06:38 : break
06:39 : that'll allow us to have multiple
06:42 : blank lines like so however this doesn't
06:45 : allow us to have
06:46 : the multiple blank lines at the
06:48 : beginning
06:50 : what we could do though is have an
06:52 : optional one of this
06:55 : i think i can use this so this goes on
06:58 : the beginning this is an optional
07:00 : multi-line white space
07:02 : this should go away because this already
07:04 : captures
07:05 : optional white space that can go here if
07:07 : i had
07:08 : double optional white space that could
07:10 : make an ambiguous grammar i think
07:12 : and then over here i think optional
07:16 : space
07:16 : over here is appropriate
07:20 : actually no it's not appropriate because
07:23 : this
07:23 : already can capture optional white space
07:26 : at the beginning
07:27 : is that true hmm i feel like
07:30 : this could give an ambiguous grammar
07:33 : right now
07:34 : but if i took it away then there might
07:37 : be some
07:37 : cases that it doesn't properly cover i
07:40 : might just have to test it out
07:42 : with different test cases to see
07:45 : i'm gonna start with this case and try
07:48 : to parse this example number five
07:52 : okay the place where it failed is
07:55 : actually
07:56 : here where this there is an arrow
07:58 : function
07:59 : so that's one of the things i wanted to
08:01 : fix so might as well just go fix it
08:03 : right now
08:05 : so at the place where this alumna body
08:09 : right following this fat arrow
08:12 : i want to allow for optional multi-line
08:16 : white space
08:17 : here
08:21 : and then that's going to shift this
08:23 : index here so let's try this
08:27 : uh there seems to be a
08:30 : error in the converter so i'm just gonna
08:33 : go debug that
08:35 : pick out the line number here which is
08:37 : 16
08:38 : ah is over here the the the code that i
08:41 : just modified let's see here it's saying
08:45 : repeated doesn't exist i
08:48 : think because we're trying to call a map
08:51 : of undefined
08:52 : actually this ought to be index two i
08:55 : miscounted
08:56 : let me try to do that again okay
09:00 : rest statement is not defined that needs
09:02 : to be pluralized
09:04 : let me regenerate the parser again and
09:07 : okay next problem
09:08 : an expected new line token here i wanted
09:12 : this to work which is
09:13 : having a new line character that can
09:17 : come after one of the arguments
09:20 : of a function call so that's going to be
09:23 : in an arc list
09:24 : of a phone call and that's going to be
09:26 : here so this
09:27 : is a mandatory multi-line white space
09:31 : just any number of white space tokens
09:34 : or new newline token
09:40 : whoa okay now we have a problem
09:43 : right after the open paren i have a new
09:45 : line so
09:46 : that's not been allowed yet so that's
09:49 : this white space here
09:50 : so i want to make that white space a
09:53 : this time is
09:54 : optional multi-line white space and the
09:56 : stuff
09:57 : that comes after the arc list that can
09:59 : also be an
10:00 : optional multi-line white space so
10:03 : regenerate the parser
10:04 : and parse it again no parts found
10:07 : oh things get trickier when there's no
10:10 : parts
10:11 : found i'm gonna try to do some test case
10:13 : simplification to debug this so i'm
10:16 : gonna
10:16 : maybe remove one of the nested if
10:19 : statements
10:21 : see if it parses no
10:26 : oh still no parts found okay there's
10:29 : something
10:30 : about the white space handling
10:33 : that is not closure now it's good
10:36 : oh so having a extra blank line at the
10:40 : end
10:41 : breaks everything what about a blank
10:44 : line at the beginning
10:46 : is okay blank line in the middle is okay
10:48 : okay it's just the blank line at the end
10:51 : that breaks everything so i'm gonna undo
10:53 : out of all of that
10:55 : bring the code back that was an example
10:57 : of test case simplification
10:59 : by the way so yes just the presence of a
11:02 : blank line oh but now i have a different
11:04 : problem we have an
11:05 : ambiguous grammar so we're gonna need to
11:07 : dig into that as well
11:08 : i first want to solve this problem the
11:11 : fact that
11:12 : a ending blank line breaks everything
11:16 : and i think the way i can solve it maybe
11:19 : have like a
11:20 : optional multi-line white space at the
11:23 : end
11:23 : like this okay
11:27 : the grammar is ambiguous at the moment i
11:29 : think we need to check out
11:31 : the reason for the ambiguity there's a
11:33 : couple of ideas i have
11:35 : for uh for fixing ambiguous grammars one
11:38 : idea is uh in the par script whenever
11:41 : there's an ambiguous
11:42 : grammar we just output an ast file for
11:45 : each of those different ast trees and
11:48 : then we inspect the ast files to see if
11:52 : there's a difference between them
11:53 : let's do that so there's gonna be more
11:55 : than one result
11:57 : when there's an ambiguous grammar so
11:58 : we're gonna basically loop through
12:00 : the results
12:04 : we'll copy this block and put it in and
12:07 : each time grab a
12:09 : different result based on the index i
12:12 : here
12:12 : to output the file name here we're going
12:15 : to
12:15 : replace the extension.smallwith.ast
12:19 : but as a cheat i'm actually going to
12:21 : insert the index right in front of the
12:23 : dot ast
12:25 : dash i dot ast as the output file name
12:29 : let's try that
12:31 : oh we have four separate different asds
12:34 : one thing we can do is do a diff
12:36 : um if you're on unix there's a diff
12:38 : command that can compare two different
12:41 : files so i'm gonna use that to see if
12:43 : the files are different
12:45 : they're not
12:48 : all four files are actually identical
12:50 : which is
12:51 : nice in one way and it's not nice in one
12:54 : way the way in which it's nice
12:56 : is that i know it didn't come up with a
12:59 : different
13:00 : interpretation of the code even though
13:02 : the grammar is ambiguous
13:04 : each interpretation of the code is
13:06 : actually the same
13:07 : so i know the ambiguous bits are all
13:10 : in dealing with the white spaces which
13:13 : makes sense because that's the thing
13:14 : that we just changed
13:16 : probably made a mistake there um i'm
13:18 : gonna try to get rid of this one
13:20 : kind of suspect that one
13:25 : we still have an ambiguous grammar even
13:27 : after deleting that one
13:29 : another thing i can do which i think i'm
13:31 : gonna do right now
13:33 : is again use test case simplification
13:35 : simplify the structure of this program
13:38 : so um this huge block
13:42 : of code is a big deal so i'm going to
13:44 : remove that see if it still
13:46 : gives me an ambiguous grammar and it
13:48 : doesn't so the presence of this
13:50 : very big statement is what is needed to
13:53 : give me the ambiguous grammar i'm going
13:55 : to remove one of these
13:57 : if statements to see what that does we
13:59 : still
14:00 : have an ambiguous grammar i'm gonna
14:02 : simplify it even further
14:04 : to this even then there's an ambiguous
14:06 : grammar so let's look at this
14:08 : first because we have to solve one thing
14:10 : at a time
14:11 : so even with this lambda function we
14:14 : have an ambiguous grammar
14:15 : let's look into that what could be
14:18 : causing this
14:19 : we got to look at the definition of a
14:21 : lambda function
14:22 : oh i have an idea it must be
14:26 : the fact that there's some white
14:28 : optional white space here
14:30 : as well as some optional multi-line
14:32 : white space
14:33 : here when you have optional things it
14:36 : makes really hard for the parser because
14:38 : when the parser sees a white space it
14:40 : could either
14:41 : match this to that white space or it
14:44 : could
14:45 : not match this to that white space but
14:47 : then match
14:48 : the next white space to the actual white
14:50 : space
14:51 : that's a really easy way to have
14:53 : ambiguous grammars so i'm going to avoid
14:55 : that
14:55 : and just unify them into one place after
14:58 : the
14:59 : fat arrow we're gonna have some optional
15:02 : multi-line white space and then the
15:04 : lambda body which can either be an
15:06 : expression
15:07 : or a block like this let's see if this
15:09 : solves
15:10 : the ambiguity and it does so now i'm
15:13 : gonna bring back some more code
15:16 : see if this okay great
15:19 : that was the problem so these four asts
15:23 : that were generated because of the
15:24 : ambiguous parts
15:26 : i'm going to delete them and look at
15:27 : this so first of all it
15:29 : ignores these extra blank lines so those
15:32 : are not represented in the est
15:33 : at all that is by design and then we
15:36 : have a var assignment to the variable
15:38 : fit the value of which is a lambda and
15:42 : then
15:42 : lambda has one parameter which is n
15:45 : the body is null that's wrong
15:48 : so we got to fix that i think that's
15:50 : because i just changed this
15:52 : rule without shifting the index back
15:56 : let's fix that looks like that was fixed
16:00 : we have a body now
16:01 : which is a function called the if
16:03 : function if is a function
16:05 : in this language we're not gonna have an
16:07 : actual if statement
16:08 : and then within the if statement the
16:10 : first argument
16:12 : is another function call to the eq
16:15 : function taking the arguments n and
16:18 : one the next argument 2
16:21 : of f is actually a lambda
16:25 : whose body has a value of 1 and no
16:27 : parameters
16:29 : and then the next one is another lambda
16:31 : who has no parameters and the body
16:33 : is another function called 2f so all of
16:36 : this looks good
16:37 : all this checks out and i'm pretty happy
16:39 : with this
16:40 : even though we ran into a hiccup there
16:43 : we were able to uh debug our way
16:45 : through that oh one more thing i guess i
16:48 : would like to change this to use one of
16:51 : my new symbols then a
16:52 : block that's enclosed by these braces i
16:55 : would like to change these guys
16:57 : to use one of these things as one of
16:59 : these new symbols i'm gonna call this a
17:03 : mandatory line break with optional white
17:05 : space around them
17:06 : i see whether i'm still referencing the
17:09 : new line
17:10 : token in other places no these are the
17:13 : only places where
17:14 : i'm referencing the new line token and
17:16 : that's how i want it to be
17:18 : let me double check that this didn't
17:20 : break anything
17:21 : by testing it against the same file
17:24 : and uh yeah i think that worked great
17:27 : seeing that that work
17:28 : of handling white spaces took quite a
17:31 : bit of time i'm going to stop this
17:32 : episode here and then in the next
17:35 : episode we will work on the code
17:37 : generator for lambda functions