1
00:00:02,720 --> 00:00:07,471
In this video, we're going to introduce
another important concept in bottom-up

2
00:00:07,471 --> 00:00:14,483
parsing, the notion of a handle. To
review, bottom up parsing is these two

3
00:00:14,483 --> 00:00:19,272
kinds of actions: we have shift moves,
which just read one token of input and

4
00:00:19,272 --> 00:00:24,377
move the vertical bar one to the right,
And reduced moves, which replace the right

5
00:00:24,377 --> 00:00:29,103
hand side of a production [inaudible] to
the left of the vertical bar by a

6
00:00:29,103 --> 00:00:34,081
production left hand side. So in this
case, the production must have been A goes

7
00:00:34,081 --> 00:00:39,944
to XY. And also reviewing what we did in
the last video, the left string can be

8
00:00:39,944 --> 00:00:44,370
implemented by a stack, where the top of
the stack is marked by the vertical bar.

9
00:00:44,370 --> 00:00:48,908
So shift pushes the terminal on to the
stack and reduce pops zero or more symbols

10
00:00:48,908 --> 00:00:53,168
of the stack, and that's gonna be the
right hand stack of some production. And

11
00:00:53,168 --> 00:00:57,595
then it's going to push one non-terminal
on to the stack which is the left hand

12
00:00:57,595 --> 00:01:03,913
side of that same production. And the key
question in bottom of parsing and the one

13
00:01:03,913 --> 00:01:08,843
we haven't addressed at all yet is how do
we decide when to shift and when to

14
00:01:08,843 --> 00:01:13,746
reduce. So let's take a look at this
example grammar. And let's think about a

15
00:01:13,746 --> 00:01:18,534
step of a parse where we've shifted one
token onto the stack. We have Nth on the

16
00:01:18,534 --> 00:01:23,443
stack, and then we have times N plus N
still to go that we haven't seen yet. Now

17
00:01:23,443 --> 00:01:28,591
at this point we could decide to reduce by
T goes to N because we have the production

18
00:01:28,591 --> 00:01:33,380
T goes to Nth right here. And so we could
then get into this particul-, potential

19
00:01:33,380 --> 00:01:38,228
state, or this particular state, where we
have T on the stack and then the rest of

20
00:01:38,228 --> 00:01:42,957
the input that looks like that. A-, but
you can see that this would be a mistake.

21
00:01:43,137 --> 00:01:48,316
There is no production in the grammar that
begins Hence T times. There's no

22
00:01:48,316 --> 00:01:55,151
production up here that looks like T
times. And therefore if we were to, to, to

23
00:01:55,151 --> 00:01:59,846
make this move, we would get stuck. We
could continue to do reductions, to

24
00:01:59,846 --> 00:02:04,722
rummage around in the string. But we would
never be able to get back to the start

25
00:02:04,722 --> 00:02:09,839
symbol. Because there is no way to deal a
sub string that has t times something in

26
00:02:09,839 --> 00:02:16,277
it. So what that shows us is that we don't
always want to reduce just because we have

27
00:02:16,277 --> 00:02:21,074
the right-hand side of a production on top
of the stack. To repeat that, even if

28
00:02:21,074 --> 00:02:25,578
there's the right-hand side of some
production sitting right there on top of

29
00:02:25,578 --> 00:02:30,375
the stack, it might be a mistake to do a
reduction. We might want to wait and do

30
00:02:30,375 --> 00:02:35,231
our reduction someplace else. And the idea
about how we decide is that we only want

31
00:02:35,231 --> 00:02:39,852
to reduce if the result can still be
reduced to the start symbol. So let's take

32
00:02:39,852 --> 00:02:44,705
a look at a right most innervations. So,
beginning with the start symbol, we get to

33
00:02:44,705 --> 00:02:49,629
some state after, after some number of
steps where that means, just an arbitrary

34
00:02:49,629 --> 00:02:54,803
number of steps. We get to some state X is
the right most non-terminal and then the

35
00:02:54,803 --> 00:02:59,603
next step is to replace X with by the
right hand side of some production. And

36
00:02:59,603 --> 00:03:04,403
remember, again, with bottom up parsing,
the parsers are actually going in this

37
00:03:04,403 --> 00:03:09,223
direction, okay. So, this is the reduction
direction. The derivation direction, the

38
00:03:09,223 --> 00:03:14,449
production direction, Because that's the
easiest way to talk about what strings are

39
00:03:14,449 --> 00:03:18,618
derived. We wanna begin with a start
symbol. But the [inaudible], but the

40
00:03:18,618 --> 00:03:23,316
parser's actually going against the flow
of these arrows. Anyway if this is a

41
00:03:23,316 --> 00:03:28,537
rightmost derivation Then we say that
alpha beta is a handle of alpha beta

42
00:03:28,537 --> 00:03:34,445
omega. And that just means that, yes, it
would be okay in this situation to reduce

43
00:03:34,445 --> 00:03:40,426
beta to X. And we could replace beta by X,
because it's not a mistake. We can still,

44
00:03:40,426 --> 00:03:46,407
by some sequence of moves, get back to the
start symbol. You know, by, by doing more

45
00:03:46,407 --> 00:03:52,104
reductions. So handles formulize the
intuition about where it is okay to do a

46
00:03:52,104 --> 00:03:57,254
reduction. A handle is just a reduction
that also allows further reduction back to

47
00:03:57,254 --> 00:04:02,278
the start symbol And we clearly only want
to do reduction at handles. If we do a

48
00:04:02,278 --> 00:04:07,490
reduction at a place that is not a handle
even though it looks like it's the right

49
00:04:07,490 --> 00:04:12,514
hand side or maybe actually be the right
hand side of some production, that does

50
00:04:12,514 --> 00:04:17,698
not mean. That it's actually a handle, and
we might, if we could reduce there, we may

51
00:04:17,698 --> 00:04:22,823
get stuck. So all we said so far is what a
handle is. We've defined, a handle, We

52
00:04:22,823 --> 00:04:27,947
haven't said anything about how to find
the handles. And actually, how we find the

53
00:04:27,947 --> 00:04:35,138
handles is gonna consume much of the rest
of our discussion of parsing. At this

54
00:04:35,138 --> 00:04:39,576
point we know enough to state The second
important fact about bottom- up parsing.

55
00:04:39,576 --> 00:04:43,960
So in shift reduce parsing handles appear
only at the top of the stack Never in

56
00:04:43,960 --> 00:04:47,960
sight Side, and in fact this is what
justifies using a stack because that

57
00:04:47,960 --> 00:04:52,617
string to the left of our focus point we
know that all the action will take place

58
00:04:52,617 --> 00:04:56,837
immediately to the left of the focus
point. We won't have to dive down to the

59
00:04:56,837 --> 00:05:01,913
string to look at its [inaudible] and
therefore the stack will be sufficient. So

60
00:05:01,913 --> 00:05:06,604
here's an informal proof, that handles
only appear at the top of the stack. And

61
00:05:06,604 --> 00:05:11,237
this is by induction on the number of
reduce moves. So this is true initially

62
00:05:11,237 --> 00:05:15,639
because the stack is empty. And so, we
don't, you know, so the only possible

63
00:05:15,639 --> 00:05:20,214
reduction is at the top of the stack if
there's an epsilon move, to make. And

64
00:05:20,214 --> 00:05:25,078
immediately after we reduce, the right
most non terminal is going to be on top of

65
00:05:25,078 --> 00:05:29,596
the stack. So immediately after we perform
a reduction, we have a, our stack, and

66
00:05:29,596 --> 00:05:34,287
then we have a, non terminal. And then our
vertical bar, And this is the right most

67
00:05:34,287 --> 00:05:42,412
non terminal. And since this is the right
most derivation that means that the next

68
00:05:42,412 --> 00:05:47,845
handle has to be somewhere to the right.
The next handle has to be, It has to

69
00:05:47,845 --> 00:05:52,025
include something that, and you know
possibly include some of this stuff. But

70
00:05:52,025 --> 00:05:56,371
it's either right here at the current
focus point, or it's to the right, Because

71
00:05:56,371 --> 00:06:01,047
we can't be doing any reductions to the
left of the rightmost non-terminal. And so

72
00:06:01,047 --> 00:06:05,503
it's gonna require a sequence of shift
moves to reach the next handle. So once we

73
00:06:05,503 --> 00:06:09,739
have this non-terminal on top of the
stack, it is by definition the rightmost

74
00:06:09,739 --> 00:06:14,140
non-terminal, and so the next handle has
to be somewhere to the right of that.

75
00:06:15,180 --> 00:06:19,499
Therefore in shift reduce parsing handles
always appear at the top of the stack.

76
00:06:19,661 --> 00:06:24,196
Handles are never to the left of the right
most knot terminal and this is why shift

77
00:06:24,196 --> 00:06:28,839
and reduce moves are sufficient. The shift
move only moves the vertical part to the

78
00:06:28,839 --> 00:06:33,374
right because we never need to move it
left. And bottom of parsing algorithms are

79
00:06:33,374 --> 00:06:37,801
based on recognizing handles. So as we saw
in the example at the beginning of this

80
00:06:37,801 --> 00:06:42,336
video. Just because you have a right hand
side on top of the stack that doesn't mean

81
00:06:42,336 --> 00:06:46,386
that it's a handle. And so we need to be
smarter about where we perform our