Tip:
Highlight text to annotate it
X
In this video, we're gonna to work through a couple of SLR parsing examples. So let's
do a very simple example. Let's consider the grammar. S goes to SA, or S goes to B.
And what does this grammar do? It produces strings of A's followed by a B. So any
number of A's followed by a single B. And notice that the grammar is left recursive,
and recall that that's not a problem for a bottom up parser. Slr parsers, LR parsers,
are perfectly happy with left recursive grammars. So let's begin by working out
what the automaton for this, grammar should be, what the parsing automaton
should be. And recall that the first step is to add a new production to the grammar.
We have to add a new start symbol. That all it does, it has one production that
goes to the old start symbol. And that's, again, just for technical reasons. Now,
the start symbol, or sorry, the start state of the NFA of the parsing automaton
is this item. S prime, our new start symbol, goes to dot S, our old start
symbol. And rather than build the NFA, and then do the subset of states construction.
Let's just go ahead and work out what items must be in the first state of the
DFA. So remember that all the epsilon moves in the, in the DF-, in the NFA, are
due to moves that happen because we don't see a non terminal on the stack. But
instead see something derived from that non terminal. So if we have a dot, Right
next to a non terminal. That means that there's an epsilon move in the NFA to all
the items that have, for all the productions, all the, all the first items,
for the productions of that non terminal. What do I mean by that? I mean that this
state, I mean epsilon production to S goes to dot SA. So this is the first item in
recognizing, this production. So the dots all the way at the left, And there would
also be an item for the other production for S, S goes to dot B. Alright, so that's
the epsilon closure in the NFA of this start item. So this'll be the first state.
These three things, these three items would be the first state of the DFA. And
now we have to consider what would happen on each of the possible transitions for
each of the symbols that we might see on the stack. So let's think about what
happens if we see a B. So if we see a B on the stack, then the only item that's going
to be in that state is S goes to B dot okay? So it'll be fine to see a B and this
would be the only item that was valid for the stack contents. Now another
possibility is that we'll see an S. So, if we see an S on the stack, what will
happen? Well, we're going to go to a state that has two items. S prime goes to S dot,
so that we've seen S on the stack, and we're ready to reduce by, by this
production, possibly. And also, S goes to S. A. And now, Clearly in this state let's
talk about his state down here. There are no more transitions possible. In all there
is only one item in the state dots all the way at the right hand side, so that state
is completely done. In this state the one over here on the right side. While one of
these items is complete, the dot's all the way at the right. But the other item still
has an A, so there could be one more transition out of this state. To the item,
S goes to SA dot, Alright? And now if we look at this, we see that for the most
part these states are in pretty good shape. So these two states this one down
here and this one over here, they only have a single item, and so there's no
possibility of a shift reduce conflict in those states. There's only one item,
there's only one thing to do. The only possibility here in both of these states
is to reduce. This state, the initial start state, has no reduce moves. So it's
only shift moves here, so there can't be a shift reduce conflict, because there are
no reduce items, No possible reduce actions. And there is to reduce, reduce
conflicts for the same reason. The only state of interest really for the point of
view for what who the grammar is SLR1 is this middle state. And here we can either
reduce by s prime goes to s dot, or we could shift and A onto the stack. And the
question is, what is in the follow of S prime? So what can follow S prime in the
grammar? And if we look back up at our grammar, we'll see that nothing can follow
S prime. S prime is the start symbol, and so, in fact, the only thing in the follow
of S prime is the, And to the input. And so what that tells us is that we'll reduce
by s prime, goes to s, if, if we're out of input. And otherwise if there is an A on
the stack, sorry, if there's an a in the input, then we'll shift it onto the stack.
And so this grammar is, SLR1. There are no shift reduce, or reduce, reduce conflicts
implied by this parsing automaton. Let's do another example, slightly more complex.
In fact, let's just extend the previous grammar. We'll have a, a production. S
goes to SAS, okay? So now we have the non terminal twice with an A in between, Or S
can go to B, just like before. And now let's work out the parsing automaton for
this grammar. And, once again, We'll need to add a dummy start symbol To the grammar
And it will go. It's only production will be to, generate the old start symbol. And
now let's begin working out what's in the, parsing automaton, for this particular
grammar. And, and just like before, we're not going to go through the effort of
constructing, the NFA. That would be a systematic way to do it. One way to it is,
is the way we sketched. Was just to construct the NFA first, and then do the
subset of states construction. But, this grammar is small enough. And simple enough
that we can work out directly what is in, what are in the states, what items are in
the states of DFA. So just like before because the dart here is immediately next
to the S, we know that we can without consuming any input at all make an epsilon
transition in the interface to the items that start the productions for S. So these
will be in the, also in the DFA state. And that's it. We can't add any other,
productions here. So S is the only non terminal. And we've added all the, first
items, initial items for S. And so that is the complete state. Okay? So just like
before, one possibility is that we'll see a B on the stack. And so that would give
us the item S goes to B dot. And that's the only item valid for that state.
Another possibility is that we'll see an S on the stack. Okay? In which case, we'll
make a transition to the state, S prime goes to S dot. And S goes to S dot AS,
alright? So we saw that same state before, in the, in the other automaton. Now we
could also see an A. Now what state would that take us to? And this is going to be a
little different. In this state, we could have the item, or will have the item, SA
dot S, and I notice that the dot is right next to S, so instead of seeing an S on
the set, we could also see something derived from S in the next position on
this stack. And so we have to throw in all the productions for S. There's only two of
them. But that means we could have the item S goes to dot SAS, and S goes to dot
P. Alright, and then out of this state, now there are a couple of different
possible transitions, we could see an S or we could see a B. Well, if we see a B,
then we wind up in this state over here. And if we see an S, Well, what's going to
happen? If we see an S, then we'll wind up in another new state. Where we have, S
goes to SAS dot. We've seen the complete right hand side of that production. Or S
goes to SA.S. Actually, that dot's in the wrong place, so let's erase that, and
let's put it in the right place. It's right here. Before the A, not after the A.
Alright and now we have to think about what happens in this state. So in this
state the only possible input is an A and if it isn't A, what's we going to have,
we're going to have S goes to SA.S and then we're gonna have to add the initial
productions for S again. And so that would just take us back to this state and like
other transition labels too we go to this state on an S and we come back to that
state, the bottom state here for the top state on an A. And I think if we hadn't
made any mistakes that, that is the complete transition system and all the
states for this DFA. Now the question is, is this , is this parsing automaton is it,
this is, is this the parsing automaton of a, a solar one grammar. And in order to
answer that question we have to look for possible reduce, reduce, and shift reduce
conflict. Well a quick scan of all the states here will show you or convince you
that there are not. Any states, where there are two possible reduce-moves. So
there can't be any reduce reuse conflicts in this, in this automaton. We can ignore
states that only have a single item or states that have no possible reduce-moves
at all. Because, those are states in which there cannot be a shift-reduce conflict
and that means we can ignore these two states. The two states over here at the
extreme left. So now we're left with these three states to think about. Alright, so
we look at this state last time. As before, the follow of S prime Is just
equal to the dollar sign. And so there's no shift reduce conflict in this state
Because on, on input A we can only shift. We can't reduce by S prime goes to S. All
right, and now we're down looking at these two states. And let's just consider this
bottom state first. Alright, so what does this state say to do? Well, this state
says, that well first of all, observe. That, the only transitions out of this
state are on B and S and there are no reduced moves in this state at all, so
there's no possibility of a shift reduce conflict in this state either. That leaves
us with just this state to think about. Now this state does have a reduced move,
the first item here is a, is a reduction, and that says that we should reduce by S
goes to S A S if whatever comes next is in the follow of S, so we're gonna need to
know what's in the follow of S. Well from S prime goes to S, we know that anything
that's in the follow of S prime is in the follow of S. So clearly dollar is in the
follow of S. And then from this part of the grammar here, we can see that A is in
the follow of S. And then from this occurrence here of S, we know that since
it occurs at the, the far right side of the production, that an ything in the
follow of the right hand side, the left hand side non terminal, is also gonna be
in follow of S. Well, in this case they're the same. It just says that the follow of
S is a subset of the follow of S which is trivially always true, and so it doesn't
add anything new. And so we wind up with just the follow of S being just two
things, dollar sign and A. But that poses a problem, because this says that if we
see an A in the input we should reduce. And this move here says that if we see an
A in the input, we should shift. And so, this state does have a shift-reduce
conflict. Alright, and so this grammar is not SLR what.