In this video, we're going to talk about
our first parsing algorithm, recursive
descent parsing. So Recursive Descent is
what is called a top-down parsing
algorithm and you might suspect that there
are also bottom-up algorithms and they are
indeed such things but we will be talking
about them later but in a top-down parsing
algorithm, the parse tree is constructed
from the top so starting with the root
node and from left to right. And so the
terminals then will be seen in the order
that they appear in the token string. So
for example, if I have this token string
here, this is a hypothetical parse tree
that I could construct and the numbers
here correspond to the order in which the
nodes of this parse tree are constructed.
So we have to begin at the roots, that's
the first thing that happens and then if
T2 is a. Belongs here in the parse tree.
That would be next thing that happened but
then if we have a nonterminal of the next
position, that will be number three and
then if it has children, well the left
most one should be going left to right
will be the fourth thing to be generated.
And then let's say the two children of
number four are both terminals that would
be the next two terminals in the input and
so on. The next thing that'll happen is
the second child of number three and then
the last two terminals appearing in left
to right order. So let's consider this
grammar for integer expressions and let's
look at a particular input, a very simple
one, just open paren five, close paren.
And now, what we're going to do is we're
going to parse this using a recursive
descent strategy. I'm not gonna actually
show you any pseudocode or anything like
that. I'm just going to walk through how
this, how this input string would be
parsed. But using this grammar and the
Recursive Descent Algorithm and the basic
idea is that we begin with a nonterminal,
we begin with the root node and we always
try the rules for nonterminal in order. So
we will begin by starting with e goes to t
and if that doesn't work, we'll try e goes
to t + e. So, this is gonna be a top down
algorithm beginning at the root. We're
gonna work from left to right, we try the
productions in order and when the
productions fail, we may have to do some
back tracking in order to try alternative
productions. There are three parts.
There's the grammar that we're using.
There is the parse tree that we're
building and initially that's just the
root of the parse tree 3e and finally
there's the input that we're processing
and we'll indicate our position in the
input, how much of the input we have read
by this big fat red arrow and it always
points to the next terminal symbol to be
read, The next token to be read. So in
this case, we're starting with an open
paren. Okay? And also in the grammar, you
can see the highlighting here the brighter
red color indicates which production we're
going to try. So, we're going to begin to
build our Parse Tree by trying production
e goes to t, and what does that mean?
Well, that means we make t the child of e
and then we continue trying to build the
Parse Tree. Well, so remember we're going
left to right and top-down so now, t is an
unexpanded nonterminal, is the only
unexpanded nonterminal so we have to work
on it. And what are we going to do, well
we're going to try a production for t and
since we haven't tried any yet, we'll just
try the first one, t goes to it. So the
next step is to make nth a child with t
and that's what our parse tree looks like.
And now, we actually have something that
we can check. We can check whether we're
making progress. So observe that as long
as we're generating nonterminals, we don't
really know whether we're on the right
track or not. We have no way to check
whether the nonterminals that we're
generating are gonna produce the, the
input string. But once we generate a
terminal symbol, then we can compare that
with the next input token to see if
they're the same and in this case,
unfortunately they're not. So, the nth
that we generated here doesn't match the
open paren in the input and so clearly
this parse, th is parsing strategy or
this. Parse Tree that we're building isn't
going to work out. So, what we're going to
have to do is we're gonna have to back
track. That means, we're gonna undo one or
more of our decisions. We're gonna go back
to our last decision point and see if
there's another alternative to try. So
what's the last decision we made, well we
decide to use t goes to nth, so we can
undo that and then we could try the next
production for t. And that happens to be t
goes to n  t so expand t using that
production and now once again, we
generated a terminal in the left most
position and so now we're able to compare
that with the input and once again
unfortunately, the nth token does not
match the open paren so we have to back
track again. So we undo that decision. And
this takes us back to trying alternatives
for t. There's one more possibility, and
that's the t goes to (e). So we expand t
using that production. And now, we can
compare the token open paren. With, is
this open paren? With the open paren in
the input and they match. And so, that's
good. That means that we're, we might be
on the right track. And since they match,
anything that we do in the future is going
to have to match the different input and
so we'll advance the input pointer. So
now, where we're gonna work on next? Well,
we have to expand this non-terminal e and
we're gonna do the same thing we did
before. We're just gonna start with the
first production. So we have e goes to t
and then we have to work on t, so we're
gonna pick the first production for t and
we have t goes to int. So now, we can
compare. Is int matching int in the input?
And if it does and so we advance the input
pointer again, And now we're here and
what's left, well we progressed to this
point. We're looking at that open paren
and that also matches. So that matches the
input and now we've matched everything in
the parse tree and our input pointer is at
the end of the string and so this is
actually a successful parse of the input,
of the input string. And so that means th
at we accept and the parser terminates
successfully.