1 00:00:02,840 --> 00:00:07,338 In this video, we're gonna talk about the main difficulty with Recursive Descent 2 00:00:07,338 --> 00:00:15,459 Parsing, a problem known as Left Recursion. Let's consider a very simple 3 00:00:15,459 --> 00:00:21,799 grammar that consist of only one production, s goes to s followed by a. So 4 00:00:21,799 --> 00:00:27,641 the Recursive Descent Algorithm for this production is the following. So, we just 5 00:00:27,641 --> 00:00:33,849 have a function called s1 for the first production of s. And it's going to succeed 6 00:00:33,849 --> 00:00:40,130 if the function s succeeds and then after that succeeds we see a terminal a in the 7 00:00:40,130 --> 00:00:45,961 input stream. And then we have to write a function for the symbol s itself and since 8 00:00:45,961 --> 00:00:51,461 there's only one alternative, there's only one production for s we don't need to 9 00:00:51,461 --> 00:00:56,755 worry about backtracking or anything. So as we'll succeed exactly when as one 10 00:00:56,755 --> 00:01:02,392 succeed. There's only one possibility in this case and now I think you can see the 11 00:01:02,392 --> 00:01:07,755 problem what's going to happen. Well, when we go to parse an input string, we're 12 00:01:07,755 --> 00:01:12,918 going to call the function s which is going to call the function s1. And then 13 00:01:12,918 --> 00:01:17,261 what the function as one gonna do well, the very first thing it's going to do is 14 00:01:17,261 --> 00:01:21,605 to call the function s again. And as a result, the function s is going to go into 15 00:01:21,605 --> 00:01:26,002 an infinite loop and we're never going to succeed in parsing any input. This will 16 00:01:26,002 --> 00:01:32,112 always go into an infinite loop. So, The reason that this, this grammar doesn't 17 00:01:32,112 --> 00:01:37,266 behave very well is because it is left recursive. And a left recursive grammar is 18 00:01:37,266 --> 00:01:42,484 any grammar that has a non-terminal where if you start with that non-terminal and 19 00:01:42,484 --> 00:01:47,257 you do some non-empty sequence of re-writes. Notice the plus there. You have 20 00:01:47,257 --> 00:01:51,775 to do more than one re-write. So, if you're actually doing a sequence of 21 00:01:51,775 --> 00:01:56,929 replacements, you get back to a situation where you have the same symbol still in 22 00:01:56,929 --> 00:02:02,020 the left most position. And you can see, this is not going to be good for parsing. 23 00:02:02,020 --> 00:02:11,450 So, in the case of this grammar up here, what happens while we get s goes to sa it 24 00:02:11,450 --> 00:02:17,576 goes to saa goes to saaa. And so on and we can always get to a situation where we 25 00:02:17,576 --> 00:02:22,762 have a long string of a's and an s on the left end of the string. And if we always 26 00:02:22,762 --> 00:02:27,764 have an s on the left end of the string, we can never manage any input because the 27 00:02:27,764 --> 00:02:32,645 only way we manage input is if the first thing we generate is a terminal symbol. 28 00:02:32,645 --> 00:02:36,977 But if the first thing is always a non-terminal, we will never make any 29 00:02:36,977 --> 00:02:41,735 progress. And, it just doesn't work. I mean, Recursive Descent does not work with 30 00:02:41,735 --> 00:02:47,552 Left-Recursive Grammars. Well, this seems like a major problem with recursive to 31 00:02:47,552 --> 00:02:52,461 same parsing. It is a problem but as we'll see shortly it's really not so major. So 32 00:02:52,461 --> 00:02:57,250 let's consider a left-recursive grammar that slightly more general form. So here 33 00:02:57,250 --> 00:03:02,039 we have two productions now for s, s goes to s followed by something alpha or it 34 00:03:02,039 --> 00:03:06,785 goes to something else that doesn't mention s and let's call that Beta. And if 35 00:03:06,785 --> 00:03:12,241 you think about the language that this generates, it's gonna join all strings 36 00:03:12,241 --> 00:03:17,909 that start with a beta and then follow, and followed by any number of alphas. And, 37 00:03:17,909 --> 00:03:23,647 but it does it in a very particular way. So if I write out some, a derivation here 38 00:03:23,647 --> 00:03:29,599 where I used a few, where I used the first production a few times. You can see what's 39 00:03:29,599 --> 00:03:35,473 going on. So again, s goes to s followed by alpha. And then s goes to s followed by 40 00:03:35,473 --> 00:03:41,395 alpha, alpha and then s goes to s followed by alpha, alpha, alpha and if I repeat 41 00:03:41,395 --> 00:03:48,570 this, I get. S followed by any number of alphas and then in one more step, I can. 42 00:03:48,747 --> 00:03:53,724 Put in beta and I get beta followed by any number of alpha. So, that's the proof that 43 00:03:53,724 --> 00:03:58,523 it generates that language. That language that begins with a beta and has some 44 00:03:58,523 --> 00:04:03,322 sequence of alphas but you can see that it does it right to left, it produces the 45 00:04:03,322 --> 00:04:08,062 right under the string first and in fact the very last thing it produces if the 46 00:04:08,062 --> 00:04:13,232 first thing that appears in the input and that's why. It doesn't work with Recursive 47 00:04:13,232 --> 00:04:18,313 Descent Parsing because Recursive Descent Parsing wants to see the first part of the 48 00:04:18,313 --> 00:04:23,154 input first and then work left to right. And this grammar is built to produce the 49 00:04:23,154 --> 00:04:28,495 string right to left. And therein lies the idea that allow us to fix the problem so 50 00:04:28,495 --> 00:04:33,964 we can generate exactly the same language producing the strings from left to right 51 00:04:33,964 --> 00:04:39,235 instead of right to left and th e way we do that is to replace left-recursion by 52 00:04:39,235 --> 00:04:44,961 right-recursion. And this requires us to add one more symbol in this case to the 53 00:04:44,961 --> 00:04:50,582 grammar so instead of having s go to something involving s on the left, we'll 54 00:04:50,582 --> 00:04:56,421 have s go to beta so the first thing notice in the very first position and then 55 00:04:56,421 --> 00:05:02,261 it goes to s prime and what does s prime do, well s prime produce what you would 56 00:05:02,261 --> 00:05:08,471 expect, a sequence of alphas and it could be the empty sequence. And if you write 57 00:05:08,471 --> 00:05:17,019 out some you know? Example derivation here we'll have s goes to beta s prime. Which 58 00:05:17,019 --> 00:05:23,385 goes to now using the rules for s prime goes to beta alpha s prime, Goes to beta 59 00:05:23,385 --> 00:05:29,168 alpha. Alpha s prime goes to and after any number of sequent, any number of rewrites 60 00:05:29,168 --> 00:05:34,672 we get beta followed by sub sequence of alphas followed by s prime. And then in 61 00:05:34,672 --> 00:05:40,594 one more step we use the Epsilon Rule here and we wind up with beta followed by some 62 00:05:40,594 --> 00:05:46,168 number of alphas. And so you can see it generates exactly the same string as the 63 00:05:46,168 --> 00:05:50,836 first grammar but it does so in a right-recursive way instead of a 64 00:05:50,836 --> 00:05:59,418 left-recursive way. So in general, we may have many productions some of which are 65 00:05:59,418 --> 00:06:05,267 left-recursive and some of which are not. And the language produced by this 66 00:06:05,267 --> 00:06:11,659 particular form of grammar here is gonna be all the strings. They are derived from 67 00:06:11,659 --> 00:06:17,827 asst start with one of the betas. So one of the things here that doesn't involve s 68 00:06:17,827 --> 00:06:23,422 and it continues with zero or more instances of the alphas. And we can do 69 00:06:23,422 --> 00:06:28,553 exactly the same trick. This is just generalizing the idea that we had before 70 00:06:28,553 --> 00:06:34,083 where we only have one beta and one alpha to many betas and many alphas and so the 71 00:06:34,083 --> 00:06:38,281 general form of rewriting this left-recursive grammar in using 72 00:06:38,281 --> 00:06:42,945 right-recursion is given here. So here each of the betas appears as an 73 00:06:42,945 --> 00:06:48,342 alternative in the first position. We only need one additional symbol s prime and 74 00:06:48,342 --> 00:06:53,540 then the s prime rules is take care of generating any sequence of the alpha i. 75 00:06:55,500 --> 00:07:00,719 Now it turns out that, that isn't the most general form of left recursion. There are 76 00:07:00,719 --> 00:07:06,191 even other ways to encode left recursion in a grammar and here's another way that's 77 00:07:06,191 --> 00:07:11,264 important. So, we may have a grammar that where nothing is obviously left-recursive. 78 00:07:11,264 --> 00:07:16,511 So if you look here, you see that the s doesn't even appear on the right hand side 79 00:07:16,511 --> 00:07:21,682 here. And if you look at this production here, a doesn't appear anywhere on the 80 00:07:21,682 --> 00:07:26,608 right hand side so there's no what's called Immediate Left-Recursion in this 81 00:07:26,608 --> 00:07:31,727 grammar. But on the other hand, there is left-recursion because s goes to a alpha 82 00:07:31,727 --> 00:07:36,909 and then a can go to s beta. And so there we have in, in two steps produce another 83 00:07:36,909 --> 00:07:42,283 string with s at the left end and so this is still a Left-Recursive Grammar. We just 84 00:07:42,283 --> 00:07:46,954 delayed it by inserting other non-terminals at the left most position 85 00:07:46,954 --> 00:07:51,705 before we got back to s. So, this left recursion can also be eliminated. In fact, 86 00:07:51,705 --> 00:07:56,469 this can be eliminated automatically, it doesn't even require human intervention. 87 00:07:56,469 --> 00:08:01,292 And if you look at any of the text pretty quickly in the Dragon Book, you'll find 88 00:08:01,292 --> 00:08:07,009 algorithms were doing that. So to summarize our discussion of Recursive 89 00:08:07,009 --> 00:08:11,801 Descent Parsing, it's a simple in general parsing strategy. You can parse any 90 00:08:11,801 --> 00:08:16,471 Context-Free Grammar using Recursive Descent, so it's very general in that 91 00:08:16,471 --> 00:08:20,293 respect. It cannot work with Left-Recursive Grammar so you must 92 00:08:20,293 --> 00:08:24,617 eliminate The Left Recursion. Now in principle, this can be automatically. You 93 00:08:24,617 --> 00:08:29,010 can have Algorithms that will eliminate the Left Recursion. In practice, people 94 00:08:29,010 --> 00:08:33,572 eliminate the Left Recursion by hand and the reason for that is that you need to 95 00:08:33,572 --> 00:08:37,966 know what the grammar is that you're using so that you can write the semantic 96 00:08:37,966 --> 00:08:42,359 actions. And we haven't talked about semantic actions yet but we will see them 97 00:08:42,359 --> 00:08:46,937 shortly. And because you wanted to know exactly what grammar, form of grammar it 98 00:08:46,937 --> 00:08:51,703 has, people generally do the elimination of left-recursion on their own. But that's 99 00:08:51,703 --> 00:08:56,063 not difficult to do. And in fact, recursion descent is a popular strategy in 100 00:08:56,063 --> 00:09:00,364 practice. There are a lot to be more complicated, but actually compilers in 101 00:09:00,364 --> 00:09:04,433 fact with complicated grammars use recursive descent because it is so 102 00:09:04,433 --> 00:09:09,200 general. So, for example GCC is front-end is a handwritten Recursive Descent Parser.