GATE CS 1992 Q02 — Parsing (LL, LR)

To understand the relationship between $FOLLOW(A)$, $LFOLLOW(A)$, and $RFOLLOW(A)$, let us analyze how terminals can appear to the right of a non-terminal $A$ under different derivations.

1. $FOLLOW(A)$ vs $LFOLLOW(A)$ (May be different):

Consider the grammar:
$S \to A B$
$A \to a$
$B \to b$

• All sentential forms: $S \Rightarrow A B \Rightarrow A b \Rightarrow a b$. Here, $b$ appears immediately to the right of $A$ in the sentential form $A b$. Thus, $b \in FOLLOW(A)$.
• Left-sentential forms: In a leftmost derivation, we must expand the leftmost non-terminal first: $S \Rightarrow_{lm} A B \Rightarrow_{lm} a B \Rightarrow_{lm} a b$. The only left-sentential forms are $A B$ and $a B$. In none of these does a terminal appear immediately to the right of $A$. Thus, $b \notin LFOLLOW(A)$.

Since $FOLLOW(A) \neq LFOLLOW(A)$ in this case, Option A is correct.

2. $FOLLOW(A)$ vs $RFOLLOW(A)$ (Always the same):

In any derivation where a terminal $a$ appears immediately to the right of $A$ (i.e., $S \Rightarrow^* \alpha A a \beta$), the symbols to the right of $A$ must eventually derive terminals. In a rightmost derivation, all non-terminals to the right of $A$ are expanded to terminals before $A$ itself is expanded. Thus, any sentential form of the type $\alpha A a \beta$ can always be reached via a rightmost derivation. Therefore, $RFOLLOW(A) = FOLLOW(A)$ always holds, making Option B correct.