Building a Parser: Abstract Syntax Trees & Binary Operations

[00:00:00]hey what's going on everyone my name is Tyler and welcome to episode three of our building a interpreter from scratch Series so in the previous episode we finished the AST types for our basic interpreter and the parser that we're going to be implementing today however I wanted to quickly note that in the description of all of these videos there will be a link to a GitHub page containing all of the source code for every single lesson so um previously I never made GitHub source code links available here I'm deciding to do so as there's going to be a lot to this and if you get lost or just want to go back and actually have a reference to follow along then you can follow along here plus I'll also go through and actually add comments to the source and stuff like that that'll make it a little bit easier to read so currently there's episode one and two right here and the other thing I wanted to show you guys is a really cool reference called AST Explorer and it's that https htex explore.net this will also be linked in the description below but what this is is it's a way for us to kind of check our AST against a popular other popular programming language parsers for example here's the Parson parser for JavaScript using Acorn and we can see what happens when we type in code so let x equals 45 and we can see that it actually shows us kind of what we should kind of be striving for right a variable declaration statements with a declarator of an identifier and an initial value of literal we can kind of see how do how does JavaScript handle these kind of complex statements right so how do they handle a function declaration or parameter lists and things like that so if you ever get lost or want to extend the language but you also kind of want to base it off of a language of your favorite choosing you can actually do this and kind of play around and just see what should be happening right it's really useful for things like order of operations so we can see here that this is what we'll have working by the end of this video we'll have things like this working Etc where we'll be able to take in binary expressions and we'll want it to be right recursive as we can see here it's not left recursive so let's actually get started now and implement the parser for our basic language types that we have so far so we're going to implement a parser that'll support our program node numeric literal an identifier and a binary expression but the last thing we need to do before we can actually get started with that is change some code in the lexer currently we have a few different token types we have closed paren open paren equals binary operators let identifiers and numbers however we need to add an additional type called an eof token and this signifies the end of file so you can think of an eof as a token that's not really visible it's not visible but it signifies the last character in a file this is going to be really useful and cause a lot less issues when we're in our parser itself so we're going to add this token and all we're going to do is inside of our tokenize function after our while loop before we return the tokens let's just do return or sorry we're going to do tokens dot push and we're just going to add a token which is going to have the type of token type Dot eof and the value is just going to be eof or ends a file like so and that's all we're going to do we're just going to make sure that we actually add our end of file token um just in case so that way we don't really have to worry about that so now we can actually get started with episode three so what I'm going to do is I'm going to open up the pan prompt type in copy episode 2 and so we're going to make sure this is recursive so I'm going to make sure to add a dash r and I'm going to create our episode three parser folder and then we're going to CD into episode three like that and there we go so now we can actually view this in vs code and get started with our parser so let's open this invisible Studio okay okay so this is everyone's favorite part typically the parser is the most fun to implement and also the most complicated but we're going to walk through this and go step by step so let's create a parser.ts file and what we're going to want to do is we're going to want to import our types from our AST so we're going to want to import a statements a program a expression a binary expression a numeric literal as well as an identifier like so so we're going to import all of the types we need from our from these files so we can actually get started with that we're also going to need to import a node type we're going to need to open import sorry not node type we're going to need to import from The Elixir so we're going to need the tokenize function so we're going to import there we go if I can type from dot slash and we're going to get this from the alexa.ts so we're going to need our tokenize as well as our token and token type values like this so now that we have all these let's create a class and we're going to export this as defaults we're going to call it um parser now the job of the parser is to take in our tokens that we created from our tokenizer so what we're going to do is we're going to do const actually we'll make this a private variable we'll call it tokens it's of type token array and let's give it a default value of an empty array next we're going to want to create a public method and we're going to call this produce is T like so and it's going to take in a string which is the source code and what we want to do is we want to return a program so we're going to return a program like so so I'm going to type return Pro and now let's actually create this program so we're going to do const program is equal to and we're going to define a program type so we're going to say this is of type program and what we want is for a program so we can recall a program node consists of this right here so let's just copy this over and get rid of that and there we go now we have our program type that we can produce like so let's also use the source code to produce our tokens array so we can save this Dot tokens is equal to and we'll call our tokenize function and we're going to pass in the source code like so so there we go now we have the ability to produce an AST of type program where each element in this body is going to be an array of statements so what we're going to want to do is we're going to want to Loop while we have tokens left in our program so what we're going to do is we're going to do while not eof like that and we're going to call this this dots not eof so we're just going to Loop while we're not at the end of the file so we're going to create a function for this privates nuts eof which is going to return a Boolean and all we're going to do is we're just going to do return this dots tokens of 0 dots type is equal to or is not equal to and we're going to do token type Dot eof so what this is saying is return this dot tokens basically the first token DOT type is not equal to end up file and we're just going to return true if it isn't if it is then we know we're at the end of the file and we should not continue parsing so that's basically it for that we're going to parse and there we go and while we're parsing what we're going to want to do is we're going to want to append to the body every single statement we find so we're going to call this dot or sorry we're going to do program dot body dot push and we're going to push on a new statement so we're going to do this dots um stmt like that now a statements I'm going to call it parse statements this function we haven't created but let's go ahead and create it and this is going to be basically the entry point for our parser so in here I'm going to go down here and go private part statement which returns in statements like so and there we go this will actually be the end of our produce AST function for a good bit of time there's not going to need to be much that we do in here until later we actually get into some complex error handling so I'm actually going to just going to minimize this okay so to produce a statement we kind of need to look at our AST and say well we don't really have any statements that we're trying to deal with we've already dealt with the program which is the only type of statement these are all Expressions so for now we actually don't have anything to parse in the future we'll have different types of statements like function expressions or sorry function declaration statements try catch blocks variable declarations while Loops etc etc but for now we don't really have anything so we skip to parse expression and what we're going to do is we're just going to do return this dots parse expression like so and now we can actually kind of get started doing stuff so we're going to create our parse expression function which is going to return an expression now since expression inherits from statements this works right so an expression is a statement but a statement is not an expression so now what we can do is we can say okay what type do we want to parse first let's for now just parse the primary expressions like numeric literals and identifiers so we're going to create a function called parse primary expression it's going to return an expression and what we're going to do is we need to parse and determine what our current token is to determine whether we're an identifier or a numeric literal so to get access to the current token I'm just going to say TK is equal to this dots tokens at index 0. however this looks really ugly and in the future we might want to change the way this actually works so what we're going to do is we're going to change this to be its own function so we're going to come up here and add a function called X then all it's going to do is return this dots tokens at index 0 as a token just in case typescript has any issues with that and there we go so now we have this at function which will simply return the current token we're at so this starts there we go and now we're just going to do token dots type just like that so now we can do a big if case or we can actually do a switch case as well so we're going to do switch on TK and we're going to handle the case where it's of type token type Dot and we want to build a handle an identifier right so what we're going to do is we're just going to return an identifier like so so what we need to do is we need to create an identifier type so we're going to say this kind is identifier in the symbol is equal to this dot x dot value however there's an issue here if we think about how this would work right let's just kind of take a quick look at our code by actually first calling this function from inside our parse expression so we're going to return this Dot uh cross primary and there we go and then also just quickly adding a defaults return um as we're just gonna lie real quick to our compiler there we go right so let's imagine what would actually happen if we were to pass in a source that looks something like this if we just passed in the variable Foo bar into a program what would happen is we would have two tokens and our tokens array it would not be the end of the file so what would happen is it would call program.body.push it would call parse statement which would return a statement parse statement we'll call parse expression parse expression we'll call parse primary and parse primary is going to get the type of the token we're currently at which again is of type identifier right because Fubar would be an identifier it's going to hit this switch and it's going to return an identifier however though returning back through the call chain it's going to iteratively keep doing this forever since we're not actually getting rid of that token we want to advance so we're at the eof so what we're going to do is we're going to instead of doing this dot at dot value we're going to create a function called Advance which simply Returns the previous token and increments it or AKA gets rid of it so what we're going to do is we're going to create a function called next sorry there we go or we can also call it eats is a common term you'll see so what we're going to do is we're going to do let's or a const prev is equal to this dot at as a token or what we can do is we can just do this dot tokens dot shift and say it's a token because we know it'll be a token and now we have this previous token we can just simply return like so so now we have the ability to get a token that we are just at as well as advance to the next token and this is just going to remove it from the beginning of the array okay so now instead of calling this dot at dot value we'll call this dot eats dot value and there we go now we have the ability to parse a identifier type now let's also add supports for parsing a token of type number and what we're going to do is say this is of type numeric literal this is no longer a number this or a new identifier this is a numeric literal and a numeric literal if we look at the type a numeric literal is going to contain a value field containing the actual number entered in the code so we're going to do value and what we're going to do is we're going to do parse floats of are this dot eats dots value like so now the reason we're doing parse floats not parse ends is because currently we only support um integers but in the future we will support floating Point values and right now we want to make sure that we can actually parse those and handle those so there we go now we have the ability in our parse primary expression to actually parse a primary expression and in the default case instead of returning like this what we're going to end up doing rights is this is going to trick the compiler for typescripts right what we're going to do is we're going to do a console.air and we're just going to say unexpected token found during parsing and what we're going to do is we're going to actually give the token those just phones so this dot ants like so and then we're just going to do Deno dot exits of one and now we don't need to trick the compiler so what we're doing here is we're saying if we get to a private primary expression we're not going to handle anything else at this point in time the most high priority types are primary Expressions they are literal types it cannot get any more priority than that so if we make it down here and we have no clue what this token is then we must have gotten to an unexpected token right maybe they typed in two parentheses instead of one or something like that now that we have this working let's actually go ahead and quickly test this out before we Implement binary Expressions because they're a little bit more complex so let's create a main.ts file and in here let's also create a folder that's going to contain all of our not compiler we'll call it front end code and I'm going to add the AST The Elixir as well as the parser and there we go and now we're just going to import parser from our front end dot slash parser.ts and in here we're just going to implement our Ripple function like so so this is going to be async function of Ripple let's just make sure we actually don't forget to call it and what we're going to do is we're just going to do punch parser is equal to a new parser so we have our parser now we're going to just do a while true Loop so we're going to keep iterating basically forever I'm just going to do a const.log um Rebel V 0.1 right so now we have this Ripple that we can use and what we're going to do is we're going to do a const is equal to prompts which is going to actually ask the user in the terminal for some input we're just going to do a greater than sunk that's what everyone does and then we're just going to do if no inputs or if input dot contains or not contains sorry dot includes exits then we're just going to do a Deno dot exit so this is just going to check for no user or exit keyword there we go and now we know if we make it to this point the user wants to enter code so we're going to do const AST is equal to our const program I'll call it is equal to and we're going to do parser dot produce AST and we're going to pass in our source code which is of type input so we're going to do inputs and there we go I also don't need to make this asynchronous I don't know I thought I did and there we go now we can actually console.log our program that we're getting back and remember our program is of type program so let's actually quickly give this a quick run and just see if this all works so we can open up our terminal clear it out and do a Deno run Dash a because we want to allow terminal access and in the future we'll also want other stuff so we're just going to do Dash a main dot TS here we can see our Ripple is starting up and we can enter something like exit and it'll exit let's enter something like the value 10 and what do you know we get a program type right it's of kind program the body though is a single value of numeric literal we can enter 10 x in Foo bar and what you'll see is we get a program which has an array containing three statements now these three statements each are them self-expressions but we can see that this works now let's go ahead and try typing something like let's and we can see unexpected token found during parsing value let type of two which is if we recall type 2 is 0 1 2 oh a let token so that makes sense so there we go now let's actually go ahead and implement the binary expression and really see how the recursive descent parser works so let's actually get started now and Implement a binary expression So currently we have the ability to eat a token return the token we're at in return if we're at an end of file what we also want to be able to do is parse from a statement we go to a parser parse expression then we parse a primary expression before we do that though a primary expression has the highest order of Precedence so what we probably want to do is we want to handle orders of precedence currently the highest order of Precedence is a primary primary expression however just above that would be an additive and just above that would be a multi multiplicative expression above that would be a unary or sorry below that would be a unary which we'll Implement in the next episode hopefully so these are kind of the Orders of Precedence that we'll be dealing with a primary expression is the highest order of Precedence we want this value to be evaluated first right a unit expression is just above that then we have multiplicative and additive expression here we would have something like a comparison then we would have things like logical Expressions so things like the and and or keywords and then up here we'd have things like function function call and a member as well as things like expression now for now we're not going to deal with any of these but I just wanted to kind of show you that the order of Precedence is important and it's important to keep in mind that the higher precedence of value is we actually want to parse that last because that'll actually give it more precedence in the tree itself so let's get started by implementing the multiplicative Addison or um comparison Expressions we already have primary out of the way so let's Implement multiplicative and additive so instead of from parsed expression we call parse primary let's call call additive so we'll do this stop parse additive expression like so and we're just going to for now just return these up to call stack so let's create this method called parse expression which returns a expr type expression right now what we want to do because in additive expression has left hand precedence right if you do something like 10 plus 5 minus 5. what we want to happen is this whole thing is an additive expression where the operator is minus the right hand side is 5 and the left hand side is its own additive expression right that's the same thing as wrapping this in parentheses so that's what we want to do we want to implement left hand precedence so to do that we actually parse the left hand value first so we do left is equal to and what we're going to do is we're just going to do this dot parse primary expression because to signify presidents what we want to do is parse the left hand side first which will then parse 10 then we'll actually handle the operators and this will all bubble up so we're going to parse a primary expression which is then going to get these values here now after we parse the left hand side we actually want to do a while loop two parse the operator token itself so we're going to do while this dot at dot value is equal to a plus or this dot X thoughts is equal to a minus so while there are still operators in between an expression and a right-hand side we're going to parse this what we're going to want to do is get the operator by doing this dot eats and what we're going to do is pass in the value like so then we're going to want to get access to the right hand side because after an operator after we eat this value the current value is going to be either a 5 or for example it could be another expression like something like this so we want to build a handle that so right is equal to this dot parse we're going to parse a primary expression this time and now we have everything we need to make a binary expression we have a kind a left-hand side a right hand side and an operator now what we're going to do is we're just going to do const by knock of type binary expression has a kind of [Applause] binary expression like so five minutes two equals there we go so it has a kind of binary expression as a left value a rights value ends an operator value like so and now we have this type of binary expression now you may be tempted to think oh so we just return this here right we return R by not like so and we're done and that's not the case we actually want to return outside of here so we want you to return left but now we're not capturing the Spy knob and what we want to do to support this left recursive rules is we actually want to say instead of this we just want to say left is equal to a new binary expression like so and the reason we can't is because this is a constant okay so let's kind of take a look at what we just did we parse the left hand side and that's because we want to be able to support recursive precedence then we can imagine if this is our code right here 10 plus 5 minus 5. what will happen is we'll parse this left hand side we'll get a 10. then we'll get an operator because we'll be found at a plus we'll get a right hand side which is a 5 at this case then we're going to say that is equal to the left so this whole thing becomes this right here then we get a minus so we're back in this loop again then we get our right which will be a 5. and this whole thing will now become left again through this assignment and we return it up and bubble it up the tree and by the time we're done with this we'll just have an eof token in our eof and our body will contain these proper types so that's a lot that's a lot to take in but let's actually give this a shot and see if this works so um did not mean to open Discord there we go okay let's actually give this a quick run so denor run Dash a main.ts let's make sure we actually call parse additive and we do here we go so now we can do something like 10 minus 5. in what do you know you can actually see that we get a type of program our body contains one element and that is a binary expression where the left hand side is a numeric literal right 10 the right hand side is a numeric literal and the operator is minus this also works like this so now we would expect to get 10 minus X plus Y and what do you know this is recursive like so we get a program a body binary the left hand side contains the 10 minus X the right hand side contains the y in the operator separating these this is a left a right and this whole thing is a binary this is also a binary so it's very recursive if you have any questions and want to go more into depth with this ask me on my Discord and I'll be sure to step through this one-on-one if you'd like okay so now we actually want to implement R right 10 times 2. ah times isn't supported right this is only an additive expression so all we're going to do is we're just going to copy this block and instead from parse additive we're going to change the name to parse to multiplicative I think I spelled that right and what we're going to do is from additive we're going to call parse multiplicative expression why why are we going to call a multiplicative because it has more precedence so we want to parse it further down the tree remember more precedence equals further down the tree and we're going to also do the same call here so parse multiplicative expression and there we go now to just change this we do a mine array um slash and we do a star however if we also wanted to support modulus we'll put this in right here this is exactly where we'll support the modulus operator like so so I'm just going to add it like so I'm going to add the modulus operator while we're on it and while we're at it I'm also going to change the Elixir to support the modulus operator so in here we're going to change this line like so we're going to add a new rule two supports the modulus operator which is on the exact same precedence of multiplication division like so so there we go now we have support for these three operators and these are all multiplicative so they will parse primary because that's further down the chain let's give this a quick run and make sure this works so we can do 10 plus 5 times 3 and what you'll see that's really neat is this follows the order of operations right if we think of this statement 10 plus 5 times 3 we want to evaluate 5 times 3 first and then we want to add 10 to it and that's exactly what this says we have an operator of plus the left hand side is 10 and the right hand side says evaluate this block before getting to this plus operation so this is really cool we can see the right hand side has precedence we could also do 10 modulus 2 minus three and sure enough we get the modulus operator and now it's left hand because left side recursion is full load over right hand side because of the Precedence just like our order of operations now the one thing we're missing besides exponents is PEMDAS for our parentheses we're not handling parentheses so if we do 34 minus 5 times 2 we expect this to work but it doesn't because we haven't handled a parenthesized expression so let's go ahead and add support for a parenthesized expression and this is actually really simple to implement what we're going to do is inside of our default right before the default we're going to say okay we've made it this far right we've handled the case of an identifier we've handled a number and the future we'll handle booleans as well as null types but here we also want to handle the case where we're at a token type of open paren just like that and now what we're going to do is really important we want to eat so this thought eats we're going to eat opening eat the opening parenthesis then we want to get the value so const value is equal to this dot parse expression so we want to get the value inside of the parenthesis and we also want to eat the paren and then we just do return value like so and this wants us to be in a block that's why it's killing at us and there we go now there's one big issue with this and that is we're not going to get error messages if there's a closing Trend missing and I really want to have error messages if an unexpected token is found for example imagine inside of our binary expression if we parse this we maybe want to have a value a rise if it's something we don't Define so for example if we parse a closing if we parse this value and we don't get a closing print let's create a function that will actually eat but if a value is not defined like we can say it expects a token type of closing paren and we give an error message like unexpected token found inside um inside front says expression like that and then we can do this dot adds like so so imagine we actually want to pass in our eat function um an optional parameter like this and let's just call it eat let's call it expect so expect is going to do the exact same thing as eat however it's going to also log an error if it fails so let's go ahead and Implement our expect function and all we're going to do is we're just going to do private expect it takes in a type of token type and it takes in an err if let's just do any for now and what we're going to do is we're just going to do if actually we'll get our previous values so pre is equal to dot tokens dot shifts as a token then we're going to say if uh no previous or prev DOT type is equal to type then what we're going to want to do is throw an error so we're just going to do console.error so we're going to do parser error and then we're going to pass in our err and this uh we're gonna pass in the previous value that we are expecting and then we're going to do expecting and we're going to pass in type like so there we go so not the most beautiful error message but it should help a lot with debugging then what we're going to want to do is we're going to want to do Deno dot exits give an error code of 1 and then return our priv if we were successful so now this expect function is going to handle exactly what we want I'm also going to get rid of this any type because I don't really care that it's any type for now and there we go so now if we look at our code we see that a produce AST function is actually going to make a call to our lexor it's going to get all of our tokens it's going to create this program type while we're not at the end of the file we're going to push through and parse every statement we locate then we're going to return the program inside a parse statement we don't really have anything to parse no variable declarations functions nothing like that so I'm going to parse an expression inside of parse expression we don't really have anything to parse either and the future we'll be checking the look ahead we'll be looking ahead to see what tokens there are but for now we don't need to look ahead we can look at our current token and determine it so we return a value from a additive expression an additive expression simply gets the left hand side and you can imagine right if this is our expression 45 times 3 minus 5 what will happen is it'll parse the left hand side that will go to the primary in here then so we'll get back a 45 then we're in the primary at this point so it'll actually see this star it'll parse the star and the right hand side so it'll actually give this 45 times 3 will come back here as a binary expression then we'll parse the operator which will be minus the right hand side will be five and we'll return this binary expression which encloses this one and that is why we do the left precedence as well as why we do additive before multiplicative because multiplicative Expressions have more precedence so hope you guys understood this and hopefully this was a good um concept to learn in the next episode we'll actually get started by traversing this tree that we're creating right so here we can do 45 minus five times three let's do five times three plus four and we see unexpected token inside print size oh it's because this was supposed to be right a another thing so we do 45 minus 5 times 34 divided by Foo bar and oh I messed up the um eat function um in the expect function it's if the type does not equal that type then we want to throw an error right this is valid code right there so we'll do 45 minus Foo Bar times X Plus Y and there we go right this all works so there we go in the next episode we'll actually get started implementing our interpreter so that's going to be really exciting for those of you who want to see how to implement a tree walk interpreter and yeah and I'll see you guys in the next video bye