What Is a Recursive Descent Parser and How Would a Programmer Build One?

[00:02] data structures in memory turning something that is human readable into data structures is the job of a parser parsers take HTML and turn them into the document object model that is used to lay out a web page they take the source

[00:18] code of a computer program and turn it into pages of error messages due to a misplaced semicolon I'm going to explain how a parser works by showing you how to write one but I'm going to go a step further than that I am going to

[00:32] introduce to you the core skills programmers use when they are tackling new problems basically I'm going to show you how a programmer thinks about programming the type of parser I'm going to explain is called a recursive descent

[00:47] to explain is called a recursive descent parser or a top-down parser it is the simplest type of General use parser so it is something that is pretty easy to explain it also has some downside words that means that it's not used in high

[01:02] performance applications but it is a good starting point a parser takes in raw human readable text and generates from that a parse tree this structured tree can then be further processed by a computer program into whatever format is

[01:18] most useful for the role let's make up a simple language for our example our language will consist of numbers the plus sign the multiplication sign and

[01:30] brackets We Will Follow The Binding rules from those irritating Facebook rules from those irritating Facebook posts okay irritating Facebook posts doesn't narrow it down too much but I'm pretty sure you know the one I'm talking

[01:43] about we are going to have brackets bind the strongest then multiplication and addition so a statement like this will get parsed into this pass tree also we are just going to ignore any white space in our language the first step is to

[02:01] refine formally the grammar of the language we are going to do this by creating grammar rule each grammar rule says what a part of the language is made up of progressively subdividing the language down until we get to the

[02:15] unsplittable atoms of the language let's call the top most rule of our language and expression we could call it anything and quite frankly some of the most difficult parts of programming is thinking up good names for things

[02:30] because we have so much Freedom there now our job is to work out what an expression consists of it becomes a little bit like a puzzle solving game since plus binds the weakest and will always be on top of the past tree then

[02:46] we know the expression must feature the plus rule so our expression must have within it the structure of expression consists of something plus something but we also know not all Expressions have plus signs so we

[03:03] can extend this to or something we know we can have chains of pluses without any we can have chains of pluses without any limits the way we can make unlimited chains of classes is to make this rule recursive for technical reasons it is

[03:20] Handy if the recursion is not on the left so our expression will need to look something like this expression is something plus expression or something

[03:33] else now we can fill in the remaining blanks with the next layer down in our grammar expression is term plus expression or term we will Define what

[03:47] term is next at this time you should start to be coming to terms with defining a grammar this is one of the Prime skills of solving programming problems divide and conquer programming is a complex task and it quickly becomes

[04:04] impossible to hold it all in your head so we split a big task into smaller durable tasks so next is the term grammar rule since times binds the next

[04:17] tightest after Edition we know that times has to be on this level term is something times something we can apply the same logic about repetitions and options we had for addition to work out the term should

[04:35] addition to work out the term should look something like this term is operand look something like this term is operand times term or it is operant we haven't even started programming yet but here's the next key insight for programming if

[04:50] you see that something common just reuse the solution you used before at the lowest level we have the operand since brackets find the tightest we know that they must be down here and since numbers

[05:06] be down here and since numbers can't fantactically be split up we know well so we can say operand equals Open so we can say operand equals Open Bracket expression close bracket or

[05:21] Bracket expression close bracket or number now the names expression term and operand are totally arbitrary these names are there to act as reminders for us what is more important is the relationship between the rules now I

[05:37] want to be super accessible to everyone so rather than using a specific programming language I am going to be giving examples using pseudocode pseudocode is not really a programming language but more a way of sketching out

[05:52] logic that a real programming language would need without going into the specifics of any language the first thing we should think about is what is going into and out of our parser the function path takes a string which we

[06:08] put in the text variable and returns maybe a pass tree a string is a type computers use to represent human readable text the metaphor is that are

[06:22] characters connected together on a common string this function returns maybe a parse tree because it's always possible for parsing to fail if it is fed something that is not possible I go more into maybe types in this video but

[06:38] the short explanation is that a maybe type can either be type can either be base type or a special value called nothing now let's talk about how we are

[06:51] going to implement this parsing in a computer system parsing is implemented by two separate but equally important sub-processors the lexical analyzer that tokenizes the string and the sum and the syntactic analyzer which structures the

[07:06] tokens the job of the lexical analyzer is to take the raw string and create is to take the raw string and create tokens from it since numbers are Atomic in this grammar it collects together the digits into entire numbers and it also

[07:22] digits into entire numbers and it also removes any white space I'm not going to explain the lexical analyzer in this video but rather I'm going to treat it like it has already been implemented function Lex takes a variable of type

[07:39] string and returns maybe an array of token function how as token function how as takes a variable text of type string and maybe returns a parse tree assigned to the variable maybe token the value

[07:56] the variable maybe token the value returned from calling Lex on the variable text we can detect errors at the laxing stage so case may be tokens in the case of nothing return nothing nothing comes of nothing the case

[08:12] statement basically checks the value that is in the variable and does the thing with the matching case calling a return statement ends the function return statement ends the function immediately and returns as the value of

[08:26] the function whatever the argument to the return statement is if there isn't an error then we can assign the token to a variable to be used later some of you

[08:38] who are more used to programming might think of what I'm doing is a little bit verbose however I'm writing this to make it extra extra clear then the next step in processing is to do the syntax analysis unlike the lexical

[08:55] analysis that operates on a character by character basis syntax works on the entire document that means that syntactical analyzer is more complex than the streamlined Alexa this is another common thing programmers

[09:12] use have a pre-processing stage that simplifies the data to make processing simplifies the data to make processing easier it's another way to divide jobs into simpler subparts we know what needs to go in and out of this path expression

[09:29] function the function parse expression takes an array of token into the variable tokens and maybe returns a parse tree however thinking about it in this grammar it is possible to have Expressions that start

[09:43] at places that are not at the beginning of the string and end at not the end so to facilitate that let's adjust our function slightly function parse expression takes an array of token into the variable tokens and an integer value

[10:00] into the variable offset it maybe returns a pair containing pars tree and integer with this stub written and a stub is this stub written and a stub is basically a hollowed out function which

[10:15] we use for work in progress we can finish off our pars function assign to maybe tree the value that's returned by parse expression when called on the

[10:27] variable tokens with the offset value of zero in the case of maybe tree if the value is nothing then return nothing if it is a just value then just return that

[10:39] it is a just value then just return that tree now that is looking good so let us tree now that is looking good so let us fill in our code for parse expression the first thing it should do is check if it has a sum again we're going to put

[10:53] off working out how to do that exactly until later assigned to the variable may be sum whatever is returned from par sum on tokens at the offset in the case that

[11:05] on tokens at the offset in the case that maybe sun is just some with a new offset maybe sun is just some with a new offset then return just the expression created from the sum pars with the new offset if pars sum fails then it might just be a

[11:20] term so we should parse it as a term next assigned to maybe term past term with the tokens at the offset in the case of maybe term it is if it is a just

[11:32] with a new offset return just expression from a term with that new offset so we now have parsing an expression defined we can go on to

[11:45] an expression defined we can go on to parsing a sum again we Define what is coming in and out of the function it has the same type as past expression parse sum takes an array of token into the variable tokens and an integer into the

[12:00] variable tokens and an integer into the variable offset and it maybe returns a variable offset and it maybe returns a pair of pars tree and integer this time rather than dealing with choices between Alternatives we are dealing with a

[12:13] sequence we will start with a parser for the term if this fails we know the rest isn't going to work so we can return nothing in this case maybe term is assigned the return value of pars term when called with tokens and offset in

[12:30] the case of maybe term if it is the just case set term tree and term offset to the first and second returned value from parse term if nothing is in maybe term

[12:44] then return nothing after we've passed the term the offset will be set after that term where the plus should be so we can add another parser for plus maybe plus set to parse plus tokens term

[13:01] offset my case maybe plus etc etc then we can end off following with the trailing expression maybe expression same pattern now we can

[13:14] create a new tree from the sub trees again I'm not going into how this function is going to work the biggest part of programming is managing part of programming is managing cognitive load nobody is smart enough to

[13:27] hold anything but the most simple computer program in the head all at once so it makes sense to divide a task into smaller parts so that you can only have to understand one part at a time assign to some tree make some tree from term

[13:43] tree plus tree and expression tree return just some tree and the final expression offset solving the definition of pars plus is pretty simple you can

[13:56] just check that the token at the offset is plus and then return the offset increment entered by one for all of the other pars literals like plus times and

[14:08] the numbers and Open Bracket and close bracket I'm just going to assume that they have the same type of code here let's go and Define pars term the first thing you're going to realize that it's going to be basically the same code for

[14:24] parse expression with a few words changed we could just cut and paste the definition and then change all the names yeah did you just copy paste that from somewhere that's programming it would look something like this this in fact is

[14:38] something that's often done with a lot of production code frequently we use cut and paste to reuse code it is not the best practice but it is something that happens in real world because we don't have much time however

[14:54] we can also make use of a much more powerful tool we can abstract out the common elements in these two functions we are going to create what is called a higher level function a function that takes in and returns functions to make

[15:11] this more convenient let's first Define a type for our parser functions the type parser is defined as a function that takes an array of token and an

[15:24] that takes an array of token and an integer and maybe returns a pair of pars tree and integer also we're going to have a function type for the thing that have a function type for the thing that creates the new parse tree from the code

[15:39] below we'll call it tree lifter type tree lifter is defined as a function it takes a parse tree and Returns the fars tree with these two types defined we can

[15:51] now go on and Define our new function as always we set up its types to give us an understanding of what it's going to be doing the function parse alt takes an doing the function parse alt takes an array of pairs of parser and tree lifter

[16:06] and puts them in to a variable called parses it will then return a parser to support the functions we've currently defined in this program we would only need something that supports two Alternatives however making something

[16:22] that supports an arbitrary number of Alternatives is almost as easy and will allow us to extend this program to more complex grammars sometimes one of the dangers in programming is over generalizing

[16:37] creating a complex solution that handles more cases than you need however in this simple situation I don't think it's going to be a problem since we know that this has to return a parser function let's do that as the first step if we

[16:52] declare a function without a name it becomes an anonymous function return a function that takes an array of token into a variable called tokens and an integer into a variable called offset and maybe returns a pair of a parse tree

[17:09] and maybe returns a pair of a parse tree and an integer next we're going to use a and an integer next we're going to use a for Loop to step over each element in our parser array for each element in parses assign that pair to the variables

[17:25] parses assign that pair to the variables p and TL we can use the code we used before but adapted for our generic case maybe element assigned to the variable maybe element the value returned by calling the function p on tokens and

[17:43] offset in the case that maybe element is the just case return just the pair of the just case return just the pair of element processed through TL and the element offset if we get through all of the loop that means we've must have

[17:59] tried all the alternatives so we've returned nothing to indicate that this attempt didn't work return nothing with this new function we can

[18:11] rewrite the parser functions we had in this pseudo code assigning an anonymous function to a name makes it into a named function assign to parse expression the

[18:23] return value of parse alt taking an array of par sum expression from sum and parse term expression from term assign to parse term the return value of parse

[18:38] alt pass product term from product plus operand term from operand this taking out repeated code and replacing it with more compact code is called refactoring

[18:50] and is a very common task though sometimes in a professional setting you can take refactoring too far and create code that is unreadable abstract and

[19:03] dense knowing when to stop refactoring and when to start is a judgment call that you tend to learn from with experience now we know that pars product

[19:15] is going to be just like path sum let us create a higher level function for doing a sequence of parser first we'll create a handy helper type the type tree Joiner

[19:27] is a function that takes an array of pars tree and returns a pass tree now we can Define our sequence function function path sequence array of parser into parsers tree Joiner into Joiner return the parser again we know it's

[19:44] going to return an anonymous function so we can just jot that down this time we are going to have to add another for Loop going over the elements in the

[19:56] parser array processing them one after the other in most languages we would have have to declare an array to put the subtrees in but since this is pseudo code we are just going to act like the language knows what we intend to do for

[20:11] language knows what we intend to do for each value between 0 and the last index each value between 0 and the last index of the array parses put that into I then assigned to maybe element the value returned by calling the I element in the

[20:28] returned by calling the I element in the pars's array with the values tokens and offset in the case that maybe term is a just value assign that maybe term is a just value assign the eighth element of subtrees The

[20:43] Returned parsing tree and update offset to the new offset value returned from the parser if the case was nothing then immediately return nothing then if we

[20:55] make it through the loop we combine all the subtrees return just a pair containing the value returned from calling tree Joiner on the sub trees and

[21:08] offset now we can refactory this all and adjust the other functions to support it adjust the other functions to support it parse sum is defined as Pi sequence of the array containing pars term Pass Plus pass expression and a make some tree

[21:26] pass expression and a make some tree while pars product is defined by the return value of pars sequence for parse operand past times and past term with make Prodigy and now we can make a parser for the operand parse operand is

[21:43] parser for the operand parse operand is defined by pars Alt with pars number and make operand from number or parse brackets make operand from brackets and brackets make operand from brackets and we can finish it off with a parser for

[21:57] the brackets case parse brackets is defined as past sequence for parse Open Bracket Parts expression parse close bracket make brackets I was going to do bracket make brackets I was going to do a step-by-step animation of how this

[22:12] algorithm passes honestly it didn't turn out that good so instead I'm going to put a link in the description if you would like to see it the top down parser spends a lot of its time trying Alternatives and having

[22:26] to roll back to try other Alternatives but since I keep calling this a top-down parser you might guess that there's an alternative bottom-up parser if this

[22:38] video generates enough interest I'll do a follow-up video on bottom-up pauses a follow-up video on bottom-up pauses and perhaps Lexus as well thank you very much for watching this video and if you want to see more of my content please

[22:53] consider subscribing and sharing it to your friends who are interested in topics like this thank you very much