GATE CSE 1992 | Question: 02,xiii

Question

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

• A. FOLLOW(A) and LFOLLOW(A) may be different.
• B. FOLLOW(A) and RFOLLOW(A) are always the same.
• C. All the three sets are identical.
• D. All the three sets are different.

Answer 1

Ans - A,B, $\textsf{LFOLLOW}$ may be different from $\textsf{FOLLOW}$ but $\textsf{RFOLLOW}$ and $\textsf{FOLLOW}$ will be the same

Consider the following grammar

• $S \rightarrow AB$
• $A \rightarrow  a$
• $B \rightarrow b$

---

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

Let's find $\textsf{FOLLOW}$(A) in all cases :

• $\textsf{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$.

          $\textsf{FOLLOW}$$(A) = \{ b \}$

---

• $\textsf{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$.

          $\textsf{LFOLLOW}(A) = \{\}$

---

• $\textsf{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$.

          $\textsf{RFOLLOW}(A) = \{ b \}$

---

The above example proves that $\textsf{LFOLLOW}$ may not always be the same as $\textsf{FOLLOW}$ but does not prove that $\textsf{RFOLLOW}$ and $\textsf{FOLLOW}$ will always be the same. 

In $\textsf{FOLLOW}(A),$ we add all terminals which appear on the immediate right of A in some sentential form. 

In $\textsf{RFOLLOW}(A),$ we add all terminals which appear on the immediate right of A in some right sentential form. 

Since a right sentential form is also a sentential form, it is clear that $\textsf{FOLLOW}(A) \supseteq \textsf{RFOLLOW}(A) \to (1)$ 

Now, we have to prove $\textsf{RFOLLOW}(A) \supseteq \textsf{FOLLOW}(A) $ for which we need to show that any terminal which gets added to $\textsf{FOLLOW}(A)$ must also be added to $\textsf{RFOLLOW}(A).$ Or in other words, any terminal which can appear on the immediate right of a non-terminal in some sentential form (a sentential form can be either left sentential or right sentential or neither) must also appear to the immediate-right of the same non-terminal in some $\textbf{right-sentential}$ form. 

A terminal $t$ can appear on the immediate right of a non-terminal $A$ in a sentential form

1. if $t$ is already like that in the grammar production (say $S \to \dots At\dots$
2. it $t$ produced by some reduction (say $S\to \dots AB \dots, B \to t)$

Now, since we are looking at $\textsf{immediate right}$ terminal in the sentential form, it means leftmost derivations cannot produce the terminal we need, since here $A$ will be reduced before we do reduction for the non-terminal to its immediate right. In fact the only way we can get this terminal $t$ in a sentential form is if we reduce the immediate right non-terminal of $A.$ If we do the rightmost derivation we are guaranteed to do this and rightmost derivation also ensures that all non-terminals to the right of $A$ are already derived and so we get all possible terminals to the right even in cases where the immediate right non-terminal derives empty string. Thus, $\textsf{RFOLLOW}(A) \supseteq \textsf{FOLLOW}(A) \to (2)$

From (1) and (2), we get $\textsf{FOLLOW}(A) = \textsf{RFOLLOW}(A).$ 

Comments

@charan2628 You can read about LR parsing here: https://gatecse.in/viable-prefixes-and-handle-in-lr-parsing/

---

The original answer was indeed missing the proof. Added now.

---

@gatecse Sir, thanks for the proof.