DIY Programming Language #2: Tokenising with Finite State Machine

hello and welcome to part two of our do-it-yourself programming language in this video we're going to look at handling more sophisticated input by using a finite State machine to PA the input into tokens tokens are tangible nuggets of information with which we can pass on to the shunting yard algorithm to then go and do useful things with such as solving or compiling now I appreciate this video is quite long but there are a number of fundamentals to get through to make sure that the paraa is robust and versatile enough to be useful in subsequent episodes so let's get started in the previous video I showed the shunting yard algorithm but it had some very bold assumptions to make it easy to demonstrate the algorithm but it actually made it very impractical to use in the real world for example we had an input expression that looked like this 1 + 2 * 4 subtract three input was provided to the algorithm in the form of a string and it was a very carefully curated string because each digit or each character of that string had something useful about it and we could iterate through the string from the beginning to the end because everything that we could process was represented by a single character it became quite an easy thing to pause we could quite easily ask the question is this a numeric digit well yes it is no it's not yes it is no it's not yes it is no it's not yes it is if it's not a numeric digit then it's going to have to be an operator however in the real world we want to work with more interesting things so we may have something along the lines of 1.13 + 2.61 * 4 on its own take Pi hopefully it's clear to see that our single numeric token now is multiple characters and it has things in it that are not strictly digits and because we're Computing nerds we may not just want to work with num numers we might want to work with other things so 0 B 011 plus 0 X2 F A times 4 take Pi okay okay you'd have to be relatively insane to actually work with something like that but it's nice to have that flexibility but that flexibility comes at a cost we've now got four different numeric standards of representing a numeric value in our expression it could also be the case that in the future our operators become more sophisticated for example we might have more than one character to represent an operator and we may also find ourselves with the dreaded un operator also sneaking into one of the advantages of being able to iterate from the left to the right of the string is we could also apply the shunting yard algorithm at each stage and sort it all out and with that we've defined the premise of this video I want to take a human readable sludge of all sorts of mess and turn it into something structured and ordered that our computer can understand I also want to keep my mind open to the idea that as we progress through the series we're going to want our DIY programming language to grow in terms of sophistication so there might be other things needed alongside numeric values and operators to handle this I'm going to use a finite State machine and it's certainly not the first time on olc that we've used finite State machines but a little refresher never hurt anybody it's essentially a posh way of describing a form of computation at any one time we can exist in a state states have inputs that can trigger and move to a different state which in turn can move to another different state it could potentially move back to the state we've just come from let's start with a very simple expression this string 100 + 35 it contains multiple digit numeric literals us humans are very good at observing that this is a token this is a token and this is a token so even though the string contains six digits there's really only three relevant bits of information our computer however can only see one digit of the string at a time but it can see them in order so I've developed a small state machine that looks at the first digit and then decides how to proceed completed tokens are then built up as we progress through the state machine Loops my first state I'm going to call new token it works a bit like a reset State any currently accumulating token string is reset my state machine is always going to be looking at the front of the string but can consume digits so right now it can see the digit one but it's not consumed it from the expression the first digit of a token is invaluable in deciding what that token might be so in this state looking at the digit one I'm going to ask the question is it a digit and if it is a digit it's likely my token is going to be a numeric literal so I'm going to append the character to my token string if I append a digit to my token then I'm going to consume it from my input string I'm still in the numeric literal state but now the front of my string is this zero so I'm going to ask the question again is it a digit well exactly the same thing happens it is a digit we consume it but we remain in the numeric literal State and then it happens again the front of the string is zero so we consume it add it to our current token and we remain in the numeric literal State now the front of our string is this plus symbol this is clearly not a digit it's not a digit so I'm not going to consume it just yet but I am going to finish off my token classify it as a numeric literal and go to my complete token State the complete token State outputs our classified token to some output container but then immediately moves us right back to our new token State recall this resets our accumulated token the plus symbol is in our known character set for operators so we can ask the question is operator in much the same way as we've just done with numeric literals we will accumulate the current token with valid operator characters and we can keep looping in this state consuming each time just as we did with numeric literals until the character is not an operator character we've already got a state to handle the completion of tokens and outputting them and that will automatically take us back to the new token starting point hopefully with this very crude example you can see we will end up with three strings from our output and not only are they just strings we know that this is a numeric literal this is an operator and this is a numeric literal we can include this meta information with each token now I have simplified my state machine somewhat to fit it all on one screen like this but the principle is what we'll be expanding upon throughout the rest of this video but I thought let's start here and replicate what we did in the previous video this time we can use multiple digit numbers this will give us a good base then from which we can start to add the new fancy features it's also an opportunity to just quickly discuss some housekeeping required as part of this Project's development even though this is a continuation I'm starting with a blank file we're now starting to not look at the individual algorithms in isolation we're working on the final DIY programming language framework and as such I'm going to add in a bunch of standard Library things that we use quite a bit of and I'm going to create the namespace olc Lang no doubt once we actually get around to naming the language that might change in the shunting our video we created a struct called symbol I'm going to change this to Simply token it made sense in the previous video to call them symbols because they had meaning associated with them but in this video we're looking at just specifically having tokens we don't really know what the tokens might mean at this stage I'm going to tidy up this struct a little bit I'm not going to contain an operator equivalent we'll see why later and I'm going to rearrange the ordering of the token some of our inline initializes later on are a little more clear each token will consist of the type as it did before and the text of that token for the time being I'm also going to store in the numeric value if applicable to this token that just makes things very convenient and keeps the code clear when we're working with just values later on I also want to add adds to this token structure the ability for it to describe itself as a string this is useful for debugging and so for each type case I will add in the string equivalent finally I'll append the token's value itself again from the shunting yard video we had a structure called s operator well I'm keeping this just the same except I'm dropping the Hungarian S at the start now as part of my ongoing efforts to upset the internet I'm going to throw in an error exception ooh this is a first for one loan code I think we don't usually use standard exceptions we usually just crash out but that's quite inconvenient for somebody that's writing code and it causes problems you want it to crash out in a controllable way but at the same time I don't want to bug down my code with thousands and thousands of nested anything in order to sort it all out I believe this is a good use case to use standard exception at the moment it's called compile error and it doesn't do anything particularly fancy other than wrap a string which we can display with our error message and finally I'm going to create a class called compiler I didn't do this previously because we had no requirement for isolation between different rounds of compilation we still technically don't but we will do in the future so it's useful to have this map of operators actually belong to something rather than just floating around in a namespace and yes this map of operators has the same purpose as it did in the shunting yard video for the time being the Constructor of the compiler will Define a few operators already and for almost being cancelled for an egregious lack of Integrity let's fix this quick bug right now done hopefully that has gone some way to sedating the armure coding Guardians of the internet to my compiler I'm going to add one more function pass which takes a standard string of input does some magic using a finite state machine to produce a vector of output tokens if we didn't provide any input by accident it's a good time to test our compile error exception mechanism and it is here where we need to implement our finite State machine mey goodness our source file doesn't have an INT main so let's quickly add one of those two to make sure we can test things quickly and easily as in the previous video I'm going to have a string called s expression this time you can see I've inflated the digits just to make them a bit more interesting and then very fancily in a tri block I'm going to call the PA function we've just created on this expression and if there's a problem I'm going to catch any error that it throws and display that to the user if there aren't any problems the PA expression returns a vector of our tokens I'm going to iterate through those tokens and call the string function upon them to display them so yes a little bit of housekeeping to get out of the way there but now let's crack with implementing a finite State machine now one of the problems with State machines is that they yield quite repetitive and at times often verose and rather large code that's just the price you pay for the power of organization a finite State machine might give you to keep track of what state I'm in I'm going to create another enum class inside this function called tokenizer State and first time around I'm just going to add in the states we've already talked about new token numeric literal operator and complete token in the interest of expediency and to have parity with the previous video I'm also going to add in two new States parenthesis open and parenthesis close now here's an important thing about State machines you need two variables to track the state the first one is State now which as its name suggests is what is the state I'm in now and then when I need to and under my control I can transition to the next state what this means is that whenever we want to change State we set state next to whatever Target State we desire and only at one point in our program do we set State now to state next changing a finite State machine's State halfway through its implementation can often yield bugs which are very difficult to track down in fact it is a violation to do so the beautiful thing about programming however is it is possible to to do so and sometimes it can save your neck but let's try and do this by the book as much as possible as we progress through the input provided to this function we're going to consume characters from it and we want to keep doing so until there is nothing less to consume that's when we can leave our state machine so while there are still characters left in our input process our state machines State now state only once we finished processing the current state can we update to the next state state machines don't have have to be included in a while loop like this sometimes it's implicit perhaps a function is called every frame and that function belongs to a particular State perhaps there is some sort of external clock input that causes your state machine to tick over to the next state how that's defined is up to you but for our purposes every character in a string will cause the state machine to think about what it's doing at least once per character our first state is basically our reset State new to token recall as I'm iterating through the input expression we're going to be accumulating tokens as strings individually I can also start to composite the current token I'm reading in our reset State should do exactly that H I'm getting a little red squiggly here which is telling me something's malformed about my token definition and indeed it is because I cut and paste the code from some prototype that I've made prior to making this video sometimes little errors like this creep in I don't need to Define type twice so apologies for that I'm only human but it does go to show that these things are a little bit live when we're in our new token State we said we were going to do some first digit analysis or first character analysis depending on where you're from now we said that the first thing we might want to check for is numeric literals the eagle eyed amongst you may have noticed that I've created what's called an iterator here called character now and my while loop is continuing on character now not being at the end of the string character now being an iterator also has a value at all times which I can access with the asteris symbol however I don't think visually that's clear enough for me particularly when the code gets complex later so I prefer in this instance to use a zero index of the array operator on the Char now iterator and if we wanted to check for numeric literals we might do something along the lines of is standard digit CH now zero that's what I was just talking about if that's true then the character supplied at that point in our input is a numeric digit if it was a valid numeric digit we can set our current token to be that and we can tell our state machine to go to the next state which is going to be tokenizer State numeric literal and most importantly we must consume that character this consumption is performed by incrementing our iterator Char now 0 now points to the next character in our string the standard Library function is digit is the correct function to use but I don't like it and this is one Lo encoder and I often have a tendency to go off on a different path rightly or wrongly one of the problems or indeed one of its powerful features is that it can detect local and it's reasonably language and character encoding independent and it has lots of interesting features that make it very safe to use all of those interesting features actually also make it quite slow to use we did some science on this on the Discord server and found out that it is quite quick but it's not that quick now given a source file might contain many many many many many different characters I want something really quick to do this assessment and we're going to need similar functions for assessing different types of tokens so instead of this being a standard is digit it should be something along the lines of is the current character considered a acceptable member of a set of characters that Define numeric literals and solving that problem is where we start to add some rules for what are the capabilities of our compiler for our custom language a more visible equivalent might be something along the lines of this here we ask the question does this string of digits contain the character we're looking for if it does then it's considered a numeric literal digit and if it doesn't it carries on it's almost functionally equivalent to is digit however now now we've got a linear search for every single character that's still also quite slow we could also do this which I know will really upset some people but because we can exploit The asky Ordering of these characters we can do two simple checks to see if the current character is a valid numeric digit this method might seem quite nice but then what happens if our set of acceptable digits has other things that we want to get to and we can't necessarily represent them as a range for example as we will see we do need the decimal point this could get very messy quite quickly so I want something that's consistent easy to construct and flexes some of my modern C++ muscles yes I am nodding my head at the top of my name space here I'm going to create another Nam space called lot this is sort of an internal in a workings namespace it stands for lookup table I'm going to throw memory at this problem to make it go away and have instantaneous lookups I'm going to start by creating a const expression Auto function called make L and it takes in a string view get that a string view of acceptable characters because it's const expression I can call it a compile time nice and easily so let's have a look at what's going on here I'm creating something called numeric digits that calls my make lot function and to that make lot function I pass a string of the character say I want to be acceptable for that set the make look function itself really just contains a standard array of booleans it contains 256 of them I'm going to assume we're only allowing asy characters and extended asky characters to some degree in our language now that's a big problem because it does rule out most foreign language characters and this is why you should probably stick with these standard Library functions provided by the C++ language however this makes videos a bit more interesting and perhaps shows some techniques where we can actually use const expression in a really valid way I'm going to initialize the array of all 256 booleans to false and then I'm going to take the asy or 8bit equivalent of the input characters and set that location in the array to true I'm going to return that array which gets copied over to our numeric digits so this allows me to construct a set and we can see it here with the tool tip false false false false false false false but true where it needs to be so if I wanted a set of numeric digits and an alternative set of real numeric digits because they include a decimal point it's now very easy for me to construct that and whilst I'm here I'm also going to create a set of wh space digits too again there is a standard is wh space I think it's called standard is space but you're not going to get much faster than just looking up an array directly with the character value so getting back to it I can now simply call the at function of the standard array for the set of digits I'm interested in passing in the character as the index and that will return true or false as to whether this character is contained within that set and it will do so pretty damn quickly I'll leave this here because this is the code that ends up on the GitHub since we just added the ability to detect white space let's just handle that too as part of our first digit analysis we look it up in our lookup table if it is Whit space all we're going to do is consume it we have literally nothing else to do we don't want to out put any tokens we just want to consume that thing if it is not Whit space then we can start checking to see if it is a numeric literal let's add in the case for our numeric literal state to close this Loop remember that we enter this state having consumed the character and our current token has already been set with the first digit so let's check if the new digit at the front is part of our set of real numeric digits if it is append the digit to our token consume the digit and stay in our numeric literal state if it's not then we're done so set our next state to be our complete token State construct the token by classifying with what it is it's a literal numeric and for convenience I'm also going to convert the string value to a numeric value this has introduced a new state now complete token well recall from the presentation that the complete token State doesn't do very much it just pushes it into our vector and goes back to the reset State new token I'm going to add a set of digits for our operators to be constructed of too now our first digit analysis becomes quite a trivial state to implement if it's not Whit space and it's not been a real numeric digit then let's check to see if it's an operator digit if it is we'll move to our state operator operators are a little trickier now originally our operators were singled digigit things but this does limit the number of operators symbols available to us that might mean something useful to the programmer it's quite often for example in C++ to see x++ this is an operator and it means increment the value of x this can lead to rather confusing things for example this is potentially valid because x++ would go away and add value one to X and then we would want to go and add two to that value we've smushed up our operators we know that a plus plus is a valid operator and this uh regular plus symbol is also a different operator so we have to start making some assumptions and rules of our own to resolve this ambiguity and I'm going to work on the assumption that my operator determination algorithm is greedy it looks for the longest valid operator it can first so assuming we've got a list of stored operators somewhere we want to keep reading operator digits until we can match it with something when we read the third one if that makes it invalid then at least we knew that this one was valid so we can write that one off and then we can start our process again this means our operator state in the state machine has a little bit of work to do before it can decide whether to move to the complete token state or remain in the operator State note that when we performed our first digit analysis we did not consume the character for an operator when we enter our operator state I'm going to check that it is indeed a valid operator digit we'll come back to what happens if it's not later one of the tricky things about thinking with State machines is you have to think in parallel slightly about what's going on we know in the background all of our states are accumulating s current token which is the text form of the current token we are deducing so let's check if the current token plus the current front of our input is a valid operator is it contained within our map of operators note that we've not actually changed the current token yet we're just doing well kind of a Forward Thinking check if this results to true then keep going we've got a larger operator so append the current character to our current token and consume it if this was false then the current character was a valid operator digit but combined with the current token is not a known operator therefore we have reached the larges size operator that is known to us for current token so we'll just confirm that the current token is indeed a valid operator we know that the next character added to that is not a valid operator but we're being greedy so we'll bank that one now by moving to our complete token State now all the time the digit is a valid operator digit we know that the next character does not yield a valid operator and we know that currently our current token is not valid either so we're in a rather strange state where we might have an operator coming up but right now we can't determine it so we'll just keep on going we'll accumulate that character into our current token string and consume it we're growing some operator which is currently not valid but it might be later it might be that it's for or five digits long this operator and we've only got around to testing the first two or three if we're still in the operator State and the digit was inv valid then confirm that the current token is legitimate if it is go back to our complete token state or throw an error because we've got a valid set of operator digits but it's not recognized as being in our map of operators we've come across an unrecognized operator so yes the operator tokenizer state is a little bit more complicated because of this greedy nature to consume the largest operator it can do first note that now we've got several Pathways going through to complete token we've not had to change it at all this is one of the nice things about a state machine that functionality is already there for us we go back to our state machine definition you'll see there's two more parenthesis open and parenthesis close this was to bring parity with the previous video let's go away and Implement those States now but these are trivial in our first digit analysis of our new token state I'm going to have two explicit checks for an open parenthesis and close parenthesis I don't consume the character but I just move to that state arguably you don't even need a explicit state to handle these but I'm choosing to because I do have some Behavior which is unique to being in these states and I shall demonstrate that now I'm going to grow the current token even though it's obviously an open parenthesis and I'm going to consume it this is just to keep the pattern consistent across all the states and then immediately I'm going to move to complete token having classified this token as a parenthesis open at this point I'm going to introduce a new variable it's a quick and dirty hack just to check that I've got a balanced number of parentheses in my application every time I open a parenthesis I'm going to increment this counter and every time I close the parenthesis I'm going to decrement this counter hopefully this should be zero once we've compiled the script I'll need to create this variable outside of my state machine and upon exit from the state machine I can do a quick check if this value is not zero then the parentheses are not balanced we'll see in a future episode how we can add more information to this to actually tell us where it's not balanced it does seem like we've written quite a lot of code today but a quick recap before we give this a world it's important to make sure that we're off to the right start we've created a very quick way to make sure if a character is part of a valid set of acceptable characters for the thing we're trying to tokenize we've created a token struct which understands its own type in its value and has the ability to display itself we're using exactly the same operator implementation as we did in the shunting yard video I've added an exception typee called compile error just to make throwing errors easier and more understandable to the user and we're encapsulating our functionality inside a class called compiler at the moment we just have a map of operators and we've just got the four bug standard operators we would normally have to this compiler class we've added a function called pa pa contains a finite State machine right now it just has a small number of states the state machine is effectively stim ated by each character in the input expression and for each character we can determine what state to go to next or remain in the current state depending on the criteria of exit for that state as we move around the state machine the state machine creates tokens it does that by looking at the first digit of a blank token and then moving on from there if the first digit is a number then it will go and try and interpret the largest number of digits it can that remain a valid number the same applies for operators providing The Operators exist as defined in our map of operators the states themselves are reasonably simple the operator state is a little bit more complicated because it has to be a little greedy that allows us to have multiple digit operators next to each other in the input expression and finally we're starting to add in the very basics of syntax checking by putting in tools like the parenthesis balance checker our state machine has a completion state which pushes that token to our Vector of output tokens and we return that Vector of output tokens to the user who called it in the first place with the expression if there's a problem that will now throw an exception and we can catch that in this TR catch block let's take a look at the top here we have our input expression and it has been broken into tokens the first is 100 plus open parenthesis then a numeric literal 20 * 40 close parenthesis then we've got an operator it could be unary it could be binary we don't know yet all we have done is tokenize these tokens have some definition but there's no meaning applied to them yet in fact because we Define sets of real numbers we should be able to put in more interesting numbers for them to try and pass this works because the decimal point character was part of our set of characters allowed in real numbers we have a problem however I can put in two decimal points in a number that's clearly not valid we'll need to handle that I can also see what happens if I put in invalid symbols in a number well it just seems to have crashed hm not very good so far what we have started to develop here is a very rudimentary form of syntax checking as I don't really have any description for this language yet and I'm not entirely sure where I'm going with it I can't set up a list of hard and fast rules for us to follow but what I do know is that we're going to need things like symbols so anything that we don't readily identify as being a literal or an operator or Whit space or something else that we already know I'm going to say is a symbol well checking for multiple decimal points is quite easy I'm going to create a Boolean B decimal point found and in our reset State set that to false in our numeric literal State we want to make sure that only one decimal point is allowed so I'm going to check if the input character is a decimal point if it is and my decimal point flag is already set then this is an error this means our numeric literal contains two decimal points however if the character is a decimal point now and our decimal point flag is false then just simply set it to true that's allowed let's try this with this dodgy expression very nice our exception was thrown and it tells us there was a bad numeric instruction solving this problem however is more complicated and it requires us to introduce a new type of object into our paa our input Expressions only know numbers and operators but that's quite limiting in the real world eventually we're going to want variables function names and other properties about our input Expressions which are described in a written way since we don't know what these might mean but we know what they are the best we can call them is a symbol the passing stage of our compiler doesn't care about the meaning of things don't forget it just cures about what things might be I've added a set called symbol name digits which are the valid characters for things such as variable and function names you can see it's really upper and lowercase letters the period symbol underscore and some numbers as with most languages we'll start to need a rule that describes what our symbols can legitimately be called for example 1 2 3 A B C is invalid because you can't have any symbol beginning with a number that's one of our rules ABC 1 2 3 however is completely valid that's basically a variable name with a number as a suffix we need this symbol state in our state machine to handle the unknown whether we process it or not is a topic for another time but let's at least handle it I'm going to add to our state machine the symbol name State and essentially we will know whether it's a symbol or not from our first digit analysis because if it's not any anything above it then it's something unknown it's potentially a symbol since it's unknown all I can do is consume the character and start a new token and enter my symbol name State just like with the numeric State we'll keep accumulating symbol name token as long as the character at the front of our input is legitimately a symbol name character we'll do that until the character isn't part of our symbol name digit set at which point we'll just complete the token call it a symbol and move on don't forget we have some rules to enforce that we can't have numbers preceding symbols so we'll make that check in our numeric literal State here we've been accumulating valid numeric literal characters into a token but we found something that isn't a numeric character it could be an operator it could be parenthesis it could be something else and that's legitimate but what isn't legitimate is if it's a valid symbol character We've Ended up in a situation like this which is an invalid token in our environment sorry golfers now when we run our program we can see that there is an invalid number or symbol in fact we can start to test these things in isolation so 1 2 3 ABC should be invalid it is but abc1 23 could be a legitimate variable name not a problem it's just identified as a symbol by the tokenizer if we put a space in between these ABC 1 2 3 we can see it's two tokens it's a symbol called ABC and a numeric literal that is fine abc1 23.4 the whole thing is considered a symbol again legitimate that's fine because we've allowed periods to be part of our symbol naming rules ABC + 1 2 3 again just fine having double Precision numeric literals is all very well and good but inside I am an embedded systems nerd I need binary and hex to handle these two additional forms of numeric literal I'm going to add in two more sets of valid digits one for hexadecimal as you can see I've got the lowercase a b CDE e f and the uppercase and binary digits zero and one oh that's nice for the time being my language is typeless everything will resolve to a numeric double and we'll look at that in a future video but paing these new numeric literal types in our finite State machine does require some additional States I'm going to throw in fancy numeric literal hex numeric literal and binary numeric literal we start checking for numeric literals in our first digit analyzer so far we've assumed that we're always going to be doing a base 10 numeric literal well if the numeric literal is prefixed with zero that may or may not be the case we have to to make that determination so if the current character is zero it could be heximal or binary if it's not then it's definitely going to be base 10 I'm going to adopt the C++ style conventions for this and prefix things with 0x whatever for hex and 0 B whatever for binary if we're in a non-base 10 State then I want to go to fancy numeric literal because the next character determines where we go next after my numeric literal state I'm going to add in my fancy numeric literal state which is where I check the next character we've consumed the zero at the start and now if it is a lowercase x we're going to move on to hexadecimal and if it's a lowercase b we're going to move on to Binary notice I'm about to add an additional string variable called Fancy numeric literal token I don't want to interfere with the actual token I want the 0x or the z b at the start but when I'm actually turning that into a number I don't so this is just a way of keeping the two separate this is just one of those anciliary things like decimal point found if the second character wasn't an X or a b and it wasn't part of the set of real numeric digits in which case just go back to being a numeric literal then clearly we've got some weird construction going on so we'll just throw an error at that point let's add in now the case for handling hexadecimal numbers the case for binary is almost identical let's make sure that our first digit is valid hexadecimal if it is is accumulate these until it isn't if the character isn't valid hexadecimal then we want to store it as a token however just like with numeric literal we want to make sure that it isn't also running into being a symbol because that's not part of our rules we don't allow that to happen create the token in preparation for being pushed to the output stream and convert the hexadecimal value into a double just for convenience we can do that straight away actually with the string to Long Long Function and passing in base 16 binary numbers are almost identical in their construction except this time we're looking for the allowed binary digit set and rather than base 16 it's base 2 I'm just going to quickly modify our tokens string function to display the value of any literal numerics that get passed in this will help us to debug these new numeric literal types here is an input expression containing now all four types of numeric literal our paraa will understand let's take a look so there is the input expression at the top we can see the first one was interpreted as binary which is four and two which yes got the value six here we've got the heximal one which I'm I'm guessing that's the right value uh here we've got one with a decimal point which was fine and here we've got one just as an integer as discussed at the moment everything resolves to a double if I malform my hex here by putting in the letter M in the middle of it heximal literal is is malformed good our errors are starting to help us out what I'm about to do next may seem a bit odd in the context of the video so far I'm going to add in a few additional features we'll need later on in the series so this is tying up a few loose ends I appreciate that right now adding additional types of token might be beyond the scope of this video but it's necessary for later videos in this series fortunately they're very simple additions to add to our state machine so we can really rattle through these you've seen already parenthesis open and parenthesis close scope open scope close end of statement separator are all implemented exactly the same way so I'm not even going to show them the only two left are literal string which is something defined in quotes which is quite interesting and keyword our state machine will need several more states to handle these but again they're near direct comparisons to parenthesis open and parenthesis close we'll leave those for the time being one that does matter however is string literal let's take a look at that one we'll check for a string token in our new token State as part of our first digit analysis strings in my scripting language are defined as beginning with open double quotes So if we encounter that as a first digit then we move into our string literal State the string literal State consumes all characters into a growing token until it encounters another double quote when that happens we classify the current token as a literal string and eventually it gets pushed to our output tokens you'll notice that if it is a double quotes either at the start or the end I'm not actually adding that to the Token I don't want the double quotes as part of the token just its contents this is also for now a little naive because there is no such thing as an escape character it will just consume everything until you get to the next Double quotes keywords are something we're not using today but we will certainly use in the future and for now I'm just going to create a map of keywords and I'm going to define a keyword as just being literally nothing at all it's just to make the unordered map work to all intents and purposes a keyword is just a special type of symbol and we might want to use keywords to change the behavior of this paa in real time so we'll just double check that we're classifying the symbol correctly by searching for it in our map of keywords and if it exists then we'll classify that token as a keyword and deal with it appropriately later just before we test this there is one more state with the string literals which causes a problem if the user never puts in another double quotes we'll keep consuming characters until we reach the end of the file or the input uh in which point the while loop containing our state machine will exit so if we're still in string literal state by the time the state machine has exited then clearly we've not got the closing double quotes so with that in place let's take a look and see what our little machine can do A+ B very good symbol operator symbol I like that a + 1.234 very good literal numeric let's do some binary uh plus plus some hex divided by a decimal that seems fine too we've also got these sort of additional symbols we've added in now so we could have uh Funk 1 2 3 4 there we are so we've now got a symbol open parenthesis a numeric value a separator object separator object separat object that might be useful later on let's try x = a + b oh we've got an unrecognized operator that time what if we wanted to do print and then hello world well here we've got a symbol called print an open parenthesis and a literal string hello world let's just make sure that we if we didn't have that in what happens yes there we go parenthesis not balanced well parenthesis Checker caught it out first so that's even better so let's just do hello without that missing quotation mark good good good I think the paraa as we have it so far is robust enough to start being used for some actual Solutions but in order to be useful we need to apply some sort of solver to it and to do that we need to have the shunting yard algorithm which we did in the last episode fortunately the way that we structured the shunting yard algorithm before is very easy to bring into the code at this point so here is the code from the original video and this was the main Loop where we iterated through the characters of the expression and we simultaneously classified the character and implemented the shunting yard algorithm we ended up with a container of things in Reverse polish notation order and we pass that container into the solver to then go ahead and work it all out the shunting yard algorithm fundamentally relied on the sequence of characters in this expression we don't have that anymore we now have a sequence of tokens in a container but otherwise it is exactly the same so I do require a little bit of trust when I do this because I'm not going to talk through every single line of code here but if you've watched the first video some of this should look very familiar I'm going to pass in our Vector of tokens into a newly created function called solve and then I'm going to paste in the shunting yard algorithm as we had it from the previous video except this time rather than being characters of a string they are our tokens in our container of tokens other than that it is functionally identical you can see that it looks at what the type of the token is and then behaves accordingly was it a literal numeric was it parentheses or was it an operator and if it was an operator was it the UN operator or not and apply the order of Precedence rules if it can't do any of those things because we do have tokens now it might not understand for now I'm going to throw this compile error that the solver contains elements that cannot be solved yet on ly after we've applied shunting yard just as before we need to drain that holding stack and then implement the solver now it makes it an assumption that intrinsically we only have divide multiply add and subtract there are a couple of subtle differences here but it is almost identical to the code in video one again so I'm not going to spend any more time on it than that this means as part of our main test program Loop we can now call our Sol function on the vector of tokens that's been passed back from our PA function and if there are any problems we'll catch the error so let's take a look 1 + 2 * 4 take 3 that's our classic that we've been using all the time now we know we can mix that up a bit I've Got a Feeling we trust that the shunting yard will get things in the right order but let's try some of the different numerical techniques we've got now so we've got 0 B 01 1 0 which is 6 uh plus 0 x 1 in this case 6 + 1 is 7 so we've got two different numeric literal types and it seems to be passing those just fine Min - 100.1 * 99.67 well it's handled the unity operator and multiple decimal points just fine let's give it something it doesn't quite know yet F of 1 2 3 expression contains elements that cannot be solved yet so it doesn't know anything about symbols or separators 0x FF / 2.0 127.5 we remain in the double domain and to leave our application quit oh well I know there was a lot to get through but I think it was necessary to cover some of these fundamentals to make sure that we have a robust solution moving forwards so far what we have developed is nothing more than a very simple calculator it can only do four different operations and it tends to do everything instantaneously we can enter one string of input and press enter and it will give us a solution that's all well and good but it's not really a computer program there's nothing that implies sequence there's nothing that Fosters reuse and we've not even looked at things such as input and output variables and memory well all of that fun is to come in subsequent episodes so if you've enjoyed what you've seen so far give me a big thumbs up please have a think about subscribing come and have a chat on the Discord you'll notice a link below to the code for this in the GitHub repo and I'll see you next time take care