1 00:00:02,900 --> 00:00:08,310 In this video, we're going to talk about our first parsing algorithm, recursive 2 00:00:08,310 --> 00:00:15,195 descent parsing. So Recursive Descent is what is called a top-down parsing 3 00:00:15,195 --> 00:00:20,527 algorithm and you might suspect that there are also bottom-up algorithms and they are 4 00:00:20,527 --> 00:00:25,796 indeed such things but we will be talking about them later but in a top-down parsing 5 00:00:25,796 --> 00:00:30,694 algorithm, the parse tree is constructed from the top so starting with the root 6 00:00:30,694 --> 00:00:35,789 node and from left to right. And so the terminals then will be seen in the order 7 00:00:35,789 --> 00:00:40,958 that they appear in the token string. So for example, if I have this token string 8 00:00:40,958 --> 00:00:45,997 here, this is a hypothetical parse tree that I could construct and the numbers 9 00:00:45,997 --> 00:00:51,359 here correspond to the order in which the nodes of this parse tree are constructed. 10 00:00:51,359 --> 00:00:56,593 So we have to begin at the roots, that's the first thing that happens and then if 11 00:00:56,593 --> 00:01:00,955 T2 is a. Belongs here in the parse tree. That would be next thing that happened but 12 00:01:00,955 --> 00:01:05,164 then if we have a nonterminal of the next position, that will be number three and 13 00:01:05,164 --> 00:01:09,166 then if it has children, well the left most one should be going left to right 14 00:01:09,166 --> 00:01:13,323 will be the fourth thing to be generated. And then let's say the two children of 15 00:01:13,323 --> 00:01:17,740 number four are both terminals that would be the next two terminals in the input and 16 00:01:17,740 --> 00:01:21,949 so on. The next thing that'll happen is the second child of number three and then 17 00:01:21,949 --> 00:01:27,870 the last two terminals appearing in left to right order. So let's consider this 18 00:01:27,870 --> 00:01:34,475 grammar for integer expressions and let's look at a particular input, a very simple 19 00:01:34,475 --> 00:01:40,022 one, just open paren five, close paren. And now, what we're going to do is we're 20 00:01:40,022 --> 00:01:44,083 going to parse this using a recursive descent strategy. I'm not gonna actually 21 00:01:44,083 --> 00:01:48,301 show you any pseudocode or anything like that. I'm just going to walk through how 22 00:01:48,301 --> 00:01:52,475 this, how this input string would be parsed. But using this grammar and the 23 00:01:52,475 --> 00:01:57,655 Recursive Descent Algorithm and the basic idea is that we begin with a nonterminal, 24 00:01:57,655 --> 00:02:02,899 we begin with the root node and we always try the rules for nonterminal in order. So 25 00:02:02,899 --> 00:02:08,204 we will begin by starting with e goes to t and if that doesn't work, we'll try e goes 26 00:02:08,204 --> 00:02:13,011 to t + e. So, this is gonna be a top down algorithm beginning at the root. We're 27 00:02:13,011 --> 00:02:17,692 gonna work from left to right, we try the productions in order and when the 28 00:02:17,692 --> 00:02:22,810 productions fail, we may have to do some back tracking in order to try alternative 29 00:02:22,810 --> 00:02:27,140 productions. There are three parts. There's the grammar that we're using. 30 00:02:27,140 --> 00:02:31,326 There is the parse tree that we're building and initially that's just the 31 00:02:31,326 --> 00:02:35,739 root of the parse tree 3e and finally there's the input that we're processing 32 00:02:35,739 --> 00:02:40,265 and we'll indicate our position in the input, how much of the input we have read 33 00:02:40,265 --> 00:02:44,847 by this big fat red arrow and it always points to the next terminal symbol to be 34 00:02:44,847 --> 00:02:49,090 read, The next token to be read. So in this case, we're starting with an open 35 00:02:49,090 --> 00:02:54,017 paren. Okay? And also in the grammar, you can see the highlighting here the brighter 36 00:02:54,017 --> 00:02:59,010 red color indicates which production we're going to try. So, we're going to begin to 37 00:02:59,010 --> 00:03:03,540 build our Parse Tree by trying production e goes to t, and what does that mean? 38 00:03:03,540 --> 00:03:08,243 Well, that means we make t the child of e and then we continue trying to build the 39 00:03:08,243 --> 00:03:12,947 Parse Tree. Well, so remember we're going left to right and top-down so now, t is an 40 00:03:12,947 --> 00:03:17,536 unexpanded nonterminal, is the only unexpanded nonterminal so we have to work 41 00:03:17,536 --> 00:03:22,182 on it. And what are we going to do, well we're going to try a production for t and 42 00:03:22,182 --> 00:03:26,808 since we haven't tried any yet, we'll just try the first one, t goes to it. So the 43 00:03:26,808 --> 00:03:31,945 next step is to make nth a child with t and that's what our parse tree looks like. 44 00:03:31,945 --> 00:03:36,957 And now, we actually have something that we can check. We can check whether we're 45 00:03:36,957 --> 00:03:42,275 making progress. So observe that as long as we're generating nonterminals, we don't 46 00:03:42,275 --> 00:03:47,244 really know whether we're on the right track or not. We have no way to check 47 00:03:47,244 --> 00:03:52,017 whether the nonterminals that we're generating are gonna produce the, the 48 00:03:52,017 --> 00:03:57,052 input string. But once we generate a terminal symbol, then we can compare that 49 00:03:57,052 --> 00:04:01,629 with the next input token to see if they're the same and in this case, 50 00:04:01,629 --> 00:04:06,729 unfortunately they're not. So, the nth that we generated here doesn't match the 51 00:04:06,729 --> 00:04:11,633 open paren in the input and so clearly this parse, th is parsing strategy or 52 00:04:11,633 --> 00:04:16,105 this. Parse Tree that we're building isn't going to work out. So, what we're going to 53 00:04:16,105 --> 00:04:20,517 have to do is we're gonna have to back track. That means, we're gonna undo one or 54 00:04:20,517 --> 00:04:24,928 more of our decisions. We're gonna go back to our last decision point and see if 55 00:04:24,928 --> 00:04:29,127 there's another alternative to try. So what's the last decision we made, well we 56 00:04:29,127 --> 00:04:33,326 decide to use t goes to nth, so we can undo that and then we could try the next 57 00:04:33,326 --> 00:04:38,592 production for t. And that happens to be t goes to n t so expand t using that 58 00:04:38,592 --> 00:04:43,670 production and now once again, we generated a terminal in the left most 59 00:04:43,670 --> 00:04:49,177 position and so now we're able to compare that with the input and once again 60 00:04:49,177 --> 00:04:54,683 unfortunately, the nth token does not match the open paren so we have to back 61 00:04:54,683 --> 00:05:01,632 track again. So we undo that decision. And this takes us back to trying alternatives 62 00:05:01,632 --> 00:05:08,394 for t. There's one more possibility, and that's the t goes to (e). So we expand t 63 00:05:08,658 --> 00:05:16,265 using that production. And now, we can compare the token open paren. With, is 64 00:05:16,265 --> 00:05:21,391 this open paren? With the open paren in the input and they match. And so, that's 65 00:05:21,391 --> 00:05:26,582 good. That means that we're, we might be on the right track. And since they match, 66 00:05:26,582 --> 00:05:32,102 anything that we do in the future is going to have to match the different input and 67 00:05:32,102 --> 00:05:37,228 so we'll advance the input pointer. So now, where we're gonna work on next? Well, 68 00:05:37,228 --> 00:05:42,420 we have to expand this non-terminal e and we're gonna do the same thing we did 69 00:05:42,420 --> 00:05:48,130 before. We're just gonna start with the first production. So we have e goes to t 70 00:05:48,130 --> 00:05:53,804 and then we have to work on t, so we're gonna pick the first production for t and 71 00:05:53,804 --> 00:05:59,197 we have t goes to int. So now, we can compare. Is int matching int in the input? 72 00:05:59,197 --> 00:06:04,797 And if it does and so we advance the input pointer again, And now we're here and 73 00:06:04,797 --> 00:06:10,250 what's left, well we progressed to this point. We're looking at that open paren 74 00:06:10,250 --> 00:06:16,122 and that also matches. So that matches the input and now we've matched everything in 75 00:06:16,122 --> 00:06:21,715 the parse tree and our input pointer is at the end of the string and so this is 76 00:06:21,715 --> 00:06:28,326 actually a successful parse of the input, of the input string. And so that means th 77 00:06:28,326 --> 00:06:32,820 at we accept and the parser terminates successfully.