>>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.