Writing a Pratt Parser in Go: Binding Powers & Lookup Tables

[00:00:00]what's going on everyone my name is Tyler and welcome to my Channel today we're going to continue where we left off in our series and we're going to get started writing the Prat parser so before we write any code I want to actually dive into what prep parsing is a prep parser is a technique for parsing a abstract snx tree it is a technique similar to recursive descent but we'll actually be utilizing a concept of binding Powers which combined with lookup tables Prov provides a really clean way to write a parser uh binding power is simply how tightly a token binds to the things around it so a plus token will have a lower binding power than a multiplication token um this is similar to precedence but you can think of a higher precedence as a lower binding power a lower precedence as a higher binding power if you compare the table to the go code on the right here you can see that it's inverted the highest precedence items actually have the lowest binding Powers um when you combine The Binding Powers with a Handler function for example there will be three types of handlers in our parser two important ones and one for statements um we have a nud and a lead a null denotation or nud is a Handler which expects nothing to the left of the current token examples of this are prefix and unary expressions um lead or left denotation handlers expect something to the left of the token you're trying to parse so if you encounter a token like plus you would expect something to the left of it like five plus something else however if you run into a token like um not right the exclamation points token you would expect that that is a unary token right there's not expected to be something to the left of that instead you parse that assum in some to the right of it um L tokens are used for infix binary as well as postfix Expressions um later on in the episodes watch you get into those in this episode we're just going to write the parser for binary Expressions so we can get a g grasp of how this all works um lastly we have lookup tables which is where the idea of Pratt parsing really comes together we Define a lookup table for each of the type of handlers as well as The Binding power this allows us to let the um parse expression function which is the heart of the prep parsing technique unravel the recursion for us so instead of in a recursive descent parser where we have to manually um consider the recursion in each steps this case we will handle it with lookup tables and it'll be a lot cleaner a lot easier to extend and maintain so without further Ado let's actually get started writing code for the series and if you want to follow along with the series and you haven't yet downloaded the code please feel free to download it in the description down below at tp/ parser series on GitHub so without further Ado let's get started okay so the first thing I want to do is I want to create a newl file so I'm going to do 02l and in here we're going to write some code which we'll be able to parse by the end of this episode so for now let's parse 45.2 uh + 5 * 4 semicolon and this is all by the end of this episode we'll build a parse but it's really important that we get off to a good start and there's a lot of boiler plate code we actually have to write um which will make our lives incredibly simple throughout every other video so um this is going to be our 0.2 Lang file I'm then going to go into the main.go change this to be 0.2 Lang right and I'm going to remove uh actually we'll just make sure it still prints out the tokens so I'm going to do go run source main.go and we see 45.2 + 5 * 4 so call EF so our our lexer is still working which if you didn't follow along in the previous two videos that's where we actually went ahead and built the lexer so what I want to do is create a couple new folders in the source folder I'm going to create a folder for as which is where our tree data structure files are going to go and I'm going to create a folder called parser like so so inside of a let's create a file called A.O it's going to be package as and in here we're going to Define all of our as types so we're going to do type statement and this is going to be an interface and a statement is just going to be anything that has a method called statement like so and so let's also Define find a type called expression it's also an interface and it's going to be anything which has an expression method like so so these are going to be our two uh main types in the future we'll also have one for like literal types Etc so for now we have that let's go ahead and create a expressions.

[00:05:23]go again this is package St and in here uh what we want to do is we wanted to find um basically all of the main expressions in our language so for now I'm going to do a number expression which is a struct and it's going to just have a value field which is a float 64 like so and since we want this fun um this number expression to be expression we need to implement a method for it called expression so we're just going to do um n for like node and let's just do number expression exper like so there we go and we just need to implement a blank method for numbers so I'm going to go ahead and copy this for three things we're going to implement a number a string which is just going to have a string like so and change this to say string and this is going to be a symbol which is going to be a string and this is also a symbol okay so these are going to be our literals so and I'm just going to create just a little bit of some formatted comments just so it looks a little clean there we go now what we want to do is Define complex Expressions so for example a complex expression um an example of one would be a binary expression so we're going to do type expression which is again a structure and a binary expression contains three things it contains the left which is an expression like so the operator which is a lexer do token and the right which is an expression like so so something that is a binary expression would be 10 uh + 5 * 2 10 would be a left expression where the expression would be a number plus would be the token and the right hand side in itself would be a binary expression where five is left uh token of star and right is two so Expressions can have other Expressions which in turn can have other Expressions so um let me implement the function [Music] Nary there we go so this is all we're going to implement for Expressions today in the future we'll have a bunch of expressions for all of the different syntaxes in our language however looking at the example code this is a number plus a number time number so all we really need to do today is handle numbers in binary so um let's now go ahead and create a new file and this is going to be statements Dogo and again this is in the package of so just like we defined Expressions we're going to want to Define some statements so what's a statement just like an expression it's anything that implements the statement function so uh let's go in here and let's define a few statements so the first thing we want to do is Define a block statement and this is a not a struct sorry a actually it is a struct my bad uh because it is an implementation in the body is an array or slice of statement which means we also need to define a method n for node block statements statements empty method implementation there we go so a block statement is anything like this so for example if you have code where you have open block right in here there can be 0 to n different statements so this is a block statement something with a open block followed by one or many statements um next let's also actually I think um I only want to implement one other one in this episode and this is going to be an expression statement and an expression statement is again also a struct which contains and an expression which is an expression like so and I'm just going to copy this because I'm kind of lazy and this going to be like so now what is an expression statement well if we look at this code right here we can see this is all of this is a binary expression right so this is a binary expression where the left is a number the right is a binary expression where again the left is a number you get the idea right so all of this was this left number write another binary expression but it was followed by semicolon right so in a language like ours where we will force semicolons every single statement has to be finished with a semicolon that means something like this um fu is needed to be separated by semicolon fu is what we would call a call expression so this is a call expression so this has to have a semicolon the goal of an expression statement is to take an expression and then terminate it with a semicolon so this is how we can enforce semicolons super simply in a programming language so an expression statement is just a statement which wraps an expression so these are all of the types which we're going to be implementing for today so let's go ahead and actually get started that now that we're done implementing the as types so what I want us to do is go into the parser which we haven't oh we did create the parser folder and what I want us to do is actually get started with the parser so let's create a f called a [Music] parser pars Dogo and this is going to be package of parser and what I want to do is first Define what a parser is a parser is a structor it's not public I don't want this to be be public I want to instead call a function which Returns the as nodes I don't want to expose the structure inside of this structure uh we're going to uh do tokens which is a slice of lexer do token and the position is an INT just like it was inside of the lexer so we're going to keep track of all the tokens which we built during tokenization and inside of here we have the position and this is all we need for our parser in the future when we handle errors we might have errors which is a slice of error like so so for now we're not actually going to be handling errors um but in the future you might want to keep track of errors and keep parsing this is how you do it let me know in the comments if you do want me to show how you can actually keep track of um errors and how you can do hard errors and soft errors okay so now that we have this parser struct defined uh let's define a public exposed method called parse parse um and this is going to take in a we take in the tokens yeah we'll take in the tokens which again is a slice of lex. token and what we're going to do is return a do wrong a I want to import our a DOT uh block statement like so and for now let's just do return loock statement like so so this is going to be our publicly exposed method for parsing so uh what I want to do in here is do the body so we're going to do a body and this is going to be a type of a. statements and it's going to be of size zero so this is just going to be an array of statements and that means we can come in here and type body like so cool now the goal of parsing is in our case to continue iterating through all of the tokens until we reach the end of the file so what I want to do is Define a few helper methods which we'll be using for the rest of our time in the parser so let's go ahead and actually take a look at some of these methods we're going to want to create so we're going to want uh some helper methods so we're going to do Funk um p is a pointer to a parser and let's just call this one a current token and this is going to return a lexer do token and all we're going to do is just do return p. tokens at p. position like so so this just Returns the current token that we're at uh we also want to have a function for advancing so how do we advance past a a specific position just like the lexer how we had Advance n here we're going to have an advance function which again is going to be a p to a pointer to a parser it's going to be called advance and it's going to return a lexer do token and what we're going to do is we're going to do get the current token so we're going to do p. current token we're going to do uh p. position Plus+ and then we're just going to do return TK so this will allow us to advance past the token and return the token at which we just parsed so um let's create a few more methods that we're going to need uh one of these is going to be function uh takes an a pointer to a parser I don't know why I can't type and this is just going to be called um has tokens and this returns a Boolean and this check is simply going to do return p. position is less than the length of p.

[00:16:01]tokens and what we're going to do with this is check that one our position is less than right the token length meaning we're not going out of bounds and we want to check that p. current uh token kind is not equal to e like so and this is our check now what I want to do is actually get a method to specifically do just this current token. and we're going to want to call it P do Uh current token kind so let's go ahead and create that method and we're going to create it right here funk in fact let's actually just straight up copy this and all we're going to do is we're going to change this to say kind this is going to be alexa. token kind and we're just going to do return p. tokens. kind like so or we could just do p. current token. like so there we go perfect so that's our has tokens method and uh for now that's all we need so let's continue uh back to the parser parts right here and this is going to be pretty simple all we want to do is while right while we still have um tokens we want to continue parsing uh the statement so what we're going to do is we're going to do four and while um P do oh sorry we need to create a parser instance my bad create parser like so and we're going to pass in the tokens okay my bad about that um so yes we do need a create parser method so that way we can actually well have access to a parser so let me just really quickly create that it's going to be called create parser it's going to take in tokens and this is just a token ah sorry a slice to a luxer do token and it's going to return a pointer to a parser um since we're going to be dealing with pointers a lot with this parser stuff I like to just return the pointer like so and all I'm going to do is do return reference to a parser like so where we're just going to say tokens is like that and that's really all we need to do since Position will automatically get set to zero perfect so that that is how we create our parser now what we want to do is we want to go ahead and we want to um iterate as long as we have tokens so right here we're just going to do while P dot has tokens so while uh too few values instruct Lal does it not like okay it does not like whatever I did there there we go um anyway so while we have tokens what we're going to want to do is we're just going to do body equals a uh not col equals sorry equals appends and we're going to append a function called to parse parse statement passing in our pointer now we haven't created this parse statement function so let's go ahead and create a file called statement.

[00:19:25]go and basically we're going to have a file for statement ments expressions in the future we'll have a statement for types but for now we're not there so we're going to have a function called parse statement so I'm just going to go ahead and create this funk parse statement it takes in a p which is a pointer to a parser and it returns an a do statement like so and for now I'm just going to panic saying not not implemented perfect so there we go okay so now that we have this uh basically what we want to do is append the body to this and the body is a capital B and so is this there we go okay so let's quickly go over what we're doing here um and yeah it does not like this so I'll just keep doing like so okay so what we're doing is we're creating a parser instance we're then just going to call parse which is just going to instantiate a body create the parser and iterate while we are not at the end of the file then we're just going to return this block statement which is the whole body of our program we've defined a few helpful methods like getting the current token current token kind has tokens and Advance which we'll be using throughout our time with the parser now what we want to do is actually now get to setting up the um lookups in binding powers that I was talking about in the beginning of the episode so this is the fun part so we're going to set up lookups Dogo and we're just going to say package parser like so okay now what we want to do is Define what a binding power is so we're going to say type binding power which is an ins and if you recall from our intro to the video um we defined a few different types of binding Powers so I'm just going to come over here copy that and here you can see the different binding Powers which we will be using we had a default binding power which is zero and it goes up to primary which is 10 now these binding powers are how tightly a certain token or tokens in a certain group um bind so for example things like primary which would be like a number or whatever bind very heavily multiplicative binds tighter than relational and additive Etc so what we want to do is Define these binding powers and this is how we're going to do it so we're going to have a binding power enum basically perfect um now what I want to do is go ahead and Define three different types of types now uh let me may also not copy it from here this should be EST there we go like so Okay so we've defined The Binding power it's just an enum like so then what we want to do is we Define what a statement Handler is a nud Handler and a let Handler these are basically just functions so we're going to create a function to parse every single type of token that we can think of and these are going to be the ways we do that so um I'm also going to go ahead and Define four different types of lookup tables uh again lexer is like so so we have a statement Handler which takes in a parser instance and returns a statement we have a nut Handler which takes in a parser instance and returns an expression a lead or um left denoted Handler is going to take in a parser the left denoted expression that we've already parsed in a b power and it's also going to return an expression then we just have a map for each of these types taking in a token kinds and returning that value so the key is going to be the token kinds and the value is the Handler itself same for binding power it's just going to return the integer value of that binding power and with this we can actually then in the global scope create four new lookup tables like so so we have a BP lookup which is this one nud which is this one Le and statement now what we want to do is also create a few helper methods so that way we can actually go ahead and create different types of um so that way we can instantiate for example a binding power lookup lead lookup nud Etc so what we want to do is Define something in here for a lead function so here we're creating a function called lead which just instantiates the binding power lookup of that token kind to be The Binding power and the lead lookup kinds to be a lead function so it takes in a function as an argument we then have two more similar functions for nud in statement so we have a lead a nud and a statement like so so now that we have all these we can actually create a function called uh create token lookups and this function won't actually return anything but what it'll allow us to do is start setting up these parsers now so let's call this function from inside of our parser so when we call create parser right here what I want to do is first call create token lookups like so let's go back to create token lookups and start figuring out how we're actually going to start doing this right so what I want to do is first handle the case of a number so when we reach a number how do we want to parse this well for this uh we're going to want to create something over here there we go so when we go into the create token lookups let's create something for literals and symbols like so and a number is a literal so what we want to do is say a nud of number so a nud for the number it has a binding power of primary because a nud is a primary expression and the function is something like this so the function is going to return an expression in our case we basically want to get um the current token right so what we want to do is we want to call a function like we basically want to get the current token kind right so we want to get the current token kinds so let's just switch um P dots current token kind and what we want to do is if the current token kind is a number which we already know it is here but I'm trying to generalize this so we can use this exact same function for all of the literals and symbols then if it's a token kind of number for example then we want to try to parse the number using St Str CV dot um parse float and this takes in the string so we're going to do p.

[00:27:18]Advanced do value and the bit size which is 64 like so and this should return a Floats or it could error in our case we're not going to check ER but it could and once we have this number then what we can just simply do is type return as.

[00:27:36]number expression or the value is the number like so and this right here is how we can parse numbers so one thing we could do for example right is we could just do this we could create a lexer Handler for the number we copy this copy it three times and here we'll do it four string and for symbol Elixir do identifier there we go right and then for string we could just do this so we could actually just remove this line because for Strings we don't have to do any parsing right whoops there we go and we can just say string expression the value right is um going to be p. advance. value and we can just copy this as well and change this to ident uh symbol expression now if you notice the issue here is that it's basically the same code we've duplicated three times ideally we want to create some way to do this uh more generally for all primary Expressions so let's go into the expression. goo and handle this the way we would like to do it so we're going to have parse primary expression it's going to take in a p a pointer to a parser and it's going to return an ax.

[00:29:10]expression I need to import EST and what we're going to do is we're going to do that switch case I was trying to do earlier and we're going to switch on the current token kind if the case is a number token right if it is a number then we're going to do what we were doing before so we're going to get out the number like so right and that is our case if the case is not a number and it is a string then we need to handle it the way we handled the string right I'm just going to paste this and I'm also going to sorry go ahead and try the case for if it is an identifier and we had identifi uh not identifier sorry symbol and like so so these are the three cases we then want to have a default case uh default where we just panic and what we're going to do is we're going to do an fmt dos prints F and we're just going to say cannot uh create [Music] um cannot create primary expression from bra s back sln and what I want to do is do lexer uh dot token con string of p.

[00:30:44]Curren token kind like so so we're basically just going to say hey if we're calling this and it's not a number a string or an identifier let's just throw an error saying hey canot like this doesn't make sense right and now now what we can do is just use this singular function here in place of all of these three So currently where we were doing this right it took in a nud Handler what is a nud Handler well a nud Handler is a function that takes an a parser pointer and returns an expression that is uh this right takes an a pointer to a parser and returns an expression so now what we can do is we can just come in here and just put that there for all three of these and we can delete that [Music] line like so and just like that we now can handle numbers strings and identifiers in our language so whenever our parser encounters a number string or identifier they can all share the same function just by using this so we switch on the current token kind the current token kind is either a number a string or identifier for us to get to this point and then we just parse it as we expect return the value and voila now one thing you're probably wondering is how do we parse binary Expressions right so how would we parse um the plus and the multiplication and all that well glad you asked so what we want to do is go into the lookups and Define a few things for binary Expressions right so what I want to do is Define our logical relational additive and multiplicative binary expression handlers so first we're going to do uh logical and what we're going to do is we're going to do lead so we did nud because a number or all these things they don't have to have something to the left as you can see right here they don't expect it however pluses and stars and all that they expect something to the left so we do our lead um left denoted stuff so first we Tak in the token kinds um for a logical let's do ANS first let's say it's of type logical and the function Handler for this is going to be parse binary expression we haven't defined this but we will in a second so let's define the other three logical operators which is or and Dot dots this isn't necessarily A logical operator but dot dot syntax is the lowest precedence operator so if we see something like this 10 dot dot um math right that means we want to iterate from 10 to this whole quantity so this requires this to have a super low precedence to be able to parcel that so um that is the logicals next we have uh relational really t i o n a l can't spell and these have a similar thing so we're going to do lexer do less uh it's going to be a relation this time and again parse uh binary expression I'm going to copy this um a few more times we're going to have less less equals greater greater equals um we need equals as well and not equals I I missed one like so and these are all relational operators again we haven't defined pars binary expression but we will once we Define the rest of these lastly we want to do attive and multiplicative so if you notice something here logical has a binding power of three relational has a binding power of four additive has a binding power of five and multiplicative has a binding power of six so this is why we're defining them like this because if you recall from our table at the beginning of the video um these are the opposite of the order of Precedence so for example a logical operator has the highest precedence while something like a multiplicative has the lowest precedence so U let's now go ahead and Define our additive and multiplicative so we're going to do lead we're going to do lexer dot uh let's do plus first for ADD it is a additive beautiful and what we want to do is do parse uh binary expression we're going to copy this and this is going to be minus uh we call it Dash right then I'm going to copy these two and we need to Define one more so for additive and multiplicative um these are the two additive next we need to do multiplicative for Star slash and uh percent for modulus right so most languages uh these are multiplicative in most languages a percent has the same precedence as star and slash they're both on multiplicative operators so there we go this is how we Define additive and multiplicative expressions and you notice all of these all use the exact same method parse binary expression which again we haven't defined yet but we will right now so let's go into expressions. go here's parse primary so right above it I'm just going to we'll go right below it actually um but right below it what we're going to do is we're going to Define parse binary expression now if we recall what this has to be this is a nud we are dealing with L or lead sorry right so it takes in a pointer to a parser it takes in a left which is an as um uh. expression and it takes an a BP which is a finding power and returns an EST do exper like so okay now what is this how do we handle this well if we think about how um a binary expression works by this point that means we've we' already hit the left thing so first thing we need to do is get the token or the operator now I'm just going to do operator token is p. Advance why Advance if we recall Advance eats the current token and returns it so this is now a token beautiful now what we want to do is we want to parse the right hand side we haven't defined this method but this is the next one we're going to Define and it takes in the p and The Binding power and then once we're done we just do return binary expression where the left is well the left the operator is the operator token and the rights is the right like so now the only thing we have to do is Define this method right here and then we're completely done with our parser so let us go ahead and actually you toine are arguably the most important method in the entirety of the prep parsing so uh let's go oh we already are in Expressions so I'm just going to minimize this and at the very top we're going to Define this method and it's going to be a function it's going to be called parse expression and it takes in again a pointer to the parser the reason we take in a pointer is so we can mutate it and it takes in a binding power which is again a binding power power and it returns an a. expression so this will always parse an expression at wherever we're at now what we want to do with prep parsing is first we uh parse the nud it assumes that if there's nothing to the left then you parse a nud then while we have a lead and the lead uh and the current BP um and the current binding power is less than the BP of current token we want to continue parsing left hand side this is the whole principle behind prep parsing and I'm going to walk you through it now so first thing I want to do is I want to get the current token kinds and what we're going to do is we're going to do p do current token kinds like so next things first I want to get the nud function and I want to check if it exists and the way we're going to do this is we're going to do a nud lookup of the token kinds like so and if it exists this is a Boolean and this will return the Handler for the current token we're at so what is this doing well if we look at our example of 10 plus um 6 * two the current token right the first time we call Par expression is a number so it's going to check does the nud lookup contain a function for a number well if we look in our lookups we see we've defined a nud for numbers strings and identifiers good so that means this will exist so first thing we want to do is we want to check if it does not exist if it does not exist there's a problem we should have this exists so we're going to do panic and what we're going to do is we're going to do an fmt dos printf and we're just going to say nud [Music] Handler expected for token percent s s back sln and what is the token well we're going to do a lexer do token kind of p uh what is it current token kind like so so if it does not exist we want to get out of here this should never happen as long as you have valid syntax now you could produce a better air message but that is up to you if you held on to the locations of the position inside of the Tok construct for example you can hold on to the line number the start and end positions you can produce a lot better errors than this right here so if it does not exist we do that if it does exist right then what we want to do is parse um whatever the nud Handler is for this token so for number it's just going to return that number so what we're going to do is we're just going to call nud function and we're just going to pass in the parser which is p and this right here is going to return the as for a number in this case and by doing so it's going to advance the position from here to here now now that it's Advanced that position what we want to do is iterate over the current tokens in The Binding power lookup of p. current token kinds notice this is not going to be the same thing as this once we call the nud function Handler we're going to advance so we will be at a different current token kinds so we started at 10 this now contains a numeric literal of 10 the current token kinds will be plus so we're going to iterate we're going to get the current token kind's binding power so The Binding power of Plus is additive we're going to get that binding power and we're going to just make sure it is greater than the current binding power now the reason we do this is we need to always try to Traverse right if we don't if we do not always try to Traverse right here we will have issues with expressions like this where this side of the tree is lighter than this side so this is what we do we say hey keep traversing and keep parsing left as long as the current binding power of what we were already parsing when we got here so by default this will be default keep traversing right now what is that going to do well what we're going to do is we're then going to say token kind is equal to P do current token kinds we're then going to get the lead function which is again we're going to have an exists like so and we're going to do lead uh lead lookup at token kinds like so we are going to basically copy this statement right here and if this does not exist now right so if this does not exist it is not a l or nud sorry it's a lead now right and we just do that lastly what we want to do is we want to replace this left with the new left so this is how we unroll a recursion all all the way through and we're just going to say left is equal to lead function where we pass in p and it takes in the previous left this is why this works it takes in the previous left so we're going to pass in left and The Binding power is BP because we want to make sure we keep um using this binding power all throughout then once we're done do not mean to do that once we're done we can just return left now let's quickly go over how this actually works in the real world so when we first called us assuming we pass in a binding power of zero which is what we'll do in a second it's going to hit 10 uh the first token kind is going to be number the token kinds is going to be checked it's going to exist so we're going to have the number Handler if we recall the number Handler's price primary expression it's just going to return an a. number expression so that will be left here here as. number expression will be in the left the position because when we do that right we advance so the position is going to go to this token now so it's going to be at plus what it's going to do is it's going to look up The Binding power of the plus token if we look in the lookups The Binding power of the plus token is additive five okay okay is five greater than zero AKA is it greater than the default binding power yes yes it is cuz zero is obviously less than five so we get the current token kind we already know we're at a left or a plus here so now we do this we get the lead function does the lead exist for a plus well as we saw here it does we've defined the lead which uses parse binary expression so we go back in here and we know this is good so we get the left hand side now we then call lead function passing in our previous left if we recall at this iteration this value is the left of the plus token it is a number expression we then call because our current token is a plus we then call binary right so this is a number this is zero we're going to get the current token advance past it so this is the plus token the right hand side what we're then going to do is repeat this process so now the right hand side now all of this has been parsed it's going to get a six nud boom it works beautiful what's going to happen is we're going to check if it exists it does this is going to be a number expression we're then going to try the right hand side it's going to be a star it's going to parse in until eventually there is no binding power for anything less than us so we're just going to return the left the 6 * 2 will be a uh binary expression which will get passed back through here as the right hand side then this will be able to return out a b expression where the left is the number the right is the plus and the right hand side is another binary expression and this right here is how we unravel the recursion instead of doing recursive Des sense manually um we use this technique of prep parsing to do it so now that we're almost done we are almost done we are so incredibly close now what we need to do is actually call parse expression as we don't ever really do this instead what we do is right here we call parse statement well parse statement we have haven't implemented so let's go ahead and finally Implement par statement so what we're going to do is we're going to do an stmt uh function we're going to check if it exists and just like we did with here we're going to do a lookup and what we're going to do is we're going to do the stmt uh look up and we're going to check the P.C current token kind if it exists then what we want to do is we just want to do return statement function passing in P like so so if we had a syntax like this uh let x = 10 let is a reserved keyword so we would Define a statement handsel for we would get here however if we just have this 10 + 5 right there this 10 is not a statement it's a number so we will go past this and what we're going to do is we're going to do expression P do uh parse expression we're going to do p and The Binding power will be default then we're going to do p. expect which we haven't created but we will in a second so we're going to do uh p. exect and what are we going to expect well we're going to expect a lexer DOT semicolon like so and then we're just going to do return expression statement where the expression is the expression here beautiful now let's just go ahead and create p. exect so we're going to go to the parser Dogo and we're going to create a few little helper functions to allow us to expect a token and produce a nice little error so what we're going to do is first we're going to create a function which is a parser and it's going to be called expect error like so and it's going to take an expected kind which is a token kind and it's going to contain an error which is going to be anything and expect is kind of like Advance it's going to try to advance and if it can't it'll throw an error but it will still return the token kind to a atat so what I want to do is I want to do token P dot Uh current token then we're going to do kind P dot uh sorry not token do kinds like so if the kind is not equal to the expected kind right then we we know we have a problem here right so if it makes it to here that's bad if it doesn't then we should probably just do return p. Advance right so we're just going to advance and return the value okay if this is an issue then what we need to do is we need to create an error but first we need to check if there's already an error that's been passed so let's do if error is equal to nil meaning we didn't pass a default error we want to produce our own kind of error so we're going to do error colon equal to uh fmt dos prints F and we're going to do expected percent s but received percent s uh instead and then backlash on like so now expected well what did we expect well we expected token kind string of the expected kinds right so I'm going to just zoom out a little bit so we can see this better so we expected a string what is the String the token kind string of what we were actually expecting and what did we receive well we received a uh lexer token con string of all kinds like so so this is just a nice helpful little method to generate an error string um if we didn't pass one into this function like so so if we passed in anything else then what we're going to do is we're going to go ahead and call Panic a like so and uh oh I need to assign like so there we go perfect and this is our expect error function now down here we can define a function uh p parser and then we call it expect and this is going to be expected kind is a token kind and the error is going to be nothing because this is just going to be our general Helper and we're just going to do lex.

[00:52:45]token and all we're going to do is we're just going to do return p. expect error we're going to pass an expected kinds nil like so so if we want to give a custom error at some point we can call expect error if we just want to generally say hey I expect a token we can just say this and that's what we're going to do so if we go back to the statement we say hey we're expecting a semicolon if anything other than a semicolon is the current token while we try to advance past it it'll throw an error and that's basically all we need to do um to handle this so this is now going to be our parser so so let's now go ahead and actually give this a try and go to the parser go and let's take a quick look and just make sure we call parse um inside of the main.go file right so here we have the tokens and what I'm going to do is I'm just going to do as colon equal uh parser dop parse and we're just going to pass some tokens like so and this will give us the a um very nicely now what I want to do also is um I want to print out this a and it's kind of hard to do that by default using GH standard Library so what we're going to do is we're going to do go uh gets and we're going to do github.com [Music] sanity.io slash litter hit enter and it's going to add this package to our go.mod right here and that's beautiful so now that we do that uh let's go into the go Main and what we're going to do right inside of the main is we're going to use this package um called litter so we're going to do litter dots we're going to call um dump we're just going to pass in the EST and this is going to very nicely print out our EST so let's give this a shot so let's just do go run source main.go and look at that that is a beautiful right there so let's kind of look through this and just see what it looks like right so we have a block statement as we expect we then have the body where the first element is an expression statement why is an expression statement well if we look through here it's because it's a semicolon in fact if I remove the semicolon we get this Panic expected semicolon but saved end of file instead and you can imagine how we can improve these errors to show the line number show a snippet of code Etc instead of panicking but if we run this again we get that so the left is the value of 45.2 yep that looks correct the operator is plus lovely the right hand side has a binary expression of the left of five nice star and right of four so we can see that the Precedence is indeed prioritizing the right hand side because this has a higher binding power than the plus so uh I hope you found this video useful this is a lot to takeen so feel free to um review the video watch it again uh I will leave a link in the description down below to this code right here as well as a link to my Discord server where if you have any questions feel free to directly reach out to me I am very frequent on there always asking or always answering questions and I love to talk to you guys so I will talk to you in the next episode where we will actually talk about variable declarations and we'll learn how to complic uh parse some more complicated ests and then it'll be a lot simpler now that we have the lookups defined basically all we have to ever do to parse a syntax is Define a nud a lead or a statement function and then just create that function like this so just as it was this easy parse binary expression works because we created it and now all of these can get parsed by one function so uh I hope to talk to you in the next video in the meantime happy coding bye