1
00:00:03,040 --> 00:00:08,280
Welcome back, In this video, we're going
to do an extended example of SLR parsing.

2
00:00:09,920 --> 00:00:14,700
To review, here is the parsing automaton
for the grammar that we've been looking at

3
00:00:14,700 --> 00:00:19,653
in the last couple of videos. And this is
just the deterministic version of the, non

4
00:00:19,653 --> 00:00:23,915
deterministic automaton we built last
time. And I've just gone through and

5
00:00:23,915 --> 00:00:28,522
numbered all of the states. So let's take
a look at what happens when we parse the

6
00:00:28,522 --> 00:00:33,241
input [inaudible] times [inaudible]. And
just to review, we've appended dollar sign

7
00:00:33,241 --> 00:00:38,070
here to the end, to indicate where the end
of the input occurs. That's just an end of

8
00:00:38,070 --> 00:00:42,677
input marker. And because this is the
beginning of the parse we haven't seen any

9
00:00:42,677 --> 00:00:47,006
input yet. And so the vertical bar is all
the way at the left hand side of the

10
00:00:47,006 --> 00:00:52,794
input. So the machine begins in state one,
and there's nothing on the stack. The

11
00:00:52,794 --> 00:00:57,856
vertical bar is all the way to the left
again, so the stack is empty. So it just

12
00:00:57,856 --> 00:01:03,175
terminates in state one. And these are the
possible items, that are valid for the

13
00:01:03,175 --> 00:01:07,698
initial state of the parser. So among
those items, we see that there are two

14
00:01:07,698 --> 00:01:12,342
that tell us that it's okay to shift an
integer in this state. And, of course, the

15
00:01:12,342 --> 00:01:16,987
first input is an integer, and so there
are no reduced moves. All the other items

16
00:01:16,987 --> 00:01:21,689
in here also have their jobs all the way
at the left side of the item, so there's

17
00:01:21,689 --> 00:01:26,217
no possible reduced move in this state.
The only thing we could possibly do is

18
00:01:26,217 --> 00:01:31,557
shift, and it's okay to shift an integer.
So to summarize, on the initial

19
00:01:31,557 --> 00:01:36,514
configuration of the parser, the DFA halts
in state one, it never even gets out of

20
00:01:36,514 --> 00:01:41,104
state one, so it starts there and ends
there without even reading any input

21
00:01:41,104 --> 00:01:45,939
because the stack is empty and the action
that, that state tells us to do is to

22
00:01:45,939 --> 00:01:50,896
shift. So that leads us in the following
state, there's an int on the stack and we

23
00:01:50,896 --> 00:01:56,586
have a times coming up on the input. So,
what happens in that situation? Well, we

24
00:01:56,586 --> 00:02:01,168
begin. The automaton is going to read the
stack. So, starting from the bottom of the

25
00:02:01,168 --> 00:02:06,242
stack, we're in the start state. And then
we read an int, there's an int on the

26
00:02:06,242 --> 00:02:11,909
stack, and we win d up in this state. And
what does this state tell us we can do?

27
00:02:11,909 --> 00:02:17,431
Well, it tells us one possibility is to
reduce by T goes to int. But again, we

28
00:02:17,431 --> 00:02:23,607
will only do that, if the following input
is in the follow of T, And times, which is

29
00:02:23,607 --> 00:02:29,458
the next input item, is not in the follow
of T. So times is not in the follow. Of T

30
00:02:29,458 --> 00:02:34,711
and so reducing here is not a possibility.
That leaves only the other item to

31
00:02:34,711 --> 00:02:40,030
consider and here we see that this item
says we can the time. So if the times the

32
00:02:40,030 --> 00:02:45,515
next thing in input, which it is, it's
okay to shift. So the DFA halts in state

33
00:02:45,515 --> 00:02:50,798
three and because there's a times in the
input the move is to shift. And that puts

34
00:02:50,798 --> 00:02:55,770
us into this configuration where we have
int and times on the stack. Times is at

35
00:02:55,770 --> 00:03:01,237
the top of the stack, int is below it and
we have an int coming up in the input. So

36
00:03:01,237 --> 00:03:06,673
what happens now, again, the DFA is going
to read the entire stack. So beginning at

37
00:03:06,673 --> 00:03:10,248
the bottom of the stack, the first thing
it sees is an int, and it moves to that

38
00:03:10,248 --> 00:03:15,156
state. And then it sees a times, and so it
moves to this state. And now, in this

39
00:03:15,156 --> 00:03:19,663
particular state, what are the
possibilities? Well, we can see, first of

40
00:03:19,663 --> 00:03:24,822
all, that there are no reduced moves.
There are no items with the dot all the

41
00:03:24,822 --> 00:03:29,655
way at the right end. So the only
possibility is a, is a shift. And we could

42
00:03:29,655 --> 00:03:34,749
shift if the upcoming input's a open
paren, which it's not. More usefully, we

43
00:03:34,749 --> 00:03:40,040
could shift if the upcoming input is an
[inaudible], which is exactly what we see.

44
00:03:40,560 --> 00:03:45,493
So, the DFA terminates in state eleven,
and the move in that state is to shift.

45
00:03:45,493 --> 00:03:50,684
And that puts us into this state, where we
have int times int on the stack, and we

46
00:03:50,684 --> 00:03:57,263
are out of input. We are at the end of the
input. So let's see what happens on the

47
00:03:57,263 --> 00:04:04,489
stack int times int. The automaton reads
it int times int and it winds up back in

48
00:04:04,489 --> 00:04:10,403
state three. Sa3 tells us that we can
shift if the, next input item is a times

49
00:04:10,403 --> 00:04:16,736
and which it is not. Or we can reduce, if
whatever the next. Is in the next input is

50
00:04:16,736 --> 00:04:22,474
in the follow of T. And in fact dollar is
in, the follow of T. So, in, the end of

51
00:04:22,474 --> 00:04:28,658
the input come after a T on the stack. And
that means it's fine to reduce by T goes

52
00:04:28,658 --> 00:04:35,073
to int. So, once we do that, once we do
the reduction T goes to int, we wind up in

53
00:04:35,073 --> 00:04:41,066
the state times T. That's our stack
contents and of course we're still at the

54
00:04:41,066 --> 00:04:45,955
end of the input. So once again the DFA is
going to read the entire stack contents

55
00:04:45,955 --> 00:04:50,517
from the bottom to the top. First it reads
the int at the bottom of the stack, then

56
00:04:50,517 --> 00:04:54,856
it sees the times. And then it finally
reads the t at the top of the stack. And

57
00:04:54,856 --> 00:04:59,120
it winds up in a new state, state four.
And the interesting thing about this

58
00:04:59,120 --> 00:05:03,768
particular step is that the DFA took a
different path through the state graph

59
00:05:03,768 --> 00:05:08,359
than it did the previous time. And that's
because the stack contents changed. We

60
00:05:08,359 --> 00:05:13,007
didn't just add stuff to the stack, and so
we didn't extend the previous path. We

61
00:05:13,007 --> 00:05:17,772
actually replaced some symbols or a symbol
on the stack with a new symbol, in this

62
00:05:17,772 --> 00:05:22,653
case, the non-terminal T and that caused
the DFA to take a different path. Now what

63
00:05:22,653 --> 00:05:27,476
does this item in state four tell us to
do? Well it says that we can reduce by T

64
00:05:27,476 --> 00:05:32,214
goes to N times T if whatever. Follows in
the input is in the follow of T. And, once

65
00:05:32,214 --> 00:05:36,822
again, dollar is in the follow of T. And
so we'll do that reduction, and now we're

66
00:05:36,822 --> 00:05:40,911
left with the static contents just
consisting of T. And, of course we're

67
00:05:40,911 --> 00:05:45,576
still at the end of the input. And let's
see what happens now. So now of course the

68
00:05:45,576 --> 00:05:50,320
contents of the stack have changed even
more radically and so the DFA just goes

69
00:05:50,320 --> 00:05:55,007
off in a completely different direction.
It reads T winds up in this state and this

70
00:05:55,007 --> 00:05:59,469
state says we can either shift a plus if
there's a plus in the input. And again,

71
00:05:59,469 --> 00:06:04,100
there's no more input. Or we can reduce by
E goes to T if dollar, if the end of the

72
00:06:04,100 --> 00:06:08,731
input is in the follow of E, Which it is.
And so the reduction will be the one that

73
00:06:08,731 --> 00:06:13,657
we do. And now we have, this stack
contents, consisting only of E. Let's see

74
00:06:13,657 --> 00:06:18,637
what happens in that situation. Now we
make a transition to this state, state

75
00:06:18,637 --> 00:06:23,684
two. And we only have one item, S prime
goes to E dot. And so this is a reduced

76
00:06:23,684 --> 00:06:28,533
move. And again, dollar is in the follow
of S prime, ' cause that is the start

77
00:06:28,533 --> 00:06:33,579
symbol. And since that is the start
symbol, we accept at this point. So once

78
00:06:33,579 --> 00:06:38,429
we get to that item as our, reduce move,
we know that the input has been

79
00:06:38,429 --> 00:06:39,740
successfully parsed.