in Compiler Design edited by
5,551 views
30 votes

For a context free grammar, FOLLOW(A) is the set of terminals that can appear immediately to the right of non-terminal $A$ in some "sentential" form. We define two sets LFOLLOW(A) and RFOLLOW(A) by replacing the word "sentential" by "left sentential" and "right most sentential" respectively in the definition of FOLLOW (A).

  1. FOLLOW(A) and LFOLLOW(A) may be different.
  2. FOLLOW(A) and RFOLLOW(A) are always the same.
  3. All the three sets are identical.
  4. All the three sets are different.
in Compiler Design edited by
5.6k views

1 Answer

61 votes
 
Best answer

Ans - A,B, LFollow may be different but RFollow and Follow will be same

Consider a Grammar - 

$S \rightarrow AB$

$A \rightarrow  a$

$B \rightarrow b$


Now only string derivable is $\{ ab \}$.

Let's find Follow(A) in all cases :

  1. Follow(A) - set of terminals that can appear immediately to the right of non-terminal $A$ in some "sentential " form
    $S \rightarrow AB \rightarrow Ab  \rightarrow ab$ 

          Here, we notice only '$b$' can appear to the right of $A$.

          Follow$(A) = \{ b \}$


  1. LFollow(A) - set of terminals that can appear immediately to the right of non-terminal $A$ in some "left sentential" form
    $S \rightarrow AB \rightarrow aB  \rightarrow ab$ 

          Here, we notice no terminal  can appear to the right of $A$.

          LFollow$(A) = \{\}$


  1. RFollow(A) - set of terminals that can appear immediately to the right of non-terminal $A$ in some "right most sentential" form
    $S \rightarrow AB  \rightarrow Ab  \rightarrow ab$ 

          Here, we notice only '$b$' can appear to the right of $A$.

          RFollow$(A) = \{ b \}$

edited by

12 Comments

Solving for an instance does not prove the general case, right? Is there some way to prove for the general case?
7
If I use below grammar, I get three different sets-

S->AaAb
A->d

Follow(A)= {a,b}

LFollow(A)={b}

RFollow(A)={a}

I think except C, all remaining options are correct.

Although for a specific sentence like S->ab (any derivation gives same sentence), the given ans is right.

3
so what is the final answer ??
0
@Arjun sir can you please have look at this question and answer?
0
@dan31

You are wrong, in your example, in all 3 cases follow(A) will be {a, b} only.
2
@vishalshrm539 how lfollow is {a,b}. I m getting {b}
0

@dan31

how you are getting Lfollow(A) ={b}.how is the procedureto derive

0
Plz explain..my.Rfollow and Lfollow concept is not clear????

In above solution( Lfollow) how immediate right of A (non terminal is null ...)
1

@dan31 in your example given, Follow(A), LFollow(A), RFollow(A) should be:-

S->AaAb
A->d

Follow(A)= {a,b}

LFollow(A)={a}

RFollow(A)={a,b}

@Arjun sir, correct me if I am wrong.

 

2
If Lfollow and follow is different then why we are using follow not using L follow in  LL(1) parsing.
0
@dan31

(LMD) : dadb → daAb → AaAb → S

(RMD) : dadb → Aadb → AaAb → S

Now why LFOLLOW(A) is not equal to RFOLLOW(A) [which in turn is actually equal to {a,b}] ?
0

The first thing we need to do to solve this question is to FORGET the definition of FOLLOW we know.

Here they have defined it in a bit new way (which might be some concept that we don’t know). Here FOLLOW can be calculated only in some sentential form and not in overall grammar as we do.

Now solving this logically.

When will you get the maximum number of terminals in the FOLLOW set as per their definition?

Obviously when we will first write terminals for the non-terminals on rightmost side i.e. RMD. Because non-terminals on the leftmost side will have more elements in their FOLLOW set.

Now using similar logic, when will we have minimum number of terminals in the FOLLOW set as per their definition?

Obviously, if we convert left most non-terminals to terminals first and let the right side non-terminals be as it is, then as per their definition we’ll have the minimum number of non-terminals in the FOLLOW sets.

I hope this is what they meant to ask. Please correct me if anything is wrong here.

1
Answer:

Related questions