In this video, we're gonna talk about the
main difficulty with Recursive Descent
Parsing, a problem known as Left
Recursion. Let's consider a very simple
grammar that consist of only one
production, s goes to s followed by a. So
the Recursive Descent Algorithm for this
production is the following. So, we just
have a function called s1 for the first
production of s. And it's going to succeed
if the function s succeeds and then after
that succeeds we see a terminal a in the
input stream. And then we have to write a
function for the symbol s itself and since
there's only one alternative, there's only
one production for s we don't need to
worry about backtracking or anything. So
as we'll succeed exactly when as one
succeed. There's only one possibility in
this case and now I think you can see the
problem what's going to happen. Well, when
we go to parse an input string, we're
going to call the function s which is
going to call the function s1. And then
what the function as one gonna do well,
the very first thing it's going to do is
to call the function s again. And as a
result, the function s is going to go into
an infinite loop and we're never going to
succeed in parsing any input. This will
always go into an infinite loop. So, The
reason that this, this grammar doesn't
behave very well is because it is left
recursive. And a left recursive grammar is
any grammar that has a non-terminal where
if you start with that non-terminal and
you do some non-empty sequence of
re-writes. Notice the plus there. You have
to do more than one re-write. So, if
you're actually doing a sequence of
replacements, you get back to a situation
where you have the same symbol still in
the left most position. And you can see,
this is not going to be good for parsing.
So, in the case of this grammar up here,
what happens while we get s goes to sa it
goes to saa goes to saaa. And so on and we
can always get to a situation where we
have a long string of a's and an s on the
left end of the string. And if we always
have an s on the left end of the string,
we can never manage any input because the
only way we manage input is if the first
thing we generate is a terminal symbol.
But if the first thing is always a
non-terminal, we will never make any
progress. And, it just doesn't work. I
mean, Recursive Descent does not work with
Left-Recursive Grammars. Well, this seems
like a major problem with recursive to
same parsing. It is a problem but as we'll
see shortly it's really not so major. So
let's consider a left-recursive grammar
that slightly more general form. So here
we have two productions now for s, s goes
to s followed by something alpha or it
goes to something else that doesn't
mention s and let's call that Beta. And if
you think about the language that this
generates, it's gonna join all strings
that start with a beta and then follow,
and followed by any number of alphas. And,
but it does it in a very particular way.
So if I write out some, a derivation here
where I used a few, where I used the first
production a few times. You can see what's
going on. So again, s goes to s followed
by alpha. And then s goes to s followed by
alpha, alpha and then s goes to s followed
by alpha, alpha, alpha and if I repeat
this, I get. S followed by any number of
alphas and then in one more step, I can.
Put in beta and I get beta followed by any
number of alpha. So, that's the proof that
it generates that language. That language
that begins with a beta and has some
sequence of alphas but you can see that it
does it right to left, it produces the
right under the string first and in fact
the very last thing it produces if the
first thing that appears in the input and
that's why. It doesn't work with Recursive
Descent Parsing because Recursive Descent
Parsing wants to see the first part of the
input first and then work left to right.
And this grammar is built to produce the
string right to left. And therein lies the
idea that allow us to fix the problem so
we can generate exactly the same language
producing the strings from left to right
instead of right to left and th e way we
do that is to replace left-recursion by
right-recursion. And this requires us to
add one more symbol in this case to the
grammar so instead of having s go to
something involving s on the left, we'll
have s go to beta so the first thing
notice in the very first position and then
it goes to s prime and what does s prime
do, well s prime produce what you would
expect, a sequence of alphas and it could
be the empty sequence. And if you write
out some you know? Example derivation here
we'll have s goes to beta s prime. Which
goes to now using the rules for s prime
goes to beta alpha s prime, Goes to beta
alpha. Alpha s prime goes to and after any
number of sequent, any number of rewrites
we get beta followed by sub sequence of
alphas followed by s prime. And then in
one more step we use the Epsilon Rule here
and we wind up with beta followed by some
number of alphas. And so you can see it
generates exactly the same string as the
first grammar but it does so in a
right-recursive way instead of a
left-recursive way. So in general, we may
have many productions some of which are
left-recursive and some of which are not.
And the language produced by this
particular form of grammar here is gonna
be all the strings. They are derived from
asst start with one of the betas. So one
of the things here that doesn't involve s
and it continues with zero or more
instances of the alphas. And we can do
exactly the same trick. This is just
generalizing the idea that we had before
where we only have one beta and one alpha
to many betas and many alphas and so the
general form of rewriting this
left-recursive grammar in using
right-recursion is given here. So here
each of the betas appears as an
alternative in the first position. We only
need one additional symbol s prime and
then the s prime rules is take care of
generating any sequence of the alpha i.
Now it turns out that, that isn't the most
general form of left recursion. There are
even other ways to encode left recursion
in a grammar and here's another way that's
important. So, we may have a grammar that
where nothing is obviously left-recursive.
So if you look here, you see that the s
doesn't even appear on the right hand side
here. And if you look at this production
here, a doesn't appear anywhere on the
right hand side so there's no what's
called Immediate Left-Recursion in this
grammar. But on the other hand, there is
left-recursion because s goes to a alpha
and then a can go to s beta. And so there
we have in, in two steps produce another
string with s at the left end and so this
is still a Left-Recursive Grammar. We just
delayed it by inserting other
non-terminals at the left most position
before we got back to s. So, this left
recursion can also be eliminated. In fact,
this can be eliminated automatically, it
doesn't even require human intervention.
And if you look at any of the text pretty
quickly in the Dragon Book, you'll find
algorithms were doing that. So to
summarize our discussion of Recursive
Descent Parsing, it's a simple in general
parsing strategy. You can parse any
Context-Free Grammar using Recursive
Descent, so it's very general in that
respect. It cannot work with
Left-Recursive Grammar so you must
eliminate The Left Recursion. Now in
principle, this can be automatically. You
can have Algorithms that will eliminate
the Left Recursion. In practice, people
eliminate the Left Recursion by hand and
the reason for that is that you need to
know what the grammar is that you're using
so that you can write the semantic
actions. And we haven't talked about
semantic actions yet but we will see them
shortly. And because you wanted to know
exactly what grammar, form of grammar it
has, people generally do the elimination
of left-recursion on their own. But that's
not difficult to do. And in fact,
recursion descent is a popular strategy in
practice. There are a lot to be more
complicated, but actually compilers in
fact with complicated grammars use
recursive descent because it is so
general. So, for example GCC is front-end
is a handwritten Recursive Descent Parser.