In this video, we're going to continue our
discussion of top-down parsing algorithms
with another strategy called predictive
parsing. So, predictive parsing is a lot
like recursive descent. It's still a
top-down parser. But the parser is able to
predict which production to use. And it's
never wrong. [inaudible] parser is always
able to guess correctly which production
will yield to, will lead to a successful
parse, if any production. Well, it lead to
a successful parse. And it does have some
two ways; first of all it looks at the
next few tokens, so it uses look-ahead to
try to figure out which production should
be used. So, based on what's coming up in
the input string, but also it restricts
the grammars. So this, this is only works
for a restricted form of grammars. And
there's, the advantage is that there's no
back tracking involved and so the parser
is completely deterministic if you were to
try alternatives. The predictive parsers
accept what are called the LLK grammars.
And this is a really cryptic name, and so
let me explain it. The first L stands for
left-to-right scan. So that means we're
starting at the left end of the input and
reading left to right. And in fact that's
what we always do, so all the techniques
that we looked at, look at will have an L
in the first position. The second L stands
for a leftmost derivation. So we are
constructing a leftmost derivation. That
means we're always working on the leftmost
non-terminal in the parse tree. And K
here, stands for K tokens of look ahead.
And in practice, while the theory is
developed for arbitrary 'k', in practice,
'k' is always equal to one. And so in
fact, we'll only discuss the 'k's, 'k'
equals to one, in these videos. To review,
in recursive descent parsing in each step,
there may be many choices of production to
use, and so we need to use backtracking to
undo bad choices. In an LL-1 parser, in
every step, there's only going to be one
choice of productions, of possible
production to use. And, and what does that
mean? Well, it means that if I have an
input string if I have a configuration of
the parser where I have some terminal
symbols omega and a non terminal a you
know, possibly now followed by some other
stuff there could be terminals and
nonterminals, but again a here is the
leftmost nonterminal. And, the next input.
Is a token T Well then there is exactly
one production A goes to alpha on input T.
Okay, there's only one possible production
that we can use. And any other production
is guaranteed to be incorrect. Now it can
be that, that even A goes to Alpha won't
succeed. It could be that we will be in a
situation where there's no production we
could use. But in [inaudible] parser,
there will always be at most one that we
could use. So in this case we would chose
to rewrite the string to Omega Alpha Beta.
Let's take a look at our favorite grammar,
the one we've been using for the last
couple of videos. We can see an issue here
with using this grammar for a predictive
parser. Take a look at the first two
productions for T. They both begin with
N's. And so if I tell you that the next
terminal in the input stream as we're
parsing along is an integer that doesn't
really help you in trying to distinguish
between these two productions in deciding,
deciding which one to use. So in fact with
only one token of look ahead, I can't
choose between these two productions. And
that is not the only problem actually, so
we have a problem with T but the same
problem exist with E. We can see that here
both production for E begin with the
non-terminal T, and it is really clear
what we're to make of that because a T
against a non-terminal terminal, so how we
even do the prediction but the fact that
they begin with the same thing suggest
that it's not going to be easy for us to
predict which production to use based of
only a single token of look ahead. So what
we need to do here is we need to change
the grammar. This grammar is actually
unacceptable for predictive parsing, or at
least for LL1 parsing. And we need to do
something that's called left factoring the
grammar. So the idea behind left factoring
is to eliminate the common prefixes of
multiple productions for one non terminal.
So that's a mouthful. Let's do an example.
Let's begin with the productions for E.
And we can see, again, that E, that both
productions for E begin with the same, the
same prefix. What we're going to do is
just factor out that common prefix into a
single production. So we're going to have
one production where E goes to T. And then
we're going to have multiple suffixes. So
let's introduce a new non terminal X that
will handle the rest. So here, we have E
goes to TX. So it says that everything
that E produces begins with T, and that's
consistent with these two productions. And
now we have to write another production
for X that handles the rest. And what
would that be? Well, one possibility is if
we're in this production, we need to have
a Plus E and then in this production
there's nothing. So that's easy to handle,
right. One possibility for X as it goes to
Plus E and the other possibility as it
goes to Epsilon. And now you can see the
general idea. We factor other common
prefix, we have one production that deals
with the prefix and then we write, and
then we introduce a non terminal or the
different suffixes. And then we just have,
multiple productions, one for each
possible suffix. And you can see what this
is going to do. This is effectively going
to delay the decision about which
production we're using. So instead of
having to decide immediately which
production we're going to use for E. Here,
in this grammar, we wait until we've
already seen the T, whatever is derived
from the T. And then we have to decide
whether the rest of the production is a
plus, E or the empty string. Let's do the
other, set of productions. So we have tea
goes to, and now the common prefix is int
that we want to eliminate So we're going
to have just one production that begins
with int and then we'll have a new, a
non-terminal to stand for the various
possible suffixes. And now we also have
another production that doesn't h ave
anything to do with int, and so we'll just
leave that one alone, that production just
stays here. Because it already begins with
something different we won't have any
trouble predicting between these two
possible productions, these two possible
productions. And now we have to write. The
productions for Y And again, we just take,
the suffixes of the productions that we,
left factored and write them down as
alternatives. So one is empty and the
other one is times T. So we wind up with
times T or epsilon. So here is the left
factor grammar now type out neatly. And we
use this grammar to construct a parsing
table. And let's not worry right now about
how we got this table, I'm not gonna give
the algorithm right now. But, let's just
say that we got it somehow. And, what I'm
going to explain is how we got the table.
So, One dimension of the table is the
current left most, non-terminal in the par
stream. That's on the rows. And then the
columns represent the next input token So,
the next token in the input stream. And,
then the entry is the right hand side of
the production to use. So, which
production that we should used at that
point in the pars. That's the production
that's predicted. So let's do an example.
So let's look at E INT entry. So this
entry right here. Now what this says is
that when the current nonterminal is E,
meaning the left most nonterminal on the
parks tree and the next input is in, the
thing that we see coming up in the input
is an integer. Then we should use the
production E goes to TX. So we should
expand E with the children TX. Let's do
another example. So when the current
non-terminal is Y and the current token,
the current input is plus, then we should
use the production Y goes to epsilon.
Okay, what that says is, it's a little bit
different situation than the previous one,
it says look when you see a plus in the
input and your current left most
non-terminal is y, the only way this parse
is going to succeed is if the y doesn't
produce anything. You need to get rid of
the y and move on to a nother non-terminal
whichever one is left-most after you get
rid of the y. If you want to have any hope
of parsing this particular string. And
finally, notice that a lot of the entries
are blank and those are error entries. So
let's take a look at the E star entry.
That says that if the leftmost non
terminal is E and the next input token is
a time symbol, a star. Well, then there is
no move that you can make. There is, there
is no production you can use for E that's
going to successfully parse that input.
And this is the point at which you would
raise a parsing error. In the rest of this
video, I'm gonna give the algorithm for
parsing using a parsing table. And then in
future videos, we'll explain how to
construct a parsing table. So the method
for parsing using a parsing table is
similar to recursive descent. Expect that
for the leftmost non terminal S in the
tree, we look at the next input token A.
And then as we just illustrated with the
examples, we look up in the table the
production to use at the low, at the, at
the entry S, A. And instead of using
recursive functions, to trace out the
parse tree, we're going to have a stack of
records that can, record the frontier. And
so at any point in the [inaudible] tree we
will have some non-terminals that have yet
to be expanded. Those are always at the
frontier at the current leaves of the
[inaudible] tree. And also there are some
terminals that we have yet to match
against. Those will all be recorded out of
stack. The important property of the stack
is that the left most pending terminal or
non-terminal is always at the top of the
stack. So, either the terminal we are
trying to match or the non-terminal we are
trying to expand will always be on top of
our stack. We'll reject if we reach an
error state. So if we look up one of those
empty entries in the table, we will reject
the string. And we'll accept if we reach
the end of the input, and we have an empty
stack. Meaning we have no pending
unmatched terminals or unexpanded non
terminals. So, here's the algorithm, we
initialize the stack to just the start
symbol S and a special symbol $. The $ is
not a part of the alphabet or you can
think of it we extend wherever our
alphabet is with a new symbol $. $ Marks
the mottom of the stack and you can think
of it also as marking the end of input.
So, this is just a way of recording where
the end of the input is going to be. Okay,
so the, so once we've matched, something
against S, then whatever's left, it better
be at the end of the input. That's what
the, that stack, expresses. And now we're
at a loop, so we're gonna repeat the
following moves until; we can't repeat
them anymore Until the stack is empty.
Okay? And there's two possible moves.
Let's do the terminals first. So let's say
the top of our stack is a terminal. So
here we're dividing the stack to the top
of the stack and the rest of the stack.
So, what are we going to do if the top of
the stack is a terminal? Well we're going
to try to match the input. So we're going
to say well if the top of the stack, the
terminal on top of the stack, matches the
next thing in the input, then we advance
the input. And we pop the stack. So we
have successfully matched the input
against the, the terminal. And so that
terminal is done, and we should progress
into the stack, and match the next thing
that hasn't been handled yet. And if they
don't match, if the terminal that we are
looking at doesn't match the next thing in
the input, well, that's an error. We don't
have any backtracking here. There's no way
to parse the string, so we'll raise
[inaudible]. Now the second class of moves
is deals with the non-terminal. So let's
say at the top of the stack is the
non-terminal x. So remember that the top
of the stack will be a non-terminal,
exactly when that is the left most
non-terminal. So now what we, now what we
do is we look at our pricing table under
the entry for x and the next input symbol
and that should give us the right hand
side of a production. Okay? And now what
we do is we pop X off the stack, and we
push the, the children of X i n the parse
tree under the stack. So this is the way
we expand X. So now, the leftmost
unhandled thing in the parse is going to
be Y1, because that's the first child of
X. And then all the other children of X
are next. And then whatever else is in the
stack. And again, if there's no entry,
for, the current non terminal and input in
the table, then that's an error, and the
parsing stops. So let's through an example
using our, pricing table, and. You might
want to refer back to the parsing table,
have not included it here, because there
isn't space for it. But I'll work through
it, and you can go back and look at it at
some point, and convince yourself that I'd
made the right moves. So initially, our
stack is E$. So E was our start symbol,
and $ is our end of input symbol. And our
input, we're gonna try to parse the input
[inaudible] times [inaudible], that's what
we want to parse. And then, of course, we
have our new symbol $, we'll tack that
onto the end of the input. And if all goes
well, the dollar sign on the stack will
match up against the dollar sign at the
end of the input. Again, dollar sign here
is just a way of marking. The end of the
input and expressing that we need to parse
the entire input. And so now if you look
up the E int entry, so the first terminal
in the, the next terminal in the input and
the left most [inaudible] terminal in our
parse, you would see that we're actually
supposed to take is to use the production
E goes to TX. And let me over here at the
same time construct our pars-trey. 'Kay,
so initially our stack, again, the stack
is the frontier of the parstrey.
Initially, all we have is the root of the
parstrey and that is its own frontier,
it's just one symbol, we haven't processed
it yet. And so E is on the stack, E is
unexpanded in the parstrey, and now we're
going to use the production E goes to TX.
So we'll have, T and X added as children.
What happens next? Well E is popped off
the stack. T and X are pushed on to the
stack. And now notice the frontier of the
parse tree, is TX. So t hese is usually
unprocessed leaves Either unmatched input
or unexpanded non-terminals And in fact
the stack records exactly which one is
left most. So T is at the top of the
stack. X is below it, on the stack. Okay
well we still haven't consumed any input.
And now if we look at the T, int entry it
says to use T goes to int Y. And so now we
can expand T by [inaudible] y. And now
what's going to happen is T is popped off
the stack. Int and Y are pushed onto the
stack and now notice the stack is Int Y X
from top to bottom. The frontier of the
parse tree is Int Y X. Okay? And now we
have a case where we have a terminal on
top of the stack. And so now we're gonna
try to match it against the first terminal
in the input and indeed they match. And so
what happens is [inaudible] just popped
off the stack and the terminal and sorry
the input pointer advances in the input.
Here I've recorded that by just discarding
the portion of the input that we've
processed. So now we have [inaudible] left
to go and the inch has been removed from
the stack. And so now what's on top of the
stack is Y. Y is indeed the leftmost
unprocessed thing on the frontier. And,
the table says that, for non terminal Y,
on, input times, we should use production
Y goes to times T. So let's put that in
here. And now what's going to happen. Y is
going to be popped off the stack. Times T
is going to be pushed on to the stack. And
now notice our stack is times T, X and the
frontier, the unprocessed frontier of the
parse tree is times T X. Okay. So now we
have another terminal on top of the stack,
it matches the next terminal in the input.
So we pop the terminal off the stack, we
advance the input player. Now we have T as
our left most nonterminal. Int is the next
thing in the input stream and the table
says, well in this situation, we should
use the production T goes from INT Y. What
does that mean? That means that T gets
popped of the stack. Int and Y get pushed
onto the stack. Notice that the stack is
Int, Y, X, and the end process frontier of
the parse t ree from left to right is Int,
Y, X. Once again we have a terminal on top
of the stack, we match it against the next
terminal in the input string, they match.
And now we have consumed all the input,
dollar sign is the only thing left to go
in the input. But our stack is not empty.
Okay and so at this point what does that
mean. Well, if the stack is not empty and
we are out of input then everything that's
left on the stack had better generate the
empty strings. So we'd better be using
only epsilon productions from here on and
indeed the table says that when Y is our
next non terminal and dollar sign we are
at the end of the input we should use the
production Y goes to epsilon. So Y goes to
epsilon that means Y just gets pop off the
stack. Epsilon gets pushed on the stack;
epsilon is the empty string so nothing
gets pushed on the stack. And now we're
down to X and in the situation where X is
the next non-terminal dollar sign is,
we're at the end of the input so dollar
sign is our next symbol. Then the table
also says to use production X goes to
epsilon. And then what happens? Well, X
gets popped off the stack and nothing gets
pushed on because the production was X
goes to the empty string. And now we see
we have dollar sign on top of the stack,
dollar sign in the input. And so we have
emptied the stack. We have, reached the
end of the input, and so we accept. That
is a successful parse.