GATE CS 2024 Set 1 Q.38: Parsing and Syntax Analysis (LL and LR)

Consider the following grammar $G$ , with $S$ as the start symbol. The grammar $G$ has three incomplete productions denoted by (1), (2), and (3).

\begin{aligned} S &\rightarrow daT \mid (1) \\ T &\rightarrow aS \mid bT \mid (2) \\ R &\rightarrow (3) \mid \epsilon \end{aligned}

The set of terminals is $\{a, b, c, d, f\}$ . The FIRST and FOLLOW sets of the different non-terminals are as follows.

\text{FIRST}(S) = \{c, d, f\},\quad \text{FIRST}(T) = \{a, b, \epsilon\},\quad \text{FIRST}(R) = \{c, \epsilon\}

\text{FOLLOW}(S) = \text{FOLLOW}(T) = \{c, f, \$\},\quad \text{FOLLOW}(R) = \{f\}

Which one of the following options CORRECTLY fills in the incomplete productions?

(1) $S \rightarrow Rf$ (2) $T \rightarrow \epsilon$ (3) $R \rightarrow cTR$

(1) $S \rightarrow fR$ (2) $T \rightarrow \epsilon$ (3) $R \rightarrow cTR$

(1) $S \rightarrow fR$ (2) $T \rightarrow cT$ (3) $R \rightarrow cR$

(1) $S \rightarrow Rf$ (2) $T \rightarrow cT$ (3) $R \rightarrow cR$

Official answer and solution

Solution

Use the given FIRST and FOLLOW sets to deduce each missing production one by one.

Deduce (2) from $\text{FIRST}(T) = \{a, b, \epsilon\}$ :
Since $\epsilon \in \text{FIRST}(T)$ , $T$ must have the production $T \rightarrow \epsilon$ . This eliminates options (C) and (D).
Deduce (1) from $\text{FIRST}(S) = \{c, d, f\}$ and $\text{FOLLOW}(R) = \{f\}$ :
The production $S \rightarrow daT$ only contributes $d$ to $\text{FIRST}(S)$ , so production (1) must contribute both $c$ and $f$ to $\text{FIRST}(S)$ . With $S \rightarrow Rf$ , since $\text{FIRST}(R) = \{c, \epsilon\}$ , we get: $\text{FIRST}(Rf) = (\text{FIRST}(R) \setminus \{\epsilon\}) \cup \text{FIRST}(f) = \{c, f\}$ which yields $\text{FIRST}(S) = \{c, d, f\}$ and also places $f \in \text{FOLLOW}(R)$ (whereas $S \rightarrow fR$ would only give $\text{FIRST}(S) = \{d, f\}$ and would place $\$ \in \text{FOLLOW}(R)$ ).
Verify (3) $R \rightarrow cTR$ :
This gives $\text{FIRST}(R) = \{c, \epsilon\}$ and adds $(\text{FIRST}(R) \setminus \{\epsilon\}) \cup \text{FOLLOW}(R) = \{c, f\}$ to $\text{FOLLOW}(T)$ , matching $\text{FOLLOW}(T) = \text{FOLLOW}(S) = \{c, f, \$\}$ .

Thus Option (A) is correct.

Final answer

Option (A)

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.