In this video we're finally gonna come to
the technical highlight of bottom up
parsings After all the definitions of the
previous videos now we're actually gonna
be able to give the algorithm for
recognizing viable prefixes. So let's dive
straight into the algorithm. The first
step is really just a very technical point
and it's not, not that important. But
we're going to do it anyway because it
makes things simpler Is to add a dummy
production as prime goes to S to our
grammar of interest G. So, just to set the
stage we are trying to compute the viable
prefixes of G. We're trying to come up
with a, algorithm for recognizing the
viable prefixes of G. If S is the start
symbol, we're going to make up a new start
symbol as prime, so as prime would be the
new start symbol of augmented grammar and
it's just one production for as prime as
prime goes to S. Right. So this just allow
us to know exactly where our start symbol
is used, in particular our new start
symbol as prime is only used in one place
and. Left hand side of this one
production, and that just makes things a
little bit simpler. Now, recall what we
are trying to do. We claim that the set of
viable prefixes for a given grammar is
regular and so what we're going to do is
we're going to construct a
non-deterministic final automaton that
recognizes the viable prefixes, okay? And
the states of this NFA are going to be the
items of the grammar. Now the input to the
NFA is the stack. So the NFA reads the
stack, okay? And then it, So let's
indicate this, so the NFA is gonna take
the stack as an argument, and it's either
gonna say yes, that's a viable prefix, or
no. And it's gonna read the stack from
bottom to top. So it's gonna start at the
bottom of the stack, and read towards the
top of the stack. And our goal here is to
write a non entromystic finite automaton
that recognizes the valid stacks of the
purser. So that is how we'll know. That,
our parser hasn't really counted any parse
errors. Because this automaton that we're
going to construct will always output e
ither yes, this stack is okay, meaning it
could wind up, parsing, the input. Or no,
what we've got on the stack now, doesn't
resemble any valid stack for any possible
parse of any input string for this
grammar. Okay, so let's think about, what
we, what we need the moves of this machine
to be. So let's say that we're in the
state E, arrow, alpha dot X beta. Now,
what does that say? So that says that so
far, we've seen alpha on the stack. Okay,
so remember the machine is reading the
stack from bottom to top. This records the
fact that the machine has already seen
"alpha" on the stack. So, what would be an
okay thing to see next on the stack? Well,
if this is a valid stack, if having
"alpha" on the stack at this point is
valid, well then certainly it would be
okay if the next thing on the stack was an
"X." So, we have a transition that if
we're in this state Where we are working
on this production, and we've seen alpha
on the stack. If the next thing is an X on
input X, then we can go to this state.
Where now we record the fact that we've
seen alpha X on the stack, and we're
waiting to see, the remaining portion,
beta, of that production. Okay, so this is
one kind of move that the non triamistic
phymotine can make, and again, we do, we
add this kind of a move for every item. So
for every item in the grammar, I, if it,
if the dot is not all the way at the right
end, then there will be a move like this
where the dot moves over, for whatever
symbol happens to come to the right of the
dot. The other class of transitions are
the following And these are the, the more
interesting ones. So let's say that we're
in this, configuration here. Where again,
we've seen alpha. And then the next thing
on the stack is X. And here, X is a non
terminal. [sound]. And I should have said
that in the previous case. X was either a
terminal or a non terminal. So this X here
is any grammar symbol, not just a non
terminal. But this, #four here, the, the
moves here in part four are specifically
for non terminals. Okay, so anyway, if, X
is not on the stack. Okay, let's assume
that we've seen alpha, and then the next
thing on the stack is not S. Well, is it
possible that there could be a valid
configuration of the parser where we saw
alpha but then X didn't appear next? And,
the answer is yes because as we said
before, the stack is a sequence of partial
right hand sides. So it could be that all
that's on the stack right now for this
production. Is alpha and if the next thing
on the stack is eventually going to reduce
to X. It might not be X itself, it might
be something that will eventually reduce
to X. Well, what does that mean? Well,
that means that whatever is there on the
stack has to be derived from X, it has to
be something that can be Generated by
using a sequence of X productions, 'cause
eventually it's going to reduce the X. So
for every item that looks like this, and
for every production for X now we're going
to add the following move, we're going to
say that if there's no X on the stack,
well then, we can make an epsilon move, we
can just shift to a state where we try to
recognize the right hand side plus
something derived from X. And these are
the only two kinds of moves Either the
items, eith sorry, either the grammar
symbols we're looking for are there on the
stack and we extend. >> The prefix of a
right hand side. So this rule here extends
a prefix. So as we see more of that
production on the stack or, it tries to
guess or tries to discover where the ends
of the prefixes are. So if, if alpha's as
much of the production that is on the
stack currently, well then this must be,
this x here must this, this point here
must mark the start of another right hand
side in our stack of right hand sides. So
we would expect to see something derived
from some production for x. Two more
rules. Every state in this automaton is
going to be an accepting state. That means
that if the automaton manages to
successfully consume the entire stack,
then the then the stack is viable. And
just notice that not every state is going
to have transition on every possibl e,
symbol. So there will be plenty of
possible stacks that, that are rejected
simply because the automaton gets stuck.
And finally, the start state of this
automaton is the item as prime goes to dot
S. So remember, the states of the machine
are the items of the grammar. And this is
why we added, this, dummy production, is
just so that we could conveniently name
the start state. So now, let's consider,
one of our, grammars we've been using a
lot, so this is the grammar. And now we're
going to augment it, with the extra
production as prime goes to E. And let's
take a look at the automaton for that
recognizes the viable prefixes of this
grammar. And here it is, and as you can
see, it's rather large it has a lot of
states and a lot of transitions, and I
just want to show it to you here before we
describe how we calculated it, just so you
can get an idea that these [inaudible] for
recognizing viable prefixes for grammars
are actually quite elaborate. But, now
let's break this down and see how it was
produced. So, let's begin with the start
state of this machine, so we have S prime
goes to dot E. And, remember what this
says is we want to be able to reduced to
the start symbol to the new start symbol.
And so we're reading the stack, and we're
hoping to see an E on the stack, and if we
don't then we're happy to see something
derived from E. So, what transition we
make from the state. One possibility is
that we do in fact see an eon a stack, and
in that case the dot simply moves over
saying yes we've read the first item on
the stack or the, we've read the E on the
stack and so we've seen the full right
hand side of this production. Now that
would indicate that we were probably done
with parsing. This is the state that you
would reach, have you'd read the entire
input and successfully parsed it, you
would have reduced the old start symbol
and be about to reduce to the augmented
the, the new start symbol. But if you're
not so fortunate as to see an E on the
stack, then you need to hope that you'll
see something derive fro m E. And there
are a couple of possibilities there. One
is that we could see something that would
eventually use this production, E goes to
T. And since we haven't seen any of it
yet, we put the dot all the way at the
left, indicating that we're hoping to see
a T, which could then reduce to E, and
which could then reduce to S prime. Now if
we don't see a T on the stack by itself
the other possibility is that we could be
working on this production. E goes to, T
plus E. And again, we haven't seen any of
it, so the dot Goes on the left hand side.
And then notice how we're crucially using
the power of nondeterministic automata. So
here we don't know which production is
going to, which right hand side of a
production is going to appear on the
stack. And in fact, I notice that these
productions are not even left factored, so
we don't know whether it's going to be
just a T there or a T plus E, but. We just
use the guessing power of the [inaudible]
chromatin you chose which one to, to use.
Remember the [inaudible] sepse is any
possible choice except. So you can always
guess correctly. So intuitively you can.
You will be able to pick the right one.
Now of course we could compile this down
to a deterministic machine that won't have
to make any guesses. But at this level
we're writing [inaudible] it's extremely
useful not to have to figure out which of
these two productions to use. We can just
try both and see what happens. Now let's
focus on this, state, E goes to dot T.
What are the possibilities there? Well,
one possibility is that we see a T on the
stack. And then we see in a complete right
hand side. And notice how when the dot was
all the way to the right hand side, that
is going to indicate that we're ready to
do a reduce. So we'll talk about that a
little bit later, but essentially that's
how we're going to recognize handles. When
we finally reach a state where the dot is
all the way to the right hand side that's
going to say this could be a handle that
you might want to reduce. Now if we don't
see a T on the stack , then we just see
something derived from T, and there's a
couple of possibilities, a few
possibilities there. One possibility is
that it's going to be the production T
goes to int, so since we're just starting
on this production again, we just put the
dot all the way at the left. Another
possibility we're working on T goes to
(E). And the third possibility that we're
working on T goes to int x T. And each of
the case here, notice that the dots are
all the way at the left indicating that
we're just getting started, we have not
actually seen any of the right hand side
yet. Now let's shift our focus to this
production, E goes to, dot T plus E. This
item, excuse me One possibility is that we
see an E on the see a T on the stack,
okay, in which case the dot just moves
over. And the other possibility is that we
see something derived from T, in which
case we will go to one of the states that
begins a T production. And notice here
that we already have all three of those
items in our automaton. We're just going
to it states that we went to from the item
E goes to dot T. So this, this item, E
goes to dot T plus E, could also move to
those three states. Now let's focus on
this, item here. T goes to dot,
open-paren, E closed-paren. Well, there's
only one possible move here, so this is
only a, a terminal, it's not, it's not a
non-terminal, so there's not going to be
any possibility of having something
derived from open-paren. We just have to
see the open-paren in the input. So
there's only one possible transition here,
which is that we see, the open-paren,
excuse me, on the stack, and the dot just
moves over. Now, from this state, once
again, we got is just next to a, or just
to the left of a non-terminal, so we might
see that non-terminal on the stack or we
might see something derived from that
non-terminal. Well, if we see that
non-terminal on the stack, your dot just
moves over and we get T(E.) indicating
that we've seen an both an ( and E on the
stack and we're still waiting to see the
). Well we might also see somethin g
derived from e, okay. So we add these two
transitions to the two items that begin
productions for e. [sound]. Alright, now,
let's focus on this state. T goes to open
paren E dot closed paren. Again, 'cause
it's a terminal, that the dot it's next to
is only one possible move. We have to see
that open paren if we see anything at all.
And we'll wind up with the item T goes to
open paren E, closed paren dot. And now
we've recognized the entire right hand
side of that production on the stack.
Let's take a look at this, item. So we're
here, because a terminal symbol, the, only
possibility is to read that terminal
symbol on the stack. So this would be the
next item. E goes to T plus dot E.
[sound]. Focusing on that item again
[inaudible] we could possible see an E on
the stack. Right, in which case we would
have recognized the entire writing inside
of this production, We have E goes T+E. Or
we can see something derived from here,
which case we make a transition back to
one of those two states. Now, where we got
productions left to go, or items left to
go Here, we haw T goes to.int. So, we
would have to see it next on to stack, and
that would be the full right hand side of
that production. Down here, we still have
T goes to dot [inaudible] times T. So
again, there's a terminal symbol here
[inaudible]. And so that would be the next
thing we would need to see on the stack
for this production to remain viable. And
once we've seen the [inaudible] we would
like to see the times. So we wind up in
this state and now we've got dot next to
T. So, again, one possibility is that we
see the T on the stack and then we've seen
the full right-hand side of this
production. But we might only see
something derive from T. The might, the,
the T might not be there yet. It might be
in a state where we're still waiting for
the T to appear through some sequence of
reductions. But then we would need to see
something derive from T. And in this case
we would make a transition to one of the
three states that begin the productions
for T. And that 's the full automaton.
That is, those are all the states and all
the transitions for the automaton that
recognizes the viable prefixes of this