Consider the following grammar \(G\), with \(S\) as the start symbol. The grammar \(G\) has three incomplete productions denoted by (1), (2), and (3).
\(S \to daT \mid \underline{\quad (1) \quad}\)
\(T \to aS \mid bT \mid \underline{\quad (2) \quad}\)
\(R \to \underline{\quad (3) \quad} \mid \epsilon\)
The set of terminals is \(\{a, b, c, d, f\}\). The FIRST and FOLLOW sets of the different non-terminals are as follows.
FIRST(\(S\)) = \(\{c, d, f\}\), FIRST(\(T\)) = \(\{a, b, \epsilon\}\), FIRST(\(R\)) = \(\{c, \epsilon\}\)
FOLLOW(\(S\)) = FOLLOW(\(T\)) = \(\{c, f, \$\}\), FOLLOW(\(R\)) = \(\{f\}\)
Which one of the following options CORRECTLY fills in the incomplete productions?
Answer
(A)
Explanation
- (2): FIRST(\(T\)) contains \(\epsilon\) but not \(c\), so the missing rule is \(T \to \epsilon\). \(T \to cT\) (options C, D) would put \(c\) into FIRST(\(T\)) and leave \(\epsilon\) out.
- (1): \(c \in\) FIRST(\(S\)) can only come through \(R\). With \(S \to Rf\) and \(R\) nullable, FIRST(\(Rf\)) = \(\{c, f\}\), so FIRST(\(S\)) = \(\{c, d, f\}\). \(S \to fR\) would miss \(c\) and would also put \(\$\) into FOLLOW(\(R\)).
- (3): \(R \to cTR\) gives FIRST(\(R\)) = \(\{c, \epsilon\}\). In it \(T\) is followed by \(R\), so FOLLOW(\(T\)) gets \(c\) and, because \(R\) can vanish, also FOLLOW(\(R\)) = \(\{f\}\), which comes from \(S \to Rf\). With \(S \to daT\) and \(T \to aS\), FOLLOW(\(S\)) = FOLLOW(\(T\)) = \(\{c, f, \$\}\), exactly the given sets.
Answer: A