Writing a Custom Language Parser in Golang: Tokenization

[00:00:00]what going on everyone my name is Tyler and welcome to my Channel today we're beginning a brand new series where we're going to be writing a pratt parser using the go programming language it's been long requested and long awaited that I continue my interpreter series but I figured I would actually focus on writing parsers so in this series we're going to be writing a parser for a syntax like the one you see right here the syntax is pretty modern it includes objectoriented principles classes um static types implicit and explicit types meaning there will be type inference it'll include array in string literals as well as common control flow patterns like if um for each and switch statements and it'll include Imports all of these combines will give you an idea of how to parse basically any syntax that you want to come across or that you want to create um to get started with parsing the first two episodes of the series we're going to be working on tokenization tokenization is the process where we take the source code and translate it into tokens so for example let nums would produce a tokens of a let's token and a symbol token where the value is nums and you can see how this would continue on um for an entire source code so the goal of tokenization is to split up the source code into um meaningful tokens that we can understand and then use with parsing into the As and a stands for abstract syntax tree it is a tree data structure which we're going to be using to represent our program so ests are incredibly powerful tools and that's what we're going to be focusing on with this series is how do we create an as the process of creating an EST is pretty simple in general we build the lexer which again we're going to be focusing on the rest of this video and the next video overall it should take about 40 minutes um of the video time to create a lexer and and then the rest of the series should be focused on parsing once we have this parser we can then do a lot of things with it such as code generation interpretation type checking and a whole bunch of other stuff this series is only covering building the parser but um the next series is going to be on interpretation or compilation I'm going to kind of see what people want in the comments and on the Discord server and I'm going to go down whatever route is most popular so even though we're not going to be building a functional language where you can actually run the code this will be a building block because to run any code you first actually have to build an EST to build an interpreter you have to build an EST to build a compiler you have to build an EST so this language series is incredibly important to get into language development um the objectives again for the series are building a tokenizer using popular um constructs such as regular Expressions we're going to be building a prep parser using the prep parsing technique um and you'll be able to apply all of these skills that you learn in the series to write a parser for any language so you'll be able to modify this parser and have the skills needed to build a parser for any language and any syntax so without further Ado we're actually going to get started right now constructing our lexer which we'll be using for the rest of the series okay so without further Ado let's actually get started by writing the source code for our lecture so what I'm going to do is I'm going to open up the terminal and I am going to create two folders so we're going to do make dur and we're going to create source and examples like so and then inside of source we're going to create a file called main.go we're also going to make a directory of source SL lexer and for now that will be it for our source um I also want to create a file inside of examples um for our source code that we're going to be testing so I'm going to go here and touch uh examples z.l and this is simply just going to be the code we're going to be parsing uh throughout the series and 0 is obviously going to be for this episode 01 for the next episode Etc so for this series um we're going to start in two stages by working on the lexer so without further Ado let's actually start by creating something I want to be able to Lex by the end of this so let's say um an expression like this we should have a 10 token a star token a two token as well as a semicolon token um if I add a minus these should also be two separate tokens so we're going to start really simple with something like this and then we're going to add plus parentheses 2.4 - -2 right something like this is something we expect to be able to Lex by the end of this episode so let's go into the main.go and let's give it a package of Main and actually go ahead and um print out this code so we're going to give it a package of main a funkman and then what I want to do is I actually want to read this file so I'm just going to call it bites uh and error we're just going to do os. read file and the path to this file is in terms of the directory we run it in so I'm just going to do slash examples SL z.l and then we're just going to do source is a string representation of bytes and then let's just say I want to print this off real quick just to make sure everything's working so I'm just going to do an fmt printf we're just going to print the code like so so like so and then now I should be able to do go run source main.go and there we go we can see the code perfect so uh what I want to do now is I want to go into the lexer and I want to create a file called tokens. go this is going to be a part of the package lexer and we're going to actually start defining um what are uh tokenizer really is so um let's actually get started with this and Define what a token is so um to Define what a token is it's uh really quite simple so we're just going to define a type of token and this is going to be a structure and it's going to have a uh value which is a string so this is the actual value of the token so for example a token of plus would have a value of the underlying um plus token right and then it also has a token kind which is simply uh sorry that's not the uh value it is kind of token kinds and a token kind for us is just basically going to be an enum so we're going to Define uh token kinds to be an ins to keep it nice and simple and then we're going to do const uh open parthy and we're going to find the different token types um like this so uh we're going to start with the eof um which is a token cun and this is going to be Iota which just allows this to keep counting upwards from here so this will start at zero if I Define something like Foo um you can see fu is one Etc it's basically just doing what an enum does in most languages so um let's define all of the token CS for example there's number there's string uh not like that there's identifiers um we also have things like grouping tokens so an Open Bracket a close close bracket open uh curly close curly open pen close p uh we'll then have things like equivalency tokens like assignment uh equals uh not not equals Etc um we will then have so for example an assignment token is just an equal sign right a um equals token is two not is obviously uh like this you you get the idea um so that's basically all we're doing right now is we're just defining all the tokens we're going to be dealing with um we have less less less equals [Music] greater greater equals or and um dots dots dots so our language will support the dot do ellipses operator so something like 0 do do10 um will be a syntax so dot dot is the ellipses operator for us um we'll also obviously have things like semicolons uh colon uh question uh we'll have things like commas um plus plus uh which means we'll also have a minus minus um we'll have plus equals minus equals um and you would obviously want to add in here things like um slash equals and star equals I'm not going to be adding these in the parser or lexer but because they're literally identical to these how they're handled so I won't be adding these but I just want to demonstrate that you will want to add those uh um yeah perfect so let's also continue on and add the uh mathematical operators so that's something like plus um we will have uh what will we have uh Dash we'll have slash which is for division we will have star and percent for modulus and there we go so these are all of the operators of our language including identifier strings and numbers as well as um symbols and grouping expressions and then now we'll actually Define the reserved keywords so things like let const um things like class new uh Imports um from uh FN h if else uh for each uh we'll support while Loops uh for Loops as well uh we have exports type of and in as well uh like so so there we go um so these are all the reserved keywords so this is is all of the token kinds so there are a total of uh 50 um different tokens so yeah exactly if you just create all the different token kinds this is what makes up a token we have a kind and a value so now that we've defined what a token is let's actually um continue and Define um a helper method so we can debug these tokens so first things first um we're going to need to have a function which is basically method it's going to be token token so this is going to be called debug and it is going to return a string uh actually we won't have a return a string sorry about that so what we're going to do is we are going to check if the token do uh. is an identifier or the token.

[00:12:56]kind is a number or the token. kinds is a string if it is uh then what we're going to do is we're going to just do a print F and what we're going to print is percent s and then space percent s like so and then a back sln and the format we're going to do is we're going to create a method to actually print the token kind which is going to be token kind string and it's just going to take in token. like so um and then actually the token. value will be the last thing so there we go um that is the case if it is an identifier a number or string uh if it's not then it's even easier because all we need to do is do an fm.

[00:13:51]printf and we just do percent s open print close print back sln and these tokens uh also we're going to use the token kind string method that we haven't created but we will uh and we're just going to pass in the kind so there we go that's basically all the debug function does um and let's now go ahead and actually create this token kind string method uh that you see right here so we're just going to do Funk uh token kind string and it's going to take in a kind which is a token kind and it returns a string right so there we go um now the compiler's happy so let's actually go ahead and Define uh this function and I will go ahead and copy this from another monitor uh because I do not want to be typing this all day long but um as you can see uh we are just defining oh did I miss semicolon wait um semicolon semicolon I did there we go there we go right so um basically I am just doing a giant switch case over all of the different tokens which we support so eof right we go to where eof is number string identifier and we go to a number string identifier and basically it just Returns the string representation of the enum itself since go does not have enums um we can't just print off the text number we have to actually do this ourself so this is just a simple helper method it takes in the token kind which if we remember is an INT um and it returns a string of what that int represents so I'm just going to go ahead and minimize this um but it's basically just a ginormous switch case uh next I want to create a function uh let's create it above called new token and it's going to take in a kind of token kind and a value of uh string and it's just going to return a token like so so we're just going to do return uh token and we're just going to do kind comma value like so and this is just going to be used to actually create a token right um so now that we have this uh let's also go ahead and create um one more method which I want to use because it will uh simplify our code here as well as a whole bunch in the parser so what I want to do is notice how we have to do this check if the kind is an identifier or token kind is a number or token kind is this really ideally we' like to have a function which is just a part of token where we can just really quickly have this written so I'm going to go ahead and Define a function for this and this is going to be token and it is a type token right and we're just going to call it is one of many and it's going to take an expected uh [Music] token which is dot dot dot uh token gun and it's just going to return a bull so this is a varic function it takes in um a whole bunch of different tokens and if the token kind of this token is any of them it will return true so we're just going to do four um we don't actually care uh about the index so we're do index comma expected and then we're going to do a range of expected tokens so we're going to iterate over each token kind and we're just going to check if the expected is equal to. if it is then we just return true right um and by the end of the slop we just return false if we don't have it now this function may not seem like it's very useful but even in a simple situation like this we can simplify this if statement to just be if um token uh token do is one of many and pass an identifier comma number comma string and that handles all of this so it just simplifies our code just a little bit and there we go so now we have a nice clean elegant way um to actually handle multiple check on a token so that's all I really wanted to do for that um so now we've actually gone ahead and created every single thing we need for this episode um so let's actually go ahead now and go to the tokenizer Dogo where we'll actually start writing the tokenizer so now we have these token structs um and some methods to print them create them debug them and let's actually now go ahead and create the uh tokenizer or lexer and this is a part of the package of lexer so uh what we're going to want to do is we are going to want to do two different types of imports so we're going to be importing fmt because we use that a lot and we're going to be using the r uh Library which is built into go so let's actually go ahead and create a type of lexer and this is a structure like so and what we want to do is Define a few fields here so we're going to do a tokens which is of type uh token slice we're going to define the source code as a private member and this is a string we're going to define the position which is an integer like so and for some reason it's not formatting my code there we go um and there is also one other type which is the patterns which is a array of rejectx patterns now what is a Rex pattern well a Rex pattern and this should be a n Rex pattern is a structure which contains um two Fields it contains a Rex which is going to be a pointer to a regular expression. regular expression so this is going to be the actual regular expression which matches a certain type of token and the Handler which is going to be a Rex uh Rex Handler now what is a regular expression Handler um don't worry these are the most complicated parts of this entire project once you to see what a regular expression Handler is and how we use it hopefully in a couple minutes um this will become a lot more clear but for now you're going to kind of have to hang in there so a type of regular expression Handler is a function which takes in the lexer and we're just going to call it Lex which is a pointer to the lexer so it's a mutable reference CU it's a pointer to the lexer and it takes in a regular expression um which is going to be a regular expression. Rex like so and it doesn't need to return anything it's basically going to be for every regular expression we'll have a Handler that handles that particular regular expression and we'll add that token to the lexer so let's actually see how this is defined cuz I'm sure it is a bit confusing so um let's go ahead and actually Define the tokenize uh method um yeah let's get started with that so we're going to have a function uh there we go a function called tokenize it's going to take in some source code which is of course a string and it's going to return an array or slice of tokens um what we're going to want to do is we're going to want to create the actual lexer instance so I'm going to create a function called create lexer and pass in the source code like so and at the very end uh for now we're just going to do return Lex do uh tokens like so now let's go ahead and create this function called create lexer and let's see how we actually Define this so uh create lexer is a function which takes in some source code which is of course a string and it returns a pointer to a lexer like so now what this function does is it simply Returns the pointer so a reference to a lexer object like so and we Define the position to be zero uh we Define the source to be well the source ah um we then Define the [Music] tokens to be a empty slice by defaults um and then the patterns is an interesting one because this is um a little bit more complicated so for now um what you can see is this create lexer just simply instantiates the lexer and in here we will Define all of our patterns like so so um I'll show you how that works in a second I'm trying to get through this there's a lot of complexity that kind of goes on with this but once you see it I think it'll be a lot more clear so let's first Define the pattern for something super simple like an open and a close bracket just so we can see how we're going to be dealing with this so let's define a pattern for a reg an open and a close bracket so uh we want to be able to par something like this and something like this so let's to find a new entry so we're going to have a comma here and a pattern if we recall from the Rex pattern has a regular expression and a Handler in that order so the regular expression we're going to use the reg x.m compile and it takes in a regular expression string and it will compile it we know all these are valid regular Expressions at run time or at compile time so this is fine and the regular expression we're going to use is back slopen bracket like so so this um right here is a regular expression to parse the Open Bracket right next we're going to define a default DF UL andler which is going to take in the Open Bracket okay and it is going to take in the Open Bracket value like so now the only other thing we have to do is to find this default Handler so let's just Define that and uh to define the default Handler uh what we're going to be doing is we are going to have it taken the token kind so this is the uh kind which is of course type uh token kind um and it's going to take in the value which is a string and what it's going to do is it's going to return a Rex Handler which if we remember is what Rex patterns are it takes in a Rex and a Handler so the default Handler is basically for all the tokens which we know how to parse immediately at run at when we see them right there's no ambiguity with how to parse this if you see this you know it's an Open Bracket with a open run like so so um all we do really is we just return an anonymous function which I'm just going to have it autocom completed right it takes in the lexer and the regular expression and then what we're going to do is we need to advance uh the Lexus position past the value we just reached so I'm going to define a me a method like lex.

[00:26:21]Advance n and n let's just say is the length of value right and this method will toine in a second and then we also need to do some sort of like lex. push which is just going to call um new token and it's going to take an a kind of kind and a value of value right so let's define these two methods uh push in advance end and you'll see these are both incredibly simple methods for the Lexus so we're going to do Funk um Lex and this is a lexer and these are all going to be mutable we're just going to do the advance n method and it's going to take in an in N which is an integer ands it's basically just going to do um what it sounds like it's going to advance the position just past n bytes so we're going to do lex. position plus equal n and that's all this method does let's also Define the other method which was push which if we recall takes in a token to push like so um and this method is going to take in a poke take in a token and do Lex uh and we're just going to do a pens lex.

[00:27:46]tokens comma token um and then we need to do lex.

[00:27:53]tokens equals append like so so we're just appending this token onto the slice and it returns a new slice which we're assigning to. tokens like so um let's also quickly Define a few more helpful methods like at which is a function which again works on a lexer pointer and this is simply going to return um the bite at which we're at so I'm just going to have it um take in nothing it returns a bytes and that's going to be return uh Lex uh what would it be it would be lex.

[00:28:37]source of lex. position like so and this just Returns the meth uh the token Rec currently at and I'm going to copy it and we're going to Define another method and another method this one is going to be called remainder which is going to return a string and remainder is going to return the remainder of the string from the position so we're just going to do lex.

[00:29:02]Source from uh lex.

[00:29:06]position to the ends like so so this is just going to get from the The Source from the position index onto the end um at we're going to create one more method called at eoff which is going to return a Boolean and this is going to return whether lex. position is greater than or equal to the length of the source like so now with all of these methods um we can actually now completely build the rest of the parser so um we have this patterns array which defines one pattern currently the pattern for Open brackets and you can see we call default Handler which literally just returns a function that parses this specific token right so it's it's pretty simple with that regard what we're going to do is we've defined a lexer in our uh create lexer method so what we're going to do is we are now going to do uh we're going to iterate while the Lex is not at the end of file right so while we still have tokens left with us um so iterate while we still have tokens while we still have tokens what we want to do is we want to Define a variable called matched which which is just going to be false by defaults and we're going to do four and we're going to iterate over every pattern and we're just going to iterate over every single pattern now why are we doing this basically what we want to do is at our current position right so let's imagine we have a string like 10 + 5 what we're going to be doing is we're going to start at the current token right our position is going to start at zero and we're going to start here what we're going to then do is we're going to apply every Rex in the patterns array first we're going to try say the Open Bracket it's not going to succeed all the way to the end so then we're going to keep iterating until we don't find a match or we find a match and then we call the Handler method for that match so let's actually see how that works so let's get the location of the match and we're going to do uh pattern Dot and we're going to do Rex dot uh find uh where is it string index and we're going to pass in the lex. remainder like so so this is going to attempt to parse every single bit of the string until it finds a uh match and then we're going to return the location of the first match so if um ah if if uh the location is not nil that means it's found right and the location's first match is equal to zero so this location at index Zer Returns the index of the first match it has to be zero because that would mean it found it right at our position if say we're trying to parse 10 right and the first thing is let's say there's a Open Bracket here for some reason right like it's an array or literal or something well the Open Bracket will match 100% right so it's going to iterate through the patterns array and if we look at lex. patterns um the first pattern is a Open Bracket so it's going to match the first thing in here is an Open Bracket it's going to match an Open Bracket at 0 1 2 3 4 5 so it exists this will pass but this won't meaning we actually need to find something to pass for this so that's why we're doing this check right here um now what we're going to do is we're going to do pattern do Handler and we're just going to pass in The Lex and the um pattern. Regular expression which we just tried we're going to set the Matched to uh true and we're going to break from this Loop uh right here because we've already found the match and then the pattern. Handler is going to build the token that it just matched for and push it into the lexer right so at the end of the for Loop we need to check if we did not match right so if we didn't match we should panic and I'm going to do an fmt dos printf which is going to be a print of a format string and we're going to do uh [Music] lexer uh error and I'm going to just say something like unre Ed unrecognized token near and then I'm just going to print out um the uh remainder of lex. remainder like so so this is just going to be a really basic error message you should obviously uh could extend this uh like so so so you can for example print the location that's occurred um and give a better airor handling description so that way the user actually knows what's going on um but for us we're just going to do very basic error handling because the point of the series is not how to handle certain errors it's how to parse and Lex in this case so this is the entirety of our tokenized method except yes we're missing one last thing um we just need to do lex. push and the token we're going to do is we're going to do a new token where the token kind is eof and the value is eof because this means we have reached the end of file right while we're not at the eof we keep running this through so we always add a token called the end of file just so that way the parser knows when we're actually at the end of the input so say there's 100 tokens in the input there'll be 101 tokens that the lexer will produce always um so this is the entirety of the tokenizer now um what you'll notice is this won't work um for anything other than syntax which just has brackets because right we haven't defined all of our um where is it sorry right here we haven't defined all of the other rules so for example that is how you do an Open Bracket here is how you would do a close bracket again it is identical uh close bracket right and basically what we're going to do is we're just going to go ahead and Define all of our um hands so I am going to be lazy and copy every single Handler but you can pause the video and type these out if you want again I am just defining all the handlers for every simple token that we have in our language Open Bracket close bracket curly parentheses equals right to equals not equals Etc now one thing I do want you to note and this is actually really important um with this type of parsing strategy the order of which we Define the patterns is important so what I mean by that is something like equal equals has to come before the simple equals right here if I switch the order of this it would create two assignment tokens instead of one equals token so the order is important here but if you just look at this right here um this is all of the patterns we're going to be defining today and in the next episode we'll actually be defining five more which will completely finish out all of our Lexing so um our goal today right is to be able to handle numbers and all of these so the only thing we don't handle right now is numbers so let me go ahead and Define the number Handler right so I'm going to go ahead again and I'm going to copy the regular expression for numbers like so and again numbers are defined like so so we have 0 through 9 including but not limited to where we have a single decimal somewhere throughout so this is how we'll handle numbers so I'm going to go ahead and Define this number Handler function uh down here so let's actually see how do we handle numbers right and you'll see it's very simple number Handler is a function which takes in the instance of the lexer a mutable instance mind you and it takes in the Reg x uh rex. regular expression and it does not return anything ah there we go right and what we do in here is we can all agree that by the time you hit the Handler right we know for a fact the location is already zeroed out with our position and we know for a fact it exists that means when we call into Handler right we're passing in the pointer to lexer in the regular expression that just matched already we can make some assumptions about the quality of this Handler we don't have to do as much error checking in these handlers because we know it's always valid so what do I mean by that well I mean let's get out the match that we just reached right so to do this we're going to do Rex ah reg X reg X dots and what we're going to do is we're going to call a method called find string um and I think it's just fine string if I'm not mistaken yeah okay takes in the string and it uh matches it so we're just going to do lex. remainder like so this is the actual string that was matched for our our number so this is the pattern that matched that what we're going to do is then I'm going to do a Lex stop push and we're going to push the new token of number comma match like so then we're going to advance n the length of match and this is how we handle numbers it is very elegant very clean using regular Expressions so uh let's now try to go ahead and actually run this code and see if it works so without further Ado let's go into the main.go we already have the source code right here so I'm going to just get rid of this and we're going to do tokens ah tokens and that is to uh to lexer yeah I should probably for some reason it's not finding it okay so that's fine uh one second we will need to bring in the lexer which is for some reason not Auto completing for so let's just see what's going on here so let's just import the lexer package to do that we're going to do github.com [Music] sltp SL um parser [Music] lexer right and okay and then we're going to [Music] do there we go it found it lex. tokenize and we're going to pass in the source code like so and hopefully it finds it tlb parser dser slle and tokenize should be a public method one second [Music] it is it's beautiful and let's see if it can find it uh why did it not find it let's go to the go do oh I see why it didn't find it because I never defined this package right here so I need to do go um mod and nits github.com tlby parser parser series like so and now if we look at this it should go get it and it'll literally just find it right there so let me just retype this we should just do lexer and there it is lexer dot um tokenize like so we pass in the source code and I'll just actually simplify this by doing string of bytes like so and there we go now we have all the tokens for our language so what we're going to do is we're just going to for Loop loop we're going to iterate over every token and here we have a token so I'm just going to call token do uh debug like so and let's just see if this works so hopefully it does uh since I haven't had ability to test this let's do go run me.

[00:42:21]go and okay so we actually do get an error here and we see unrecognized token star uh oh I actually see the issue it's actually because of space if you look here we see there's two spaces it's because we don't have a token which handles Whit space right so that is something we need to handle so let's go into the luxer and Define another regular expression specifically um for white spaces so this token is going to be for uh skips so we're going to just cop this right here and I'm going to define the regular expression uh for back slash um S Plus and this is the skip Handler like so so let's define this function down below I'm literally going to copy this uh right here and we're going to Define one called skip Handler like so and inside of the skip Handler basically all we need to do is just find out out how big it was uh how big the thing is that we just had right so we're going to do match rex. find string index and it's going to give us the remainder like so and then this what we're going to do is we're just going to do lex. Advance n and we're going to do match at the first index now this is going to return us the length of the first match right here and now if we run this it works so we actually take a look at what happening here and we see we have a number token so if we look here we see number the space was ignored and we get star Dash 2 plus open PR 2.4 Dash Dash um number and then Clos pen semicolon eof so um that is basically Lexing in a nutshell next series or next episode we're going to finish off the lexer with a few tiny adjustments and then we'll be completely ready to go for parsing which is going to be really exciting Lexing is really the boring part of this whole thing parsing is where it gets really exciting and we can actually use these tokens to construct a really meaningful product which is our EST so I will see you in the next episode if you have any questions feel free to ask on my Discord server which will be linked in the description down below and in the meantime uh peace have a good time and Happy coding bye