1
00:00:00,640 --> 00:00:04,200
In this video, I'm going to cover a 
limitation of the Recursive Descent 

2
00:00:04,200 --> 00:00:09,950
Algorithm that I presented last time. 
Here's the grammar from our last 

3
00:00:09,950 --> 00:00:14,900
presentation, and here's its 
implementation again, as a set of 

4
00:00:14,900 --> 00:00:18,540
mutually recursive function that 
together, implement this simple recursive 

5
00:00:18,540 --> 00:00:21,700
descent strategy. 
And now, let's think about what happens. 

6
00:00:21,700 --> 00:00:28,670
When we go to parse the input int, 
simplest possible input strength. 

7
00:00:28,670 --> 00:00:33,050
Well, let's work through it. 
So remember, we start with the function 

8
00:00:33,050 --> 00:00:37,590
that implements all the productions for 
the non-terminal e. 

9
00:00:37,590 --> 00:00:40,100
And so what we're going to do here, we're 
going to call e. 

10
00:00:40,100 --> 00:00:43,600
And that will try calling E1. 
All right? 

11
00:00:43,600 --> 00:00:46,750
And what is E1 going to do? 
E1 is going to call T. 

12
00:00:46,750 --> 00:00:50,135
Because, of course, the first production 
is E goes to T. 

13
00:00:50,135 --> 00:00:55,548
So let's take a look at what T does. 
T is going to try out the production of 

14
00:00:55,548 --> 00:01:00,323
T1, all right? 
And what does T1 do? 

15
00:01:00,323 --> 00:01:04,810
Well, T1 recognizes an int. 
Okay, so that's good. 

16
00:01:04,810 --> 00:01:11,130
And it will match it and return, okay, 
and then E will return and we will 

17
00:01:11,130 --> 00:01:14,274
succeed in parsing. 
And I forgot to mention it, also the 

18
00:01:14,274 --> 00:01:20,120
process, the input point will be moved 
across the int, and so when we're done 

19
00:01:20,120 --> 00:01:24,120
you will return, and we will have 
succeeded in parsing the string int 

20
00:01:24,120 --> 00:01:30,088
because E return true the production for 
E return true, and we consumed all of the 

21
00:01:30,088 --> 00:01:31,600
input. 
All right? 

22
00:01:31,600 --> 00:01:39,820
So now, let's consider a slightly more 
complicated example, okay? 

23
00:01:39,820 --> 00:01:47,691
So let's try the input string Int times 
int. 

24
00:01:47,691 --> 00:01:51,764
All right? 
So again, we start with the production E. 

25
00:01:51,764 --> 00:01:55,430
Okay? 
And the first thing we'll do, is we'll 

26
00:01:55,430 --> 00:01:58,175
try the production E1. 
Same thing we did last time. 

27
00:01:58,175 --> 00:02:05,640
E1 is going to call the function T. 
And T is going to try the first 

28
00:02:05,640 --> 00:02:08,580
production for T. 
Which, again, is the production int. 

29
00:02:08,580 --> 00:02:11,420
Okay? 
And the input pointer, of course, is 

30
00:02:11,420 --> 00:02:16,010
here, and then it will try to match that 
against an int. 

31
00:02:16,010 --> 00:02:18,420
Okay? 
If I match the first token in the input 

32
00:02:18,420 --> 00:02:22,035
stream against the, the terminal int. 
And it will succeed. 

33
00:02:22,035 --> 00:02:25,160
Okay? 
So the input pointer will be moved over. 

34
00:02:25,160 --> 00:02:26,865
So T1 will return true. 
All right? 

35
00:02:26,865 --> 00:02:29,822
And as a result. 
This right hand side here of the function 

36
00:02:29,822 --> 00:02:31,280
T will also succeed, because T1 returns 
true, so T will return true. 

37
00:02:31,280 --> 00:02:35,590
Okay? 
Therefore, E1 will return true and E, E1 

38
00:02:35,590 --> 00:02:44,880
returning true will cause E to return 
true. 

39
00:02:44,880 --> 00:02:49,410
And in fact that will be the end of the 
execution of the program will terminate. 

40
00:02:49,410 --> 00:02:53,450
E will return true and the input player 
will only have advanced as far as int, 

41
00:02:53,450 --> 00:02:57,965
and so we will reject the parse. 
This is actually, ends up getting 

42
00:02:57,965 --> 00:03:02,444
rejected. 
And the question of course is what 

43
00:03:02,444 --> 00:03:06,716
happened? 
All right. 

44
00:03:06,716 --> 00:03:10,050
Why didn't we succeed in parsing this 
input? 

45
00:03:10,050 --> 00:03:12,830
Which is clearly in the language of this 
grammar. 

46
00:03:12,830 --> 00:03:15,040
Well, the story here is actually a little 
bit interesting. 

47
00:03:15,040 --> 00:03:23,270
What happened is down here when we 
discovered that Int matched the first 

48
00:03:23,270 --> 00:03:26,539
production for T, we said that T was 
done. 

49
00:03:26,539 --> 00:03:31,260
Okay, T had succeeded, had matched it's 
input. 

50
00:03:31,260 --> 00:03:36,800
And then, when E ultimately returns and 
the whole parse fails, because we haven't 

51
00:03:36,800 --> 00:03:42,070
consumed the input, we don't have a way 
to back track and try another alternative 

52
00:03:42,070 --> 00:03:45,780
for T. 
If we were going to succeed we would have 

53
00:03:45,780 --> 00:03:50,930
to say, oh, well even though, we found a 
production for T that matched part of the 

54
00:03:50,930 --> 00:03:53,660
input. 
Since the overall parts fail, that must 

55
00:03:53,660 --> 00:03:57,650
not have been the right production to 
choose for T. 

56
00:03:57,650 --> 00:04:00,270
Maybe we should try some other 
productions for T. 

57
00:04:00,270 --> 00:04:04,300
And in fact if we'd tried the second 
production for T, T2. 

58
00:04:04,300 --> 00:04:09,350
We would have matched Int times T, and 
then we probably would of succeeded. 

59
00:04:09,350 --> 00:04:12,090
We would have been able to manage int 
times int. 

60
00:04:12,090 --> 00:04:13,790
Okay? 
And so, the problem here is that even 

61
00:04:13,790 --> 00:04:18,680
though there is backtracking within a 
production; while we're trying to find a 

62
00:04:18,680 --> 00:04:21,052
production that works for a given 
non-terminals. 

63
00:04:21,052 --> 00:04:25,830
So, while there is backtracking For a 
non-terminal during the time that we're 

64
00:04:25,830 --> 00:04:29,555
trying to find a production that works 
for that non-terminal, but there is no 

65
00:04:29,555 --> 00:04:33,655
backtracking once we have found a 
production that succeeds for 

66
00:04:33,655 --> 00:04:36,160
non-terminals. 
So once a non-terminal commits and 

67
00:04:36,160 --> 00:04:40,940
returns and says, I have found a way to 
parse part of the input using one of my 

68
00:04:40,940 --> 00:04:43,510
productions. 
There's no way, in this particular 

69
00:04:43,510 --> 00:04:47,370
structure, this particular algorithm, to 
go back and revisit that decision and try 

70
00:04:47,370 --> 00:04:50,890
a different production. 
All right? 

71
00:04:50,890 --> 00:04:54,960
So the problem is that if a production 
for non-terminal x succeeds, there's no 

72
00:04:54,960 --> 00:04:58,270
way to backtrack to try a different 
production for x later. 

73
00:04:58,270 --> 00:05:01,350
So once x, once the function for x has 
returned. 

74
00:05:01,350 --> 00:05:03,620
And we're really committed to that 
production. 

75
00:05:03,620 --> 00:05:08,890
Now that means that the particularly 
Recursive Descent Algorithm that I should 

76
00:05:08,890 --> 00:05:13,080
in the last video, is not completely 
general, and Recursive Descent is a 

77
00:05:13,080 --> 00:05:16,606
general technique. 
There are algorithms for Resursive 

78
00:05:16,606 --> 00:05:20,850
Descent parsing that can parse any 
grammar. 

79
00:05:20,850 --> 00:05:23,930
That can implement the full language of 
any grammar. 

80
00:05:23,930 --> 00:05:28,940
And they have more sophisticated 
backtracking, than what I showed in the 

81
00:05:28,940 --> 00:05:33,980
algorithm that I presented last time. 
Now the reason for showing this 

82
00:05:33,980 --> 00:05:37,290
particular algorithm is that it's easy to 
implement by hand. 

83
00:05:37,290 --> 00:05:41,060
So this is actually an algorithm, or 
approach to Recursive Descent that while 

84
00:05:41,060 --> 00:05:45,320
it has this limitation, as you can see, 
it's very mechanical and very 

85
00:05:45,320 --> 00:05:50,890
straightforward to design a parser for a 
given for a given grammar. 

86
00:05:50,890 --> 00:05:55,080
And it will work for a rather large 
class, class of grammar. 

87
00:05:55,080 --> 00:06:00,210
So in particular, it'll work for any 
grammar where for any non-terminal at 

88
00:06:00,210 --> 00:06:03,640
most one production can succeed. 
So if you know from the way that you've 

89
00:06:03,640 --> 00:06:08,070
built your grammar, that in any 
situation, that the grammar can get into 

90
00:06:08,070 --> 00:06:12,820
or the Recursive Descent Algorithm can 
get into during parsing, that at most one 

91
00:06:12,820 --> 00:06:17,360
production can succeed. 
Then it this, this parsing is gradually 

92
00:06:17,360 --> 00:06:20,400
will be sufficient, because there will 
never be, once you find a production that 

93
00:06:20,400 --> 00:06:24,300
succeeds, there will never be a need to 
go back and revisit that decision, 

94
00:06:24,300 --> 00:06:28,040
because it must be the case that none of 
the other productions could have 

95
00:06:28,040 --> 00:06:31,770
succeeded. 
And it turns out that the example grammar 

96
00:06:31,770 --> 00:06:36,910
that we're working with in the last 
couple of videos could actually be 

97
00:06:36,910 --> 00:06:39,690
written to work with this algorithm. 
All right. 

98
00:06:39,690 --> 00:06:41,760
And we would have to left factor the 
grammar. 

99
00:06:41,760 --> 00:06:45,243
Well, actually there's more than one way 
to rewrite the grammar to work with this 

100
00:06:45,243 --> 00:06:48,660
Recursive Decent Algorithm but one way to 
do it Is to left factor it. 

101
00:06:48,660 --> 00:06:53,130
I'm not going to say any more about left 
factoring in this video, because that's 

102
00:06:53,130 --> 00:06:56,492
going to be a topic of a video that's 
coming up shortly.