1
00:00:02,880 --> 00:00:07,344
In this video we're finally gonna come to
the technical highlight of bottom up

2
00:00:07,344 --> 00:00:12,035
parsings After all the definitions of the
previous videos now we're actually gonna

3
00:00:12,035 --> 00:00:17,716
be able to give the algorithm for
recognizing viable prefixes. So let's dive

4
00:00:17,716 --> 00:00:23,336
straight into the algorithm. The first
step is really just a very technical point

5
00:00:23,336 --> 00:00:28,755
and it's not, not that important. But
we're going to do it anyway because it

6
00:00:28,755 --> 00:00:33,367
makes things simpler Is to add a dummy
production as prime goes to S to our

7
00:00:33,367 --> 00:00:38,208
grammar of interest G. So, just to set the
stage we are trying to compute the viable

8
00:00:38,208 --> 00:00:42,581
prefixes of G. We're trying to come up
with a, algorithm for recognizing the

9
00:00:42,581 --> 00:00:47,305
viable prefixes of G. If S is the start
symbol, we're going to make up a new start

10
00:00:47,305 --> 00:00:52,146
symbol as prime, so as prime would be the
new start symbol of augmented grammar and

11
00:00:52,146 --> 00:00:56,928
it's just one production for as prime as
prime goes to S. Right. So this just allow

12
00:00:56,928 --> 00:01:01,477
us to know exactly where our start symbol
is used, in particular our new start

13
00:01:01,477 --> 00:01:05,522
symbol as prime is only used in one place
and. Left hand side of this one

14
00:01:05,522 --> 00:01:09,957
production, and that just makes things a
little bit simpler. Now, recall what we

15
00:01:09,957 --> 00:01:16,631
are trying to do. We claim that the set of
viable prefixes for a given grammar is

16
00:01:16,631 --> 00:01:21,848
regular and so what we're going to do is
we're going to construct a

17
00:01:21,848 --> 00:01:27,909
non-deterministic final automaton that
recognizes the viable prefixes, okay? And

18
00:01:27,909 --> 00:01:34,430
the states of this NFA are going to be the
items of the grammar. Now the input to the

19
00:01:34,430 --> 00:01:39,602
NFA is the stack. So the NFA reads the
stack, okay? And then it, So let's

20
00:01:39,602 --> 00:01:43,985
indicate this, so the NFA is gonna take
the stack as an argument, and it's either

21
00:01:43,985 --> 00:01:48,257
gonna say yes, that's a viable prefix, or
no. And it's gonna read the stack from

22
00:01:48,257 --> 00:01:52,749
bottom to top. So it's gonna start at the
bottom of the stack, and read towards the

23
00:01:52,749 --> 00:01:57,241
top of the stack. And our goal here is to
write a non entromystic finite automaton

24
00:01:57,241 --> 00:02:01,563
that recognizes the valid stacks of the
purser. So that is how we'll know. That,

25
00:02:01,758 --> 00:02:07,201
our parser hasn't really counted any parse
errors. Because this automaton that we're

26
00:02:07,201 --> 00:02:12,320
going to construct will always output e
ither yes, this stack is okay, meaning it

27
00:02:12,320 --> 00:02:18,152
could wind up, parsing, the input. Or no,
what we've got on the stack now, doesn't

28
00:02:18,152 --> 00:02:23,141
resemble any valid stack for any possible
parse of any input string for this

29
00:02:23,141 --> 00:02:30,318
grammar. Okay, so let's think about, what
we, what we need the moves of this machine

30
00:02:30,318 --> 00:02:36,198
to be. So let's say that we're in the
state E, arrow, alpha dot X beta. Now,

31
00:02:36,198 --> 00:02:43,632
what does that say? So that says that so
far, we've seen alpha on the stack. Okay,

32
00:02:43,632 --> 00:02:48,055
so remember the machine is reading the
stack from bottom to top. This records the

33
00:02:48,055 --> 00:02:52,314
fact that the machine has already seen
"alpha" on the stack. So, what would be an

34
00:02:52,314 --> 00:02:56,463
okay thing to see next on the stack? Well,
if this is a valid stack, if having

35
00:02:56,463 --> 00:03:00,503
"alpha" on the stack at this point is
valid, well then certainly it would be

36
00:03:00,503 --> 00:03:04,708
okay if the next thing on the stack was an
"X." So, we have a transition that if

37
00:03:04,708 --> 00:03:09,188
we're in this state Where we are working
on this production, and we've seen alpha

38
00:03:09,188 --> 00:03:13,743
on the stack. If the next thing is an X on
input X, then we can go to this state.

39
00:03:13,743 --> 00:03:17,964
Where now we record the fact that we've
seen alpha X on the stack, and we're

40
00:03:17,964 --> 00:03:22,497
waiting to see, the remaining portion,
beta, of that production. Okay, so this is

41
00:03:22,497 --> 00:03:27,506
one kind of move that the non triamistic
phymotine can make, and again, we do, we

42
00:03:27,506 --> 00:03:32,393
add this kind of a move for every item. So
for every item in the grammar, I, if it,

43
00:03:32,393 --> 00:03:37,464
if the dot is not all the way at the right
end, then there will be a move like this

44
00:03:37,464 --> 00:03:42,595
where the dot moves over, for whatever
symbol happens to come to the right of the

45
00:03:42,595 --> 00:03:49,360
dot. The other class of transitions are
the following And these are the, the more

46
00:03:49,360 --> 00:03:55,913
interesting ones. So let's say that we're
in this, configuration here. Where again,

47
00:03:55,913 --> 00:04:01,934
we've seen alpha. And then the next thing
on the stack is X. And here, X is a non

48
00:04:01,934 --> 00:04:08,167
terminal. [sound]. And I should have said
that in the previous case. X was either a

49
00:04:08,167 --> 00:04:13,205
terminal or a non terminal. So this X here
is any grammar symbol, not just a non

50
00:04:13,205 --> 00:04:18,306
terminal. But this, #four here, the, the
moves here in part four are specifically

51
00:04:18,306 --> 00:04:23,343
for non terminals. Okay, so anyway, if, X
is not on the stack. Okay, let's assume

52
00:04:23,343 --> 00:04:28,368
that we've seen alpha, and then the next
thing on the stack is not S. Well, is it

53
00:04:28,368 --> 00:04:33,249
possible that there could be a valid
configuration of the parser where we saw

54
00:04:33,249 --> 00:04:38,067
alpha but then X didn't appear next? And,
the answer is yes because as we said

55
00:04:38,067 --> 00:04:43,261
before, the stack is a sequence of partial
right hand sides. So it could be that all

56
00:04:43,261 --> 00:04:48,283
that's on the stack right now for this
production. Is alpha and if the next thing

57
00:04:48,283 --> 00:04:53,292
on the stack is eventually going to reduce
to X. It might not be X itself, it might

58
00:04:53,292 --> 00:04:57,934
be something that will eventually reduce
to X. Well, what does that mean? Well,

59
00:04:57,934 --> 00:05:02,942
that means that whatever is there on the
stack has to be derived from X, it has to

60
00:05:02,942 --> 00:05:07,453
be something that can be Generated by
using a sequence of X productions, 'cause

61
00:05:07,453 --> 00:05:12,012
eventually it's going to reduce the X. So
for every item that looks like this, and

62
00:05:12,012 --> 00:05:16,741
for every production for X now we're going
to add the following move, we're going to

63
00:05:16,741 --> 00:05:21,188
say that if there's no X on the stack,
well then, we can make an epsilon move, we

64
00:05:21,188 --> 00:05:25,522
can just shift to a state where we try to
recognize the right hand side plus

65
00:05:25,522 --> 00:05:29,939
something derived from X. And these are
the only two kinds of moves Either the

66
00:05:30,109 --> 00:05:34,594
items, eith sorry, either the grammar
symbols we're looking for are there on the

67
00:05:34,594 --> 00:05:39,388
stack and we extend. >> The prefix of a
right hand side. So this rule here extends

68
00:05:39,388 --> 00:05:43,617
a prefix. So as we see more of that
production on the stack or, it tries to

69
00:05:43,617 --> 00:05:48,476
guess or tries to discover where the ends
of the prefixes are. So if, if alpha's as

70
00:05:48,476 --> 00:05:52,877
much of the production that is on the
stack currently, well then this must be,

71
00:05:52,877 --> 00:05:57,449
this x here must this, this point here
must mark the start of another right hand

72
00:05:57,449 --> 00:06:02,136
side in our stack of right hand sides. So
we would expect to see something derived

73
00:06:02,136 --> 00:06:07,940
from some production for x. Two more
rules. Every state in this automaton is

74
00:06:07,940 --> 00:06:13,277
going to be an accepting state. That means
that if the automaton manages to

75
00:06:13,277 --> 00:06:18,679
successfully consume the entire stack,
then the then the stack is viable. And

76
00:06:18,679 --> 00:06:23,884
just notice that not every state is going
to have transition on every possibl e,

77
00:06:23,884 --> 00:06:28,694
symbol. So there will be plenty of
possible stacks that, that are rejected

78
00:06:28,694 --> 00:06:33,577
simply because the automaton gets stuck.
And finally, the start state of this

79
00:06:33,577 --> 00:06:38,758
automaton is the item as prime goes to dot
S. So remember, the states of the machine

80
00:06:38,758 --> 00:06:44,064
are the items of the grammar. And this is
why we added, this, dummy production, is

81
00:06:44,064 --> 00:06:50,005
just so that we could conveniently name
the start state. So now, let's consider,

82
00:06:50,211 --> 00:06:55,892
one of our, grammars we've been using a
lot, so this is the grammar. And now we're

83
00:06:55,892 --> 00:07:01,231
going to augment it, with the extra
production as prime goes to E. And let's

84
00:07:01,231 --> 00:07:06,502
take a look at the automaton for that
recognizes the viable prefixes of this

85
00:07:06,502 --> 00:07:11,750
grammar. And here it is, and as you can
see, it's rather large it has a lot of

86
00:07:11,750 --> 00:07:17,112
states and a lot of transitions, and I
just want to show it to you here before we

87
00:07:17,112 --> 00:07:23,136
describe how we calculated it, just so you
can get an idea that these [inaudible] for

88
00:07:23,136 --> 00:07:28,300
recognizing viable prefixes for grammars
are actually quite elaborate. But, now

89
00:07:28,300 --> 00:07:33,352
let's break this down and see how it was
produced. So, let's begin with the start

90
00:07:33,352 --> 00:07:37,882
state of this machine, so we have S prime
goes to dot E. And, remember what this

91
00:07:37,882 --> 00:07:42,645
says is we want to be able to reduced to
the start symbol to the new start symbol.

92
00:07:42,645 --> 00:07:47,466
And so we're reading the stack, and we're
hoping to see an E on the stack, and if we

93
00:07:47,466 --> 00:07:51,938
don't then we're happy to see something
derived from E. So, what transition we

94
00:07:51,938 --> 00:07:56,755
make from the state. One possibility is
that we do in fact see an eon a stack, and

95
00:07:56,755 --> 00:08:01,669
in that case the dot simply moves over
saying yes we've read the first item on

96
00:08:01,669 --> 00:08:06,463
the stack or the, we've read the E on the
stack and so we've seen the full right

97
00:08:06,463 --> 00:08:11,257
hand side of this production. Now that
would indicate that we were probably done

98
00:08:11,257 --> 00:08:15,991
with parsing. This is the state that you
would reach, have you'd read the entire

99
00:08:15,991 --> 00:08:20,605
input and successfully parsed it, you
would have reduced the old start symbol

100
00:08:20,605 --> 00:08:25,898
and be about to reduce to the augmented
the, the new start symbol. But if you're

101
00:08:25,898 --> 00:08:30,288
not so fortunate as to see an E on the
stack, then you need to hope that you'll

102
00:08:30,288 --> 00:08:34,623
see something derive fro m E. And there
are a couple of possibilities there. One

103
00:08:34,623 --> 00:08:39,236
is that we could see something that would
eventually use this production, E goes to

104
00:08:39,236 --> 00:08:43,459
T. And since we haven't seen any of it
yet, we put the dot all the way at the

105
00:08:43,459 --> 00:08:47,794
left, indicating that we're hoping to see
a T, which could then reduce to E, and

106
00:08:47,794 --> 00:08:52,493
which could then reduce to S prime. Now if
we don't see a T on the stack by itself

107
00:08:52,493 --> 00:08:57,415
the other possibility is that we could be
working on this production. E goes to, T

108
00:08:57,415 --> 00:09:02,310
plus E. And again, we haven't seen any of
it, so the dot Goes on the left hand side.

109
00:09:02,310 --> 00:09:07,695
And then notice how we're crucially using
the power of nondeterministic automata. So

110
00:09:07,695 --> 00:09:12,503
here we don't know which production is
going to, which right hand side of a

111
00:09:12,503 --> 00:09:17,311
production is going to appear on the
stack. And in fact, I notice that these

112
00:09:17,311 --> 00:09:22,504
productions are not even left factored, so
we don't know whether it's going to be

113
00:09:22,504 --> 00:09:27,710
just a T there or a T plus E, but. We just
use the guessing power of the [inaudible]

114
00:09:27,710 --> 00:09:32,717
chromatin you chose which one to, to use.
Remember the [inaudible] sepse is any

115
00:09:32,717 --> 00:09:37,847
possible choice except. So you can always
guess correctly. So intuitively you can.

116
00:09:37,847 --> 00:09:42,730
You will be able to pick the right one.
Now of course we could compile this down

117
00:09:42,730 --> 00:09:47,888
to a deterministic machine that won't have
to make any guesses. But at this level

118
00:09:47,888 --> 00:09:52,864
we're writing [inaudible] it's extremely
useful not to have to figure out which of

119
00:09:52,864 --> 00:09:58,202
these two productions to use. We can just
try both and see what happens. Now let's

120
00:09:58,202 --> 00:10:02,684
focus on this, state, E goes to dot T.
What are the possibilities there? Well,

121
00:10:02,684 --> 00:10:07,574
one possibility is that we see a T on the
stack. And then we see in a complete right

122
00:10:07,574 --> 00:10:12,522
hand side. And notice how when the dot was
all the way to the right hand side, that

123
00:10:12,522 --> 00:10:17,179
is going to indicate that we're ready to
do a reduce. So we'll talk about that a

124
00:10:17,179 --> 00:10:21,953
little bit later, but essentially that's
how we're going to recognize handles. When

125
00:10:21,953 --> 00:10:26,843
we finally reach a state where the dot is
all the way to the right hand side that's

126
00:10:26,843 --> 00:10:32,034
going to say this could be a handle that
you might want to reduce. Now if we don't

127
00:10:32,034 --> 00:10:36,338
see a T on the stack , then we just see
something derived from T, and there's a

128
00:10:36,338 --> 00:10:40,194
couple of possibilities, a few
possibilities there. One possibility is

129
00:10:40,194 --> 00:10:44,666
that it's going to be the production T
goes to int, so since we're just starting

130
00:10:44,666 --> 00:10:48,969
on this production again, we just put the
dot all the way at the left. Another

131
00:10:48,969 --> 00:10:53,217
possibility we're working on T goes to
(E). And the third possibility that we're

132
00:10:53,217 --> 00:10:57,689
working on T goes to int x T. And each of
the case here, notice that the dots are

133
00:10:57,689 --> 00:11:02,104
all the way at the left indicating that
we're just getting started, we have not

134
00:11:02,104 --> 00:11:08,499
actually seen any of the right hand side
yet. Now let's shift our focus to this

135
00:11:08,499 --> 00:11:15,295
production, E goes to, dot T plus E. This
item, excuse me One possibility is that we

136
00:11:15,295 --> 00:11:20,066
see an E on the see a T on the stack,
okay, in which case the dot just moves

137
00:11:20,066 --> 00:11:24,960
over. And the other possibility is that we
see something derived from T, in which

138
00:11:24,960 --> 00:11:29,854
case we will go to one of the states that
begins a T production. And notice here

139
00:11:29,854 --> 00:11:34,747
that we already have all three of those
items in our automaton. We're just going

140
00:11:34,747 --> 00:11:40,130
to it states that we went to from the item
E goes to dot T. So this, this item, E

141
00:11:40,130 --> 00:11:45,476
goes to dot T plus E, could also move to
those three states. Now let's focus on

142
00:11:45,476 --> 00:11:49,572
this, item here. T goes to dot,
open-paren, E closed-paren. Well, there's

143
00:11:49,572 --> 00:11:54,015
only one possible move here, so this is
only a, a terminal, it's not, it's not a

144
00:11:54,015 --> 00:11:58,400
non-terminal, so there's not going to be
any possibility of having something

145
00:11:58,400 --> 00:12:02,727
derived from open-paren. We just have to
see the open-paren in the input. So

146
00:12:02,727 --> 00:12:07,227
there's only one possible transition here,
which is that we see, the open-paren,

147
00:12:07,227 --> 00:12:11,733
excuse me, on the stack, and the dot just
moves over. Now, from this state, once

148
00:12:11,733 --> 00:12:16,797
again, we got is just next to a, or just
to the left of a non-terminal, so we might

149
00:12:16,797 --> 00:12:21,737
see that non-terminal on the stack or we
might see something derived from that

150
00:12:21,737 --> 00:12:26,301
non-terminal. Well, if we see that
non-terminal on the stack, your dot just

151
00:12:26,301 --> 00:12:31,053
moves over and we get T(E.) indicating
that we've seen an both an ( and E on the

152
00:12:31,053 --> 00:12:36,194
stack and we're still waiting to see the
). Well we might also see somethin g

153
00:12:36,194 --> 00:12:42,518
derived from e, okay. So we add these two
transitions to the two items that begin

154
00:12:42,518 --> 00:12:48,370
productions for e. [sound]. Alright, now,
let's focus on this state. T goes to open

155
00:12:48,370 --> 00:12:53,135
paren E dot closed paren. Again, 'cause
it's a terminal, that the dot it's next to

156
00:12:53,135 --> 00:12:57,959
is only one possible move. We have to see
that open paren if we see anything at all.

157
00:12:57,959 --> 00:13:02,609
And we'll wind up with the item T goes to
open paren E, closed paren dot. And now

158
00:13:02,609 --> 00:13:07,026
we've recognized the entire right hand
side of that production on the stack.

159
00:13:07,026 --> 00:13:12,198
Let's take a look at this, item. So we're
here, because a terminal symbol, the, only

160
00:13:12,198 --> 00:13:16,732
possibility is to read that terminal
symbol on the stack. So this would be the

161
00:13:16,732 --> 00:13:21,970
next item. E goes to T plus dot E.
[sound]. Focusing on that item again

162
00:13:21,970 --> 00:13:27,802
[inaudible] we could possible see an E on
the stack. Right, in which case we would

163
00:13:27,802 --> 00:13:33,144
have recognized the entire writing inside
of this production, We have E goes T+E. Or

164
00:13:33,144 --> 00:13:38,354
we can see something derived from here,
which case we make a transition back to

165
00:13:38,354 --> 00:13:43,696
one of those two states. Now, where we got
productions left to go, or items left to

166
00:13:43,696 --> 00:13:48,774
go Here, we haw T goes to.int. So, we
would have to see it next on to stack, and

167
00:13:48,774 --> 00:13:54,302
that would be the full right hand side of
that production. Down here, we still have

168
00:13:54,302 --> 00:13:59,550
T goes to dot [inaudible] times T. So
again, there's a terminal symbol here

169
00:13:59,763 --> 00:14:05,578
[inaudible]. And so that would be the next
thing we would need to see on the stack

170
00:14:05,578 --> 00:14:11,819
for this production to remain viable. And
once we've seen the [inaudible] we would

171
00:14:11,819 --> 00:14:16,789
like to see the times. So we wind up in
this state and now we've got dot next to

172
00:14:16,789 --> 00:14:21,551
T. So, again, one possibility is that we
see the T on the stack and then we've seen

173
00:14:21,551 --> 00:14:25,431
the full right-hand side of this
production. But we might only see

174
00:14:25,431 --> 00:14:30,428
something derive from T. The might, the,
the T might not be there yet. It might be

175
00:14:30,428 --> 00:14:35,248
in a state where we're still waiting for
the T to appear through some sequence of

176
00:14:35,248 --> 00:14:40,069
reductions. But then we would need to see
something derive from T. And in this case

177
00:14:40,069 --> 00:14:45,007
we would make a transition to one of the
three states that begin the productions

178
00:14:45,007 --> 00:14:50,289
for T. And that 's the full automaton.
That is, those are all the states and all

179
00:14:50,289 --> 00:14:55,704
the transitions for the automaton that
recognizes the viable prefixes of this