Let's write a recursive descent parser in C (Part 1)

hey guys long time no see today we're going to write a simple recursive descent P for evaluating mathematical formula this is one of my favorite examples for recursion because it's uh non-trivial and it's very practical certainly more practical than calculating Fibonacci numbers or other classic examples for recursion so the point of paers in general is to take um a string and turn it into some other structure data normally you would turn this into an abstract syntax tree if you're a compiler writer but for this simple example I just want to transform the string into an INT in this case I would like to transform it into 26 if I'm not mistaken so the classic approach is to split the problem of passing the string into several functions each function responsible uh for a small sub problem the smallest sub problem is to pass numbers and I'm I'm going to make it even smaller I'm only going to allow single digit numbers so I want to write one function pass factor which is responsible for detecting that this is a digit and um it transforms this digit into the integer two so maybe we should simply start with that um pass vector okay as you can see I have a global variable Global variables are evil I know but for the purposes of this video it's going to be a lot um easier to understand uh having just one pointer uh instead of having several pointers and all pointers clogging up this very limited space so this uh Global variable is going to point to where I am currently in the passing process inside the string so let's start at the uh at the first character uh I can I can even show you starting at the first character let's let's execute the main function you can see pointers uh can or are visualized by orange arrows maybe you've already seen this okay after we've initialized X we call the past Factor function and uh store the result in know variable so we can see it and uh for we have to do some error checking inside pass Factor because we are not guaranteed that indeed it uh will only contain numbers and not other strange characters like letters or exclamation marks Etc so let's check if the character we currently point to is um a valid digit this is a well-known trick we simply check if it lies within uh zero and n and if it does we return the value sub and subtract uh Zero from it this is important if we didn't do this uh zero has the SK code 48 9 has the SK code 57 if we didn't subtract 48 we will get nonsense numbers I want a number an integer between 0 and 9 not between 48 and 57 and also um pass Factor should increment X by one um because we have just consumed we have consumed this digit we we are done with it uh we no longer need to look at it whoops what have I done here okay let's see if this works okay so first we check if star X which is this box X points to this box uh contains a value between 0 and 9 indeed it does so um we subtract in this case uh the S code 50 from 48 which is two exactly the number that we need and uh in the process we are also going to increment the pointer X so it should point to the next um character inside the string there we are okay what do we do if uh it's not a digit let's do some very simple error reporting expected digit but found whatever character there is and I'm not going to return a value which is a very bad practice um we even get a warning that we don't res return a result on all code paths so at run time if I get a passing error this particular IDE of mine will crash uh your IDE or your compiler or runtime environment will proberbly do um lesb N Stuff okay so I'm reasonably convinced that it works Let's test it let's start with a which is not a digit let's see if it works okay a is not between Z and 9 and we should get the error message expected digit but found a let's see there we are okay and then we will crash missing return statement good so this seems to work for single digits now let's write the next function above pass product what do we have to do in pass product if we if we look at the first product the first product contains of one factor then a multiplication sign and another Factor uh we could have an arbitrary number of um multiplication sign and another Factor after that so we'll have to use some kind of loop but first let's start with the first Factor so we pass that and after we pass pass that we would expect xra point to this star um maybe there is a star maybe there isn't we have to check so let's check if indeed there is a star and if there is uh we skip it and pass the next Factor when this call returns uh we are going to have two numbers two and three and um we can immediately multiply them there's no need to defer this calculation we can evaluate from left to right and um right nothing more to do in the loop then we can have uh further multiplications we don't have them in this in this example and when there are no more further multiplications we we can simply return the the product that we calculated okay let's put this to test let's pass a product and see what happens okay so by passing a product first means we have to pass a factor okay so this variable is going to to be um allocated but we don't know the value yet here it is okay first factor is this two it's a valid digit so we can simply return two and increment X and now we check is there something to multiply because we could have started with two plus something and there would have been no need to multiply something indeed we have to multiply so let's skip the star and uh pass the next Factor the three three is a valid digit let's return it and increment X okay and now we can for For the First Time multiply these two factors 2 * 3 should be six so I would expect six to show up here and Factor should disappear because it falls out of scope at this closing brace yes okay is there still more stuff to multiply no there isn't because plus is not a star so we can return six to our caller which was which was here so I would expect six to be stor inside the variable result there we are okay this seems to work as well so we can continue with the next function pass sum which is structured extremely similarly like pass product you can see um what does it mean to pass a sum first we have to pass a product then we look oh indeed we have to add something so let's pass another product and then we can add these two products so it's exactly the same structure as below let's call it product one uh then we have to Loop do we have to add something or not then we have to skip the plus sign and get the next product sorry why did I write the numbers here that doesn't make sense okay now we have two products in our example I would expect six and 20 so we can add them together and when there's nothing more to add we can return what ER we have calculated okay let's see if this works so we in order to add stuff we first have to pass the first product okay in order to multiply stuff we have to get the first Factor uh two is a valid Factor we already saw this yes there's star let's skip the star let's get the second factor three is a valid Factor let's return it and increment X and now we can multiply two and three we already saw this just for repetition nothing more to multiply we can return the six now we return the six not to the main function but here to the Past sum function we know that the first product is six at this point and now we have to see if we have to add something yes we have so let's skip the plus sign and now we uh need to pass the next product which eventually will be 20 okay product consists of the first factor which is four in this case let's return it and increment X indeed we have to multiply let's skip the star get the next Factor five is a valid digit let's return it and increment X now there's nothing stopping us from multiplying these two numbers together 4 * 5 is 20 there we are um now there's nothing left to multiply we can uh leave the loop and return the result 20 now for the first time we can add two numbers because we know that 2 * 3 is 6 and we know that 4 * 5 is 20 so let's add these two together uh 6 + 20 is 26 there we are nothing more to add and we can return 26 as the result to the main function there we are okay this was simple stuff not recursive so far um but recursive descent passs are called recursive descent passes for a reason the next example I want to make work is parenthesize sub Expressions let's say now for now I can only multiply single digits but I also want to be able to multiply um parenthesized Expressions so we have to um change the definition of definition of factor what is it that I can multiply what is a factor digits are still factors but also parenthesized Expressions should be factors as well so let's um add another case um if x points to an opening Parn we can um skip it let's write I don't know consume the opening Parn just for clarity and now inside these parenthesis um we can have an arbitrarily complex expression which is on the top level a sum we started with a sum because sums um the the plus operator binds least tightly so we can simply call um the pass sum function and when will the pass sum function stop uh it will stop at this point because uh it will it will recognize that there's nothing more to add because this is not a plus symbol so uh we will skip the closing parent here of course in a real par you would have to check that indeed it is a closing parel let's just skip it for for Simplicity here and then we can return the sum okay now let's see if this works uh we would expect 2 * 7 should be 14 let's see if this works okay now the first part is not uh terribly interesting um we already know uh that the first product is a factor is a digit so we can return two we have to multiply now it gets a little more interesting uh this is a uh this is not a digit so we will skip this if but it is indeed an opening Parn so let's skip the opening pattern and now we call pass sum even though pass sum is still uh active pass sum you can see it defines a variable Pro one and we still haven't filled this variable with a useful value this this call hasn't returned yet okay what happens if we call pass sum again I would expect um new variables to appear here as soon as we declare them inside um the function and also sum is going to be declared first so we we will see sum here waiting for the result and now we are inside pass sum for the second time and if I step into pass product you will see that we are waiting for this call to return so we know what the first product inside the parenthesis is so this is the first product outside of the parenthesis which would be the entire expression and this is the first product inside the parenthesis which would be three okay so we pass uh the three nothing new here uh we have nothing to multiply so we can just return the three uh we still have to add okay so skip the plus symbol get the next product uh get the next factor four is a digit we return the four nothing more to multiply because there is no multiplication uh so we can simply return Fact one what is what is f one in this case four okay where is it returned okay now we know that uh inside the parents we have two products three and four which are quite trivial products we didn't really uh uh multiply them with anything and now we have to add them we have to add three and four to get seven here's seven um then there's nothing left to do inside the parents so we can return the seven to our caller which was pass Factor at this point okay so we know that the sum inside the parenthesis is seven uh we can skip the closing pattern and return the seven to our caller who was our caller uh pass product because we were in the process of multiplication okay so now we can multiply 2 * 7 which is 14 uh nothing left to multiply we only had one multiplication so we we can return the 14 to our caller um okay and now nothing left to add because at the top level there was no addition we can we don't even enter this Loop in this activation and we return the 14 to the main function there we are 14 okay these are the basics of uh recursive descent passing now there are several several possible uh future directions for Little P we can do better error handling uh we can do let's say multi-digit numbers um we can do multiplication and division and maybe you can come up with even more useful stuff uh let me know in the comments what you would like to see next thank you and goodbye

So far it only supports single-digit numbers, addition, multiplication and parentheses. You decide what comes next! https://github.com/fredoverflow/skorbut