Compilers Lecture 15: Parsing (4): LL(1) Parsing, Part II: First and Follow Sets

Compilers Lecture 15: Parsing (4): LL(1) Parsing, Part II: First and Follow Sets


>>So, we still have everything
on the board from last lecture. So in today’s lecture, we
will continue our discussion of top-down parsing. So this lecture’s going to focus
on the FIRST and FOLLOW sets. You know we went through the
FIRST and FOLLOW sets for this, you know, for this
particular grammar last time. But we did not present a
complete procedure, you know, for computing the
FIRST and FOLLOW. So this is going to be the
focus of today’s lecture. But before we start, and
we’ll do another example, not this grammar. We’ll do a hypothetical example
for illustrating the computation of FIRST and FOLLOW set. But before I do this,
I wanted to make sure that everybody understands what, why we need to compute
the FOLLOW set when we are doing parsing. First of all, one thing that
I noticed may be confusing for some people is
that, you know, right now we are
writing a grammar for which the start
variable is expression. What does this mean? It means that we are parsing
a program that consists of a single expression. So right now, at this point,
we are parsing a program that consists of a
single expression. It doesn’t even have multiple
expressions it doesn’t have assignments, it doesn’t
have if else, etcetera. You know, later on, we
will be writing grammars for parsing a real
program, you know. So our start symbol is
going to be a program. And the program is going
to be a list of statements. And each statement is one
of many different kinds of statement, assignment
statement, conditional statement,
loop, etcetera, all the different
kinds of statement. And then, the assignment
statement, in particular, will have an identifier
then the equal sign or the assignment
operator, then an expression. So what we are discussing now
is half of the big grammar for an actual programming
language. So we will do this. In assignment number 2 in fact,
you know, there is a question that asks you to write
a more general grammar for more general
programming constructs. At this point, we’re only
focusing on the expression. So you know that’s why, when
we start the parsing, our, you know, root of
the tree is going to be the start variable
expression. But when we write, when we build
a parser for a real program, our, the root of the tree
is going to be a program. Okay. So the root of the tree
is going to be a program, when we write a grammar
for an actual program. Right now our root
is an expression. And top-down parsing is about
starting at the root at the top. Now, now just, this is
something to keep I mind. Now one thing that we did
last time, and I want to go through again today is why
we need, you know, this, we need to look at
that FOLLOW set. So we trying to parse
an expression like, I believe the example was X
plus A times B or maybe 2, 5 times Y. Was that the
example, last time example?>>Yeah.>>It was?>>Yeah.>>So X plus 5 times
Y. And, at some point, we got to an expression
or expression prime. So the root is expression. And at some point we
got to expression prime. And we were looking for
the right substitution for an expression prime. So is it plus term
expression time or minus term expression
prime or epsilon? And our pointer in the input was
right here pointing at the plus. So remember that parsing is all
about matching the actual string with the grammar, try
to find the derivation that will derive this
string from this grammar. Now what we have here
is expression prime, we reached that point,
expression prime. And we’re trying to figure
out what would, what, which one of these
alternative we should take. The alternative that we can
easily rule out is the minus because this thing,
think of this. By the way let’s
give them names. So this is well this is
A, this whole thing is This is A, A1, this
is A2, this is A3. So I’m trying to choose
between A1, A2, and A3. A1 starts with a plus I can
match a plus with a plus. So this looks like
definitely a good option. But we’re not sure yet
if it’s the only option. Because this backtrack tree
parsing business is all about designing the grammar such that there is only one
correct option at any point. So we shouldn’t have
multiple options. If there are multiple options
then this parsing technique doesn’t work on this
particular grammar and we should look either
for another parsing technique or we should find a way of
restructuring our grammar such that it doesn’t
have multiple options. So now this is, the A2 is an
option that we can exclude. Now the point here is A3. A3 is an option where we’re
substituting an epsilon for an expression prime. So by substituting an epsilon,
this means that we are passing or we are skipping the
matching at this point. We are not doing
any actual matching. So we are saying,
okay expression prime, we have an expression
prime here right here. This is an expression prime. And we are keeping the matching,
we are not matching the plus with anything related
to expression prime. And we are differing
the matching of the plus until the next step in the
derivation or in the parsing. So now differing the
substitution will make sense or differing the
substitution will lead to a correct derivation
only if this plus can appear after an expression prime or after an expression
prime that appears here. Now the question is does
the expression prime have is FOLLOW set? A plus. We look at
the FOLLOW set of the expression prime
after we compute it. Expression prime does
not, it has end of file and it has closed parenthesis. It does not have a
plus in it which means that differing the matching,
until the other step, we know for sure will not
lead to a correct derivation because this plus does not
belong to anything that may come after an expression prime. So skipping or differing
the matching is not a valid option here. So the only valid option, the only valid alternative is
plus term expression prime. So it, somehow, you know,
if we had a plus here in the FOLLOW set
of expression prime, then we would’ve had
two valid alternatives. Then this would’ve have
been a valid alternative because a plus could
be something that is in a FOLLOW set of
an expression prime. So if there had been
a plus here, there would have been two
valid alternatives which means that this parsing
technique fails. If there are multiple
alternatives, then, this parsing technique
that we’re doing, which is LR1 parsing
fails on this grammar. If at any point there
are multiple options, this particular parsing
technique fails. What’s the solution? Either find another
parsing technique, and we will study
another parsing technique, or try to restructure
your grammar such that you avoid
this situation where multiple options
are possible, multiple options are valid. Okay? Right? So this LR1 node is
not a parsing technique that passes all of the
grammars in the node. It only passes a subset of
the context tree grammars. Right? And, you know,
sometimes it’s possible to restructure our grammar
such that it’s parsable by LL1. And sometimes it’s not parsable. Not all grammars
are LL1 parsable. And one technique that we have
studied for converting a grammar from non LL1 parsable to LL1 parsable is the
recursion elimination. So by eliminating left
recursion, you may be able to translate, to translate, to transform a grammar
into an LL1 grammar. In this case we did the
left recursion elimination but it was not sufficient. The left recursion
elimination is not sufficient to transform any
grammar into a grammar that was parsable by LL1. Yeah.>>Is LL1 equivalent to
recursive descent parsing or is it more powerful
or less powerful?>>Okay. Yeah. Recursive descent is
a parsing technique. So that is based on LL1. So if a grammar is LL1 parsable, you can built a cursive
descent parser for it. And we will do a
cursive descent.>>And they’re equivalent?>>In one of the next lectures. Well, generally speaking,
no, strictly speaking no, because recursive
descent is, you know, any top-down parser
can be implemented as a recursive descent. Recursive descent is about, as the name implies,
is about top-down. So anything that is
top-down is, you know, can be done with
recursive descent. LL1 parsing, LL1 is
one of them, you know, the descent of languages
that are LL1 parsable or LL1 languages can be parsed
using a cursive descent parser. Yes.>>Is it common for a
language to be LL1 parsable?>>Yes. So we will
do LL1 and LR1. LR1’s more powerful than LL1. But LL1 is, you know,
is you know good enough for many languages or for
most language constructs. But we’ll see the advantages
of LR1 when we get to LR1. Now the question is, if we
have multiple correct options, then this particular
parsing technique fails. Now, what if we don’t
have any options? What does that mean? What if we don’t have
any valid options?>>Syntax error.>>Syntax error. Means that the string
that is wrong. So the string does not
belong to the language that we are trying to parse. So if zero options are
good, the string is wrong, we can say this is
a syntax error. If multiple options are good,
then LL1 parsing is not good for this particular grammar. If there is only one option
that is correct, then, LL1 parsing is good
and we can continue. Okay? Now in today’s lecture we
will be looking into, you know, the the computation of
FIRST and FOLLOW sets and how this can lead to a
condition for LL1 parsing. Well, let’s write, let’s
write the condition first. So how can we, using this
a grammar, a grammar is LL1 if what, how can we expres
what I have just said in terms of FIRST and FOLLOW set?>>If we, if their every point, if every point the next symbol
there is, there is like, there’s one alternative.>>So remember that this is a
condition that, we are looking at a condition that
checks the grammar is LL1 or not for any string. It’s not with one
particular string. So we don’t have a string. We’re given a grammar
and we are trying to come up with some conditions
for determining if the grammar is LL1 or not. Without in general,
without any specific string. Yes.>>Is one of the
conditions that all the non, all the non terminals have to be
to the right of the terminals?>>Not necessarily. Not necessarily. But if you okay so
let me simplify. So for any, for every
production and the general form of a production is going
to be X is let’s say A1 or A2 or, no it’s not. Let me not use, let me use
the more general, okay. So this is a mental notation. So when we use the
Greek alphabet, it means that this is something that may consist of
multiple symbols. It’s not necessarily one symbol. So beta 1 or beta 2 or through
beta M. So, every production in the grammar is going to have
this general form, you know, beta 1, beta 2, beta M, right. Now, if every production in the
grammar has only 1 alternative, we know for sure that we’re
going to have a problem, right. It’s definitely LL1 if
every production has, you know, only 1 alternative. But obviously, this is
not going to be the case in an interesting grammar, a grammar that only
has 1 alternative for every non-terminal is
not going to be interesting. Yeah.>>For each symbol in the
alphabet there’s a unique, there’s a unique alternative
that would work for that symbol.>>For every symbol
in the alphabet, no it’s not about
alphabet symbol. Think in terms of, you
know, this production, this general production
beta 1, beta 2, beta M. So what’s the
condition that should apply to beta 1, beta 2, beta M?>>First step should
be disjoint?>>Yes first step should
be disjoint, exactly. But, the first step
should be disjoint. But this is not sufficient for
what I was just explaining, you know, for, this is
not sufficient for this.>>Yeah the FOLLOW step would
have to be disjoint I think.>>Well not always. So when do we look
at the FOLLOW set?>>If the alternative’s epsilon.>>Yes. So if one of the alternatives
has an epsilon in it.>>Then instead of.>>Then we look at
the FOLLOW set.>>Yeah instead of
the first set.>>So basically, we are
comparing the FIRST sets, and the FIRST set
must be disjoint. But, if there is an
alternative that has an epsilon in its FIRST set, in general, so
it doesn’t have to be epsilon, if any alternative that has
an epsilon in its FIRST set, if there’s such an
alternative, then we should look at the FOLLOW set as well. Because having an epsilon in the
FIRST set means that we can skip or we can differ the matching
and we can match later. Now will matching
later work or not? That will depend
on the FOLLOW set. Okay? So we will define here, yeah I should have defined
this first, but the definition, we defined FIRST plus X
beta I as FIRST beta I if epsilon does not belong to. I’m having a hard
time distinguishing between the epsilon and
the belong to of this. So epsilon does not
belong to the first beta I. But if epsilon belongs
then it’s going to be FIRST of beta I union FOLLOW,
FOLLOW of X in fact, FOLLOW of X because this is a
substitution for X otherwise. Okay. So this is the FIRST plus. So given the FIRST plus, if for every production beta I
intersected, sorry FIRST plus, FIRST plus of X beta I
intersected with FIRST plus of X beta G equals 5 for
every ING, so for ING from 0 or from 1, 1 less than equal I
less than G less than or equal to N and I is must equal to
G. For any 2 distinct ING, the intersection of the
first plus sets should be 5. Okay? Because if it’s not 5,
there is something in common which means that there’s
multiple correct alternatives. Okay? So this is the condition. Now let’s, let’s take
another example from the FIRST and FOLLOW set and apply
it, and apply this to it. So let’s look at this example. SA equal 3, A goes to B, B goes
to BAC, B or A and C goes to AD or 1 [inaudible] sorry
or epsilon there is no Y and B goes to [inaudible]. This is the grammar. Now with this, with the current
form, this grammar is not LL1 because it has left recursion. So first step, we will
eliminate left recursion. So we only have left
recursion here, right. This is the only production
that has left recursion. So eliminating left
recursion is going to be. How do we eliminate
left recursion here? So where is our alpha
and where is on beta? Remember the rule for left
recursion elimination X is X alpha or beta goes to what X
beta X prime where X prime is.>>Alpha X prime.>>Alpha X prime or
X. Now where’s alpha? What’s alpha and
what’s beta here?>>ACB is alpha.>>Yes. ACB is alpha
and this is beta. Okay? Okay. So now, this is
alpha and this is beta. So now what’s the left
recursion elimination? Beta is or B is?>>ABA.>>AB prime where
the B prime is?>>ACB prime or epsilon.>>ACB prime or epsilon. Okay. So this is left
recursion elimination. Okay. So we will be basing
our solution on this. Let’s look at the logic
of the FIRST and FOLLOW. So in general, you know,
in generally speaking, if you have a production
like this X goes to A1, A2, A3, through AN. So generally speaking, we
are assuming that we know that the FIRST sets for A1,
A2, A3 and we are trying to compute the FIRST
sets are X given. The FIRST sets for
A1, A2, and A3. Now obviously, the first
thing that should got in FIRST of X is FIRST of A1. So the first thing that
you first put FIRST of A1 into FIRST of X.>>So this is computing
the FIRST set.>>Yeah. So this
is the FIRST set. So now this is not strictly to. So we put the FIRST of
A1 in the FIRST of X but this is not strictly to.>>If A1 contains an
epsilon, then you go to A2?>>Well, we never add the
epsilon at this point. So we put FIRST of A1 minus
epsilon at the FIRST of X. Now if it has an epsilon, if
there’s an epsilon here, we should look at FIRST of A2. What’s the logic here? The logic is if we can
substitute and epsilon for A1, if A1, this means that
we’re not matching A1 with anything in the string. This means that an X
may start with an A2 if this has an epsilon
in its FIRST step. The X may start with an A2. And, if A2 has an epsilon then
an X may start with an A3. So we have to add the
FIRST step of A3 and so on. So we have to keep checking
until we either get to one of these A’s, to an A that
doesn’t have an epsilon in it or all of them are epsilon. Now if all of them are epsilon,
or if all of them have epsilon in their FIRST set, in that
case what should we do?>>Put an epsilon
in the FIRST set.>>Put epsilon on
the FIRST set of X. So you can do this as follows. So you can just loop, basically,
for I equals, for equals 1 to N. Just put FIRST
of X union equals. So initially FIRST
of X equals 5. And for I equals 1 and FIRST of
X union equals FIRST A1 at FIRST of AI minus epsilon to FIRST
of X. Then keep doing this as long as it’s an epsilon. And you break out of the loop
when you hit a non-epsilon or you go through all of them. So if you hit a non-epsilon. If epsilon does not belong
to FIRST of, what AI or X?>>AI.>>AI, then break. So when you have non-epsilon we
break because we should stop. Now if I have an A3
with a non-epsilon, if A3 doesn’t have
an epsilon in it, this means that I only
add the FIRST of A1, A2, and A3 to the FIRST of
X. And whatever comes after A3 I don’t add its
FIRST to the FIRST of X because this A3 cannot vanish. Okay. Now after we break, we look at whether we
went through all of them. So if we went through
all of them, and that is the value
of I would be what?>>N.>>In fact N plus 1 right. Because after the loop, if
you go through all of them, the value of I would
be the first value of I that causes this
condition to be false. What causes this condition
to be false is N plus 1. So if I equals N plus 1 we
have gone through all of them. Then FIRST of X union
equals epsilon. Okay? And we have to do
this for every production. And in fact we have to
repeat the whole thing. We have to repeat it until
no more changes are possible. And why repeat it? Because the FIRST set of one
variable may be dependent on the FIRST set of
another variable. And dependencies can be
bidirectional in some cases. So we have to keep repeating
until no more changes happen. We will show this when we
go through the example. So repeat for all
productions and repeat until no more change
is possible. Repeat [inaudible] in loop. Repeat for all productions
and repeat when the outer loop is repeated for until no more
changes are possible. So the outer loop repeat
until no more changes happen. Then the inner loop
repeat for all productions. Now this is the logic
of the FIRST set. Now, what’s the logic
of the FOLLOW set? So with the FOLLOW set, if we
have this is FIRST, FOLLOW. Now with the FOLLOW set, X
will be equal to alpha at Y and then A1, A2, A3 through AN. Why alpha here? Because we don’t care about
what comes before a Y in order to compute the FOLLOW
set of a Y. And again, in order to compute the
FOLLOW set of a variable, you have to find it on
the right hand side, somewhere on the right hand
side of the production. And you look at productions
like this. Now the logic of this, the
first thing I would add to the FOLLOW of
Y would be what?>>FIRST of A1.>>FIRST of A1. So this is definitely,
this would go, the FIRST of A1 would go. But if FIRST of A1
has an epsilon in it, I should add FIRST of A2. And if FIRST of A2
has an epsilon in it, I should add FIRST of A3,
until I hit a variable that doesn’t have an
epsilon in its FIRST set. So if, for example here, if A3 doesn’t have an epsilon
then I just stop there. Then the FOLLOW of Y is going to
be the FIRST of A1 union FIRST of A2, without the epsilon
of course, union FIRST of A3. But FIRST of A4 is
not going to follow. FIRST of A4 is not going
to follow a Y. Why? Because there’s a
non-epsilon here. No epsilon means you must
have something substituted for this A3 you cannot
substitute nothing. So FIRST of this A4 is not
going to appear in FOLLOW of 1. Now what if all of
them have epsilons? What if I have a,
you know, epsilon, all of them have epsilon in
their FIRST set, epsilon, epsilon, epsilon, epsilon. If all of them have epsilons,
including A1, then in addition to adding the FIRST sets of all
of them to the FOLLOW set of Y, I also need to add the FOLLOW
set of X, the FOLLOW set of X. Why the FOLLOW set of X? Because having all of
these epsilon, at the Y, having all of these epsilons
at the Y means this may vanish and this may vanish and
all them may vanish. If all of them vanish, then Y
can be the last symbol in an X. If all of them vanish, Y could
be the last symbol in an X. And if Y can be the
last symbol in an X, we should logically add
everything that is already in the FOLLOW set of X to
the FOLLOW set of Y. Okay? So again we have a similar
loop for I equals 1 to N FOLLOW of what, of Y, right
where computed FOLLOW of Y union equals what? FOLLOW of Y union equals?>>FIRST of AI.>>FIRST of AI yes
minus epsilon. And then, if epsilon does not
belong to FIRST of AI, break. Now if I equals N plus 1,
all of them have epsilon, then FOLLOW of Y
will have in it what? Union equals what? FOLLOW of?>>Set.>>And you repeat this again. You repeat it of all
productions and you repeat it until no more changes happen. So this is just, this whole
thing is inside of two loops. One loop that goes to all
productions and one loop that goes through, that keeps
repeating the whole thing until no more changes happen. And at the very beginning,
you know, the seed for this
computation is what? What’s the seed for the
FOLLOW of computation? Where do we start? You know, initially all of the
FOLLOW sets are empty except on set in which we
add, in which we add.>>Start.>>Yeah the end of file. So at the end of file we add it to that FOLLOW set
of the start there. So we look at the
start variable, we add to its FOLLOW
set and end of file. And the logic behind
this is that, you know, this is the string that we’re
matching, you know, A, B, C, D, CC, whatever that string is, it’s going to be the
whole derivation is about matching this
whole string with and S. But after this we
have an end of file. So the logic is, after the
S which is the big variable, the top, the root of the tree,
there should be an end of file. So now let’s apply all
of this to this grammar. Now FIRST of, FIRST
of, let’s start with. What’s the easiest FIRST here? What’s the obvious one?>>FIRST of A.>>FIRST of A. FIRST of
A equals B. By the way, the FIRS of every terminal
is the terminal itself. So FIRST of A is B. And what
other FIRST are obvious? So let’s look at FIRST of, FIRST
of B. So what’s the FIRST of B? FIRST of B.>>A.>>Is an A. Now should we
look at the FIRST of B prime? No we shouldn’t look
at the FIRST of B prime because this is our
A1 and this is our A2. So our A1 is this A and
our A2 is the B prime. And our A1 doesn’t have
an epsilon in the set because our A1 is the terminal. And the FIRST of a terminal
is the terminal itself. It doesn’t have an epsilon. So because this doesn’t have
an epsilon, we stop there and we don’t go to B prime. So FIRST of B is going to be AA. FIRST of B prime is going to
be, by the way let’s erase this so that we don’t get confused. So FIRST of B prime, B starts
with an A so we put FIRST of A minus epsilon which is a
B. Now should we consider FIRST of C?>>No.>>No because FIRST of A does
not have an epsilon in it. So we don’t look at FIRST of C. But B prime has another
definition.>>Epsilon.>>Which is epsilon. So we add an epsilon. So this B comes from this
definition or this production and the epsilon comes from
the other alternative. Now FIRST of C what’s
FIRST of C? C starts with an A. So we’ll
put FIRST of A which is a B. But C also has an epsilon. Now FIRST of D? D starts with a B. So put
FIRST of B which is an A. Okay. Do we consider FIRST of C?>>No.>>No. Because FIRST of B
does not have an epsilon so we don’t consider FIRST of C. But this is FIRST
of D. Is that it?>>There’s another one.>>There’s another definition in which the D starts
with a B. Okay. And finally. FIRST of FIRST of S
is going to be what?>>FIRST of A.>>FIRST of A which is a B
and FIRST of B which is an A. And in fact, if we go for another round here
nothing will change because there are
no dependencies. We need a second round if
something up top depends on something below it. Okay. Something here
depends on something below and that something below it
gets something added to it, then we would need
a second round. We would need a second round
in the FOLLOW set we see that. So we don’t need a second
round and we are done. Now the FOLLOW sets we always
start with what the start tree. Follow of S is end of file. We add it, we add end of file. Now this may not be enough,
then we have to scan for S on the right hand side. So we scan for S on
the right hand side, we don’t find any S’s. There’s no S on the
right hand side. So that should be the end of it. We know that that’s the end. Now FOLLOW of what, let’s, yeah
let’s go in order, FOLLOW of A. So we scan for A on
the right hand side. Here is an A. So what
does this rule tell us?>>FOLLOW set S.>>Yeah. So it tells us
that there is only an A and there’s nothing after. So in fact for here, our alpha
is epsilon, our Y is the A and our A1, A2, A3
AN are absent. There aren’t any. So it’s an epsilon after. So it means that we add the
FOLLOW of S to the FOLLOW of A. Because in this case,
all the A’s are absent. So we put end of file. But this may not
be the end of it. So we look for another A.
Here is another A here. The A is followed by a C. So
we definitely need to put FIRST of C into FOLLOW of A
because C follows and A. So FIRST of C B and epsilon. We put everything
beside the epsilon. So we’ll put the B. Now should
we put what comes after C.>>Yes.>>Yeah because there is an
epsilon in the FIRST of C so we put this B. But
B is already there. Okay. Now we stop here Y.>>[Inaudible] B prime.>>No we stop here, no. That’s not the reason
why we stop.>>Because you have
to have the B.>>There is no epsilon. So B, in this example, you know,
this is, you know A is the Y, A is the Y, and this
is A1, this is A2. So B is A2, the B
is the A2 here. And this A2 does not have
an epsilon in its FIRST set because it’s a terminal. And the terminal, the FIRST set of a terminal is
the terminal itself. So we stop there. So we don’t look at
that FIRST of B prime. And we don’t add the FOLLOW B
prime to the Follow of C. right? We do not add the FOLLOW of B
prime to the FOLLOW of A, sorry, because of this B. So a cannot
be the last symbol in a B prime. Okay? Now we keep scanning for A. Here’s another
A. It’s followed by a D. So we add the FIRST set
of the D which has an A and a B. The D is already
there so we add an A. And can an A have an, sorry,
can the D have an epsilon? No it cannot, so we stop. D cannot have an epsilon. D is A and B. So we stop there. FOLLOW of B. We scan for B. Here is a
B. What does this tell.>>FOLLOW of S.>>Put FOLLOW of S in FOLLOW
of B. So, FOLLOW of S is put in FOLLOW of B. We keep scanning
for B on the right hand side. This is on the left hand side. So go look at it. Okay. So this is the only then. Okay. So this is the first B and this is the second B. These
are the only occurrences of B on the right hand side
of any production. So this is the B. Now okay,
what comes after is C. So we put the FIRST of C, and
this is B without the epsilon. So this is a B. Okay. Now should we put the,
should we put the FOLLOW of B into the FOLLOW of C?>>Yes.>>Yes because C has
an epsilon in it. So FOLLOW of D. This is where we may
need multiple iterations. So FOLLOW of D should be
put in FOLLOW of B. Why? Because C may vanish. C may vanish then B may
be the last thing in D. And we should put whatever is
in FOLLOW of D into FOLLOW of B. But FOLLOW of D is
currently empty. We haven’t put anything
in there yet. That’s why we need
a second iteration. Okay. Is there another
D, another B.>>Nope.>>No, that’s it. So we look for C, we scan for C,
no C, here’s a C, it’s followed by a B. And we stop there because this is a,
this is a terminal. Okay? And we scan for C
again, this is another C.>>FOLLOW of D.>>Yeah FOLLOW of D. So it’s
again FOLLOW of D should go in FOLLOW of C. So
FOLLOW of D feeds FOLLOW C and FOLLOW B. Now, it’s followed
by nothing so just add FOLLOW of D when we figure
out FOLLOW of D. And C, here again, same thing. Okay. So are there
any other C’s? Well there’s a C that’s followed
by a B and we already put that. Okay. Now last thing is D.
So we scan for D. No D here. There’s a D here. So this tell us put whatever is
in FOLLOW of C into FOLLOW of D. So this tells us this, put
whatever is in FOLLOW of C into FOLLOW of D.
So it says this. So we put the B. So C here is, this is a bidirectional
relation. So FOLLOW of C feeds FOLLOW of
D and FOLLOW of D feeds FOLLOW of C. Both feed each other. That’s why we need
multiple iterations until no more changes happen. So now, FOLLOW of D has this
B in it that comes from FOLLOW of C. Then we scan for D. This
is the only appearance of D. So we are done with
this iteration. Now with the second iteration.>>You’ve got FOLLOW B prime?>>Now. Sorry?>>What about FOLLOW of B prime?>>Oh we forgot the
B prime okay. Okay so FOLLOW of B prime
is going to be fed by FOLLOW of B right because it appears
at the end of a B. So FOLLOW of B PRIME gets fed by Follow
of B and we put end of file and B. This tell
us that put FOLLOW of B prime in FOLLOW of D prime. This is a useless,
so it doesn’t help. And that’s all what we need. Now the thing is FOLLOW of
B feeds follow B in part. So now we are done with
the first iteration. In the second iteration, we
will see if this, for example, B that is fed by D, if
D now has something new. These have something new, but
this something new, which is B, is already in FOLLOW of B. So
it’s not going to add anything. But, in general, you need
to check because we did D after B. We did D after
B. And, if D happened to have something new, we
had to add it to FOLLOW of B because of this dependence. Okay so this doesn’t add
anything to B. FOLLOW of C is also fed by
FOLLOW of D. But FOLLOW of D doesn’t have
anything new in it. If it had something new, we
would have had to add it. And that’s it. So in this case you’ll
have the right dependencies but the second iterations
does not add anything new.

Leave a Reply

Your email address will not be published. Required fields are marked *