1
00:00:03,960 --> 00:00:09,684
Welcome back, in this video we're gonna
talk about the key ideas behind techniques

2
00:00:09,684 --> 00:00:17,961
for recognizing handles. There is good
news and bad news when it comes to

3
00:00:17,961 --> 00:00:23,238
recognizing handles. The bad news is that
there is no known efficient algorithm that

4
00:00:23,238 --> 00:00:28,143
recognizes handles in general. So for an
arbitrary grammar, we don't have a fast

5
00:00:28,143 --> 00:00:32,985
way to find the handles when we're
parsing. The good news is that there are

6
00:00:32,985 --> 00:00:37,889
heuristics for guessing handles, and for
some context free grammars, for some

7
00:00:37,889 --> 00:00:42,794
fairly large classes of context free
grammars, these heuristics always identify

8
00:00:42,794 --> 00:00:49,049
the handles correctly. We can illustrate
the situation with a Venn diagram. If we

9
00:00:49,049 --> 00:00:54,026
start with a set of all context free
grammars, then the unambiguous context

10
00:00:54,026 --> 00:00:59,401
free grammars are a sub-set of those, and
then an even smaller set are called the

11
00:00:59,401 --> 00:01:04,246
LR(k) grammars. And here, just to remind
you, 'l' stands for left to right scan,

12
00:01:04,246 --> 00:01:09,290
'r' stands for rightmost variation, and
'k' stands for the number of tokens of

13
00:01:09,290 --> 00:01:14,807
look ahead. Now the LRK grammars are one
of the most general deterministic families

14
00:01:14,807 --> 00:01:19,716
of deterministic grammars that we know of.
But those aren't the ones that are

15
00:01:19,716 --> 00:01:24,626
actually used in practice. Most of the
bottom up tools that are practical, use

16
00:01:24,626 --> 00:01:29,720
what are called the LALRK grammars, which
are a subset of the LRK grammars. And then

17
00:01:29,720 --> 00:01:34,936
what we're gonna talk mostly about is a
simplification of those called the simple

18
00:01:34,936 --> 00:01:39,110
LR grammars, or the SLRK context free
grammars. And these containment

19
00:01:39,110 --> 00:01:44,185
relationships or [inaudible] that is,
there are grammars that are [inaudible]. R

20
00:01:44,185 --> 00:01:50,490
k but not s l r k, for every k, and
similarly there are grammars that are l r

21
00:01:50,490 --> 00:01:59,354
k for every k that are not l a l r k. As
we've already said, it's not obvious how

22
00:01:59,354 --> 00:02:03,962
to detect handles. So, what does the
parser know? Well, it sees the stack. At

23
00:02:03,962 --> 00:02:09,138
each step it knows the stack that it has
already, constructed. And so let's see how

24
00:02:09,138 --> 00:02:14,125
much progress we can make just thinking
about, what information we can get from

25
00:02:14,125 --> 00:02:18,860
the stack. So here's a definition. We're
going to say that alpha is a viable

26
00:02:18,860 --> 00:02:23,720
prefix. If there is some omega, such that
alpha bar omega is a configuration, a

27
00:02:23,720 --> 00:02:28,518
valid configuration of a shift reduce
parse. Now keep in mind that the alpha

28
00:02:28,518 --> 00:02:36,616
here. This is the stack. And the omega
here is the rest of the input. And what

29
00:02:36,616 --> 00:02:41,035
does that means? That means the parser
knows this part. The parser knows alpha,

30
00:02:41,035 --> 00:02:45,569
it doesn't know much of omega. It can do
some look-ahead, it can look at a small

31
00:02:45,569 --> 00:02:50,275
prefix of omega, usually just one token,
but it certainly doesn't know the whole

32
00:02:50,275 --> 00:02:57,675
thing. So what does a viable prefix mean?
Well, a viable prefix is a string that

33
00:02:57,675 --> 00:03:03,013
does not extend past the right end of the
handle. And the reason we call it a viable

34
00:03:03,013 --> 00:03:07,842
prefix is because it is a prefix of the
handle. So as long as the parser has

35
00:03:07,842 --> 00:03:12,858
viable prefixes on the stack, no parsing
error has been detected. And really the

36
00:03:12,858 --> 00:03:17,539
definition is just giving a name to
something, it's not anything very deep,

37
00:03:17,539 --> 00:03:22,157
the fact that alpha bar omega is, is
viable, that's just saying we haven't

38
00:03:22,157 --> 00:03:27,154
encountered an error. That this is some
state of a shift reduce parse. It hasn't

39
00:03:27,154 --> 00:03:32,657
said yet how we're going to identity it or
anything like that; it's just saying that

40
00:03:32,657 --> 00:03:39,813
these are the valid states of shift
reduced parse. Now the definition is

41
00:03:39,813 --> 00:03:45,492
useful in one way if it bring us to the
last important fact, important fact number

42
00:03:45,492 --> 00:03:50,686
three about bottom up parsing. In this
effort, any grammar, the set of viable

43
00:03:50,686 --> 00:03:56,295
prefixes is a regular language, and this
is really an amazing fact, and one that's

44
00:03:56,295 --> 00:04:01,558
going to take us a little while to
demonstrate, but this is the key to bottom

45
00:04:01,558 --> 00:04:07,098
up parsing. At least all the bottom up
parsing tools are based on this fact, that

46
00:04:07,098 --> 00:04:13,548
the set of viable prefix can be recognized
by a finite automaton. So, we're going to

47
00:04:13,548 --> 00:04:18,808
show how to compute this automaton that
accepts the viable prefixes, but first

48
00:04:18,808 --> 00:04:25,554
we're going to need a number of additional
definitions. The first definition we need

49
00:04:25,554 --> 00:04:30,064
is the idea of an item. Now an item is a
production that just has a dot somewhere

50
00:04:30,064 --> 00:04:34,351
on the right hand side. So here's an
example. Let's take the production, T goes

51
00:04:34,351 --> 00:04:38,806
to open paren, E closed paren. What we're
going to do is we're just gonna put the

52
00:04:38,806 --> 00:04:43,093
dot in eve ry possible position on the
right hand side. So we'll have one item

53
00:04:43,093 --> 00:04:47,603
where the dot is all the way at the left
end. We'll have one where the dot is all

54
00:04:47,603 --> 00:04:52,335
the way at the right end. And then we'll
have, items where the dot is between every

55
00:04:52,335 --> 00:04:56,567
pair of consecutive symbols. So in this
case, there are four items for the

56
00:04:56,567 --> 00:05:02,619
production. One special case is, what do
we do with epsilon productions? Well, for

57
00:05:02,619 --> 00:05:07,436
an epsilon production, there is no, there
are no symbols on the right hand side.

58
00:05:07,436 --> 00:05:12,314
We'll just say there is one item, X goes
to dot. And these items, you'll see them

59
00:05:12,314 --> 00:05:17,440
referred to, if you, if you look in help,
pages and in the literature, as, the LR

60
00:05:17,440 --> 00:05:22,771
zero items. Now we're ready to discuss how
we recognize viable prefixes. And the

61
00:05:22,771 --> 00:05:27,891
problem is that the stack has only bits
and pieces of the right hand side of

62
00:05:27,891 --> 00:05:33,074
productions. In general most of the time,
we don't have a complete right hand side

63
00:05:33,074 --> 00:05:38,194
on top of the stack. Most of the time, we
only have a part of the right hand side.

64
00:05:38,194 --> 00:05:43,300
And. It turns out that what is on the
stack is actually not just random it's,

65
00:05:43,300 --> 00:05:48,690
it's it actually has a very special
structure. In, in these bits and pieces

66
00:05:48,690 --> 00:05:54,147
are always prefixes of right hand sides of
productions. That is in any successful

67
00:05:54,147 --> 00:06:00,008
parse what is on the stack always has to
be a prefix of the right hand side of some

68
00:06:00,008 --> 00:06:06,509
production or productions. Let's take a
look at an example. Let's consider the

69
00:06:06,509 --> 00:06:11,604
input open paren, [inaudible] closed
paren. And here's one of our favorite

70
00:06:11,604 --> 00:06:17,257
grammars. Now, this configurations, where
I have open paren E, [inaudible], on the

71
00:06:17,257 --> 00:06:22,836
stack. Remember that this is our stack.
And we have the close [inaudible] in the

72
00:06:22,836 --> 00:06:28,386
input. This is actually a state or a valid
state of a shift [inaudible]. And you can

73
00:06:28,386 --> 00:06:33,888
see here that, open paren E is a prefix of
the production. T goes to open paren E,

74
00:06:33,888 --> 00:06:39,197
close paren. And after we shift the
remaining close paren onto the stack, then

75
00:06:39,197 --> 00:06:44,843
we'll have the complete right hand side,
and it will be ready to reduce. So this is

76
00:06:44,843 --> 00:06:50,530
where the items come in. The item, T goes
to open paren E. Dot, closed paren. This

77
00:06:50,530 --> 00:06:56,461
describes this state of affairs. I t says
that so far, we have seen open paren E of

78
00:06:56,461 --> 00:07:02,195
this production. And we're hoping in the
future to see the closed paren. So another

79
00:07:02,195 --> 00:07:06,190
way of thinking about it is that this item
records the fact that we're working on

80
00:07:06,190 --> 00:07:10,129
this production. And then so far we've
seen this much. Everything to the left of

81
00:07:10,129 --> 00:07:14,240
the dot is what we've already seen and is
what is on the stack and. What is to the

82
00:07:14,240 --> 00:07:18,340
right of the dot is what we're waiting to
see before we could possibly reduce. And

83
00:07:18,340 --> 00:07:22,240
we may or may not see that, remember, the
parser doesn't know the input. In this

84
00:07:22,240 --> 00:07:26,090
case of course, it's the very next, next
symbol and so it can see in the

85
00:07:26,090 --> 00:07:30,340
look-ahead, but you know at this point in
time the parser doesn't know for sure

86
00:07:30,340 --> 00:07:34,390
what's coming up and, you know, and, and,
if this dot were further to the left there

87
00:07:34,390 --> 00:07:38,440
might be many, many more symbols that we
had to go, before we could perform the

88
00:07:38,440 --> 00:07:42,390
reduction. So anyway, what's to the left
of that records what we've already seen.

89
00:07:42,390 --> 00:07:46,556
And what is to the right of the dot, says
that what we are waiting to see on the

90
00:07:46,556 --> 00:07:52,592
stack, before we can perform a reduction.
And now we could talk about the structure

91
00:07:52,592 --> 00:07:57,544
of the stack. So you see it's not just
arbitrary collections of symbols. In fact,

92
00:07:57,544 --> 00:08:02,747
it has this very particular structure. So
the stack is actually a stack of prefixes

93
00:08:02,747 --> 00:08:07,636
of right hand sides. So the stack always
has this organization where there's a

94
00:08:07,636 --> 00:08:12,651
bunch of prefixes, stacked up, literally
stacked up on the stack. And what's going

95
00:08:12,651 --> 00:08:17,854
to happen is that the ice prefix, if you
were to pick a prefix out of this stack of

96
00:08:17,854 --> 00:08:23,489
prefixes, While that must be the prefix of
some production. Okay. The right hand side

97
00:08:23,489 --> 00:08:29,343
of sum production And what that means is
that, that prefix, that [inaudible] prefix

98
00:08:29,343 --> 00:08:35,055
on the stack, will eventually reduce to
the left hand side of that production. So

99
00:08:35,055 --> 00:08:40,928
it will eventually reduce to, XI in this
case. And then that XI has to be Part of

100
00:08:40,928 --> 00:08:46,305
the missing suffix, of the prefix that is
below it on the stack. So if I look at the

101
00:08:46,305 --> 00:08:51,165
previous prefix the one that's right
below, prefix [inaudible] on the stack

102
00:08:51,165 --> 00:08:56,153
Then when I perform this reducti on that
XI needs to extend that prefix to be

103
00:08:56,153 --> 00:09:01,420
closer to a complete right hand side of
that particular reduction. Okay so in

104
00:09:01,420 --> 00:09:08,098
particular there's going to be some
production. That is going to; already have

105
00:09:08,098 --> 00:09:12,877
a portion of its right hand side on the
stack. So prefix of I minus one. And X I

106
00:09:12,877 --> 00:09:17,839
is going to extend that prefix, and then
there's gonna be some more stuff possibly

107
00:09:17,839 --> 00:09:23,045
that we're waiting to see, even after the
X I is put there. And recursively, all the

108
00:09:23,045 --> 00:09:28,288
prefixes above prefix K eventually have to
reduce to the missing part of the right

109
00:09:28,288 --> 00:09:33,278
hand side of prefix K, the alpha K that
goes on the right hand side. [inaudible]

110
00:09:33,278 --> 00:09:38,142
This image, you have a stack of prefixes
we're always working on the top-most

111
00:09:38,142 --> 00:09:43,701
prefix on the stack, so you will be always
working here on the right and shifting and

112
00:09:43,701 --> 00:09:48,089
reducing, but every time we perform a
reduction. That has to extend the prefix

113
00:09:48,089 --> 00:09:51,828
immediately below it on the stack. And
when these, when a bunch of prefixes have

114
00:09:51,828 --> 00:09:55,377
been removed from the stack through
reductions, then we, when we get to work

115
00:09:55,377 --> 00:10:00,975
on the prefixes that are lower in the
stack. So let's illustrate this idea with

116
00:10:00,975 --> 00:10:05,986
an example. So here is another input
string, and we're gonna use the same

117
00:10:05,986 --> 00:10:12,041
grammar. You can, you can rewind if you
want to see the grammar again. But let's

118
00:10:12,041 --> 00:10:17,756
consider this state where we have open
paren, [inaudible] star on the stack. And

119
00:10:17,756 --> 00:10:23,566
we have int, close paren remaining in the
input, 'kay? And so what items would

120
00:10:23,566 --> 00:10:29,304
record, what is the, what is the stack
structure here and how do the items record

121
00:10:29,304 --> 00:10:35,544
it? Well let's start here at the bottom,
let's actually work from the bottom up. So

122
00:10:35,544 --> 00:10:41,928
we have in start the top of our stack, so
we this is the right hand side that we're

123
00:10:41,928 --> 00:10:47,737
currently working on, and that would be a
prefix to this production T goes to int

124
00:10:47,737 --> 00:10:53,151
star T. Okay? So what this says is that
we're looking you know, we, we've seen in

125
00:10:53,151 --> 00:10:57,998
stars so far, and we're waiting to see
[inaudible]. I'm not showing the items,

126
00:10:57,998 --> 00:11:03,420
but I'm just showing the productions that
this is eventually going to use. Now, the

127
00:11:03,420 --> 00:11:08,395
one that's below it here, the, the prefix
that's below it o n the stack is right

128
00:11:08,395 --> 00:11:13,625
here in between the open paren and the
int. This one's an interesting case. It's

129
00:11:13,625 --> 00:11:19,301
actually epsilon. So there's nothing there
now on the stack. But eventually once the

130
00:11:19,301 --> 00:11:25,187
int star has reduced to T. Okay? Then that
T is going to reduce to E. And currently,

131
00:11:25,187 --> 00:11:30,489
of course, there's not a T there at all.
So we've only seen epsilon. We've seen

132
00:11:30,489 --> 00:11:35,515
none of the prefix of this production on
the stack. And then for the last

133
00:11:35,515 --> 00:11:41,437
production, the one deepest in the stack,
we're currently, we've currently seen an

134
00:11:41,437 --> 00:11:46,946
open paren. And, we're w-, and we think
we're working on this production. T goes

135
00:11:46,946 --> 00:11:52,523
to open paren, E closed paren, alright? So
when this E is produced, that will extend

136
00:11:52,523 --> 00:11:57,590
this right hand side. And now we can
record all of this with the stack of

137
00:11:57,590 --> 00:12:02,882
items, T goes to open paren dot E, E goes
to dot T, and T goes to N star dot T.

138
00:12:02,882 --> 00:12:08,313
Okay, and we just record what we said on
the previous slide, that so far, we see

139
00:12:08,313 --> 00:12:14,092
the open paren of this production. We've
seen nothing out of the right hand side of

140
00:12:14,092 --> 00:12:19,663
this production, and we've seen N star so
far of this production. And just notice

141
00:12:19,663 --> 00:12:25,372
how the left hand side of each of these
productions is going to eventually become

142
00:12:25,372 --> 00:12:31,138
part of the right hand side of the. Of the
right, part of the right hand side of the

143
00:12:31,138 --> 00:12:37,002
production we are working on just below it
in the stack. So when we've reduced this

144
00:12:37,002 --> 00:12:42,740
instar T to T that will extend this
production, when it reaches E that will

145
00:12:42,740 --> 00:12:49,006
extend this production To summarize this
video, we can say a little more precisely

146
00:12:49,006 --> 00:12:53,895
how we go about recognizing viable
prefixes. The crux of the problem is going

147
00:12:53,895 --> 00:12:58,907
to be to recognize a sequence of partial
right had sides of production. Where each

148
00:12:58,907 --> 00:13:03,736
of those partial right hand sides can
eventually reduce to part of the missing

149
00:13:03,736 --> 00:13:08,748
suffix of its predecessor Next time, in
the next video we're going to actually

150
00:13:08,748 --> 00:13:11,560
give the algorithm for implementing this
idea.