Welcome back. In this video, I'm going to
outline a general algorithm for recursive
descent parsing. Before I dive into the
details of the recursive descent parsing
algorithm, let me justify a couple of
small things that we're going to use
throughout this video. Token is going to
be a type and we're gonna be writing codes
and so token would be the type of all the
tokens. And the particular tokens that
we'll use in the example are things like
int, open-pare, close-paren, + and  and
so token is a type and these things are
instances, values of that type. And then
we're going to need a global variable
called next that points to the next token
in the input string. And if you recall
from the previous video, we used a big
arrow to point into the input to indicate
our current position. The global variable
next is going to play the same role in our
code. So let's begin. The first thing
we're going to do is define a number of
Boolean functions and one function we have
to define is one that matches the given
token in the input. So how does this work?
Well, it takes this argument, a token,
okay this is a type token again. And, and
then it just checks whether that matches
what's currently pointed to in the input
string so is t okay equal to the thing
pointed by next and notice there's a side
effect, we increment the next pointer. And
what's returned then is a Boolean. This is
either true or false. So yes the token
that we passed in matches the input or no
it doesn't. And again, just to stress
this, those at the next pointer is
incremented regardless of whether the
match succeeded or failed. Now, another
thing we need to check for a matchup is
the int production of asset. This is a
particular production of a particular
nonterminal s. And we'll denote that by a
function that returns a Boolean and is
written as s sub n. So this is, this is a
function that only checks for the success
of one production of s. And when that, I
won't write out the code for that now,
we'll see that in a minute. And then we're
gonna need another func tion that tries
all the productions of s so this one is
going to be called just s with no
subscript, no subscript and so with this
one, we'll succeed if any production of s
can match the input, alright. So we're
going to have two classes of functions for
each nonterminal. One class that where
there's one function per production and it
checks, it checks just whether that
production can match the input and then
one that combines all the productions for
that particular nonterminal together and
checks whether any of them can match the
input. Okay, that's the general plan. Now,
let's see how this works for some specific
productions, and we'll just use the same
grammar that we used in the last video.
The first production of that grammar is e
goes to t and now we wanted to do is we
want to write the functions that are
needed to decide whether this production
matches some input. And this one happens
to be simplicity itself and it's easy to
see why. So we're, first of all, we're
writing the function e1, this is the
function that deals with the first
production for e and succeeds returns true
only if this production succeeds in
matching some input. Well. How would this
production match any input? Well it can
only match some input if some production
of t matches the input and we have name
for that function, that's the function t
which tries all the different productions
for t. So e1 succeeds returns true exactly
when t succeeds returns true and that's
all there is to this first production. For
the second production, we have a little
more work to do. Now, e will succeed if t
+ e can match some of the input and how
does that work? Well first, t has to match
some of the input so some production of t
has to match a portion of the input and
after that, we have to find a + in the
input following whatever t matched and if
+ matches then, some production for e has
to match some portion of the input. And
notice the use of the short circuiting
double end here. So this is actually
important where you're exploiting the
semantics of do uble end and C and C++
which evaluates. The arguments to the
double end in left to right orders. So
first, t will execute and notice that t
has embedded within its side effects on
the pointer into the input. So it's
incrementing the next pointer and
incrementing exactly however far t makes
it. So whatever t manages to match, the
next pointer will advance that far. When
this function returns, it's left pointing
to the next terminal that t did not match
and that needs to be a plus. And the call
of term will increment the next pointer
again which is exactly where e should pick
up and whatever e can match it will
increment the next pointer just beyond
that. So, that the rest of the grammar
outside of this particular call can match
it And then notice that this particular
function is called e2 because this is the
function for the second production for e.
Well, we have one more thing to deal with
for e and that is the function e itself.
We need to write the function that will
match any alternative for e and since it's
only these two productions, it just has to
match one of these two productions And
that; this is where the backtracking is
dealt with. Now the only bit of state that
we have to worry about in the backtracking
Is this next pointer so that needs to be
restored if we ever have to undo our
decisions. And so the way we accomplish
that is we just have a local variable to
this function called save that records the
position of the next pointer before we do
anything. So before we try to match any
input, we just remember where the next
point started when this function was
called. Okay? And now to do to, to do the
alternative matching, we first try e1. And
we see if it succeeds and if it, if it
doesn't succeed, actually let's do the
succeeds case first. If this succeeds, if
this returns true then The semantics of
double or here, it means we don't evaluate
e2 so this will not be evaluated. The
second component here will not be
evaluated if e1, if e1 returns true. It'll
short circuit cuz it knows that it's going
be tru e no matter what and it'll just
stop there. And notice that whatever side
effects e1 has on the next pointer will be
retained and will remember and when we
return true, the next pointer will be left
pointing to the next piece of unconsumed
input. Now, let's consider what happens if
e1 returns false. Well if e1 returns
false, well then the only way this or can
be true is if the second component is
true. And what's the first thing we do?
The first thing we do is restore the next
pointer. Okay, before we try e2. And if
each returns true, then the whole thing
returns true and, and the e function
succeeds. If the e function fails, well
they were out of alternatives for e and
the failure is gonna be returned to the
next higher level production, in our
derivation and it will have to backtrack
and try another alternative. Now finally,
what about this particular statement next
= save here. Well, this is not strictly
needed. Notice that here we save the next
pointer in the save variable and then the
first thing, the very first thing we do if
we copy it back over the next again. This
is just for uniformity to make all the
productions look the same but since this
is the very first production, we actually
don't need this assignment statement if we
don't want to have it. So let's turn our
attention to the non-terminal t. There are
three productions. The first one is the t
goes to int. And that's a simple one to
write. We just have to match the terminal
int so the next thing in the input has to
be an integer and if it is, then t1
succeeds. T2 is slightly more complex.
That's the production int  t, t goes to
int  t so we have to match an int in the
input followed by a  followed by
something that matches any production of
t. The third production is t goes to (e).
So, what has to happen? We have to match
an open-paren first and then. Something
that matches one of the productions of e,
we call the function e there and then
finally a close-paren. And then putting
all three of these together in the
function t that tries all three
alternatives, we just have exactly the
same structure we had for e. So we saved
the current input pointer and then we try
the alternatives t1, t2 and t3 in order
and each step we restore the input point
before we try the next alternative. Start
the parser up, we have to initialize the
next pointer to point to the first token
in the input stream and we have to invoke
the function that matches anything
derivable from the start symbols. So in
this case, that's just the function e. And
recursive descent parsers are really easy
to implement by hand. In fact, people
often do implement them by hand and just
following the discipline that I showed the
previous slides. To wrap up this video,
let's work through a complete example. So
here's our grammar, and here is all the
code for the recursive descent parser for
this grammar and here is the input that
we'll be looking at and we're gonna just
mark the next pointer pointing to the
initial token of the input, all right? And
I'll also draw the Parse Tree that we're
constructing at the same time. So we'll
begin by invoking the start symbol so,
we're gonna be trying to derive something
from e. And the first thing we'll do is
we'll try the first production. So we'll
try e1, and what does e1 do? E1 is going
to try t. It's gonna try to derive
something from t. So, our possible Parse
Tree looks like this. And so we invoke t
and what is t going to do is we're going
to try all three productions for t in
order and so I was gonna call t1 and we'll
see that t1 is going to fail because it's
going try it an int so I won't put it in
the parse tree since it isn't going to
work but the int is not going to match the
open-paren. So that's going to return
false which will cause us to backtrack. It
will reset The, the input pointer, okay?
And, to the beginning of the string and
then it'll try t2. And t2 is also going to
ask, well is the input pointer = an int?
And recall that the term function here
always increments the input pointer. So in
fact, this pointer is going to move over
one, one tok en but this is going to
return false because int doesn't match
open-paren. So we'll come back here. The
input point will be restored back to the
beginning of the string and then it's
gonna try the alternative t3. Now, when we
finally get the t3, something good is
going to happen. First thing it's going to
do is going to ask is the first thing in
input an open-paren, And in fact, it is.
And so the input pointer will advance to
point to the int. And then it's going to
try to match something derivable from e so
now we have our first recursive call to e.
We're back here at e and it's going to try
e1 first and then e2. And so it calls e1
and e1 will only match something if it can
match t. Okay, so this is, we're down here
inside of e now and now we're going to
call t. And what's t going to do was going
to try all three productions for t in
order. The first one of which happens to
be the single token int and that is going
to match. It's going to call term int; t1
is calling term int so that matches the
next token in the input stream. So, we're
happy about that. The input pointer
advances again. And now, we return through
all these levels of calls. T1 succeeds
which means that t succeeds, which means
that e succeeds. Okay. And now we're back
here in the production for t3 and we're
going to ask well is the next thing that
we see in the input a close-paren? And it
did it is and so a close-paren we'll be
recorded. And now t3 will succeed which
means that t succeeds, this t succeeds and
finally we'll return to the root call e
and that returns true which means that the
Parse succeeded. That plus the fact that
we are now at the end of the input, there
is no more input to consume and we have
returned from the start symbol with true
and so we have successfully parse the
input string.