Question

Consider the following context-free grammar where the set of terminals is \(\{a,b,c,d,f\}\): 
\[ S \rightarrow daT \mid Rf \] \[ T \rightarrow aS \mid baT \mid \epsilon \] \[ R \rightarrow caTR \mid \epsilon \] The following is a partially-filled LL(1) parsing table. 

Which one of the following choices represents the correct combination for the numbered cells in the parsing table ("blank" denotes that the corresponding cell is empty)? 

• A. A
• B. B
• C. C
• D. D

Hint:

For LL(1) parsing tables, use FIRST sets to place productions, and when \(\epsilon\) occurs, use FOLLOW sets to complete the table.

Answer 1

The Correct Option is A

Step 1: Compute FIRST sets.
\[ \text{FIRST}(S) = \{d, c, f\} \] \[ \text{FIRST}(T) = \{a, b, \epsilon\} \] \[ \text{FIRST}(R) = \{c, \epsilon\} \]

Step 2: Compute FOLLOW sets.
From the grammar rules, we obtain: \[ \text{FOLLOW}(S) = \{\$, f\} \] \[ \text{FOLLOW}(T) = \{c, f, \$\} \] \[ \text{FOLLOW}(R) = \{f\} \]

Step 3: Fill the LL(1) parsing table.
• For \(S \rightarrow Rf\): Since \(\text{FIRST}(Rf) = \{c, f\}\), the entries under columns \(c\) and \(f\) must contain \(S \rightarrow Rf\). Hence, ① = \(S \rightarrow Rf\) and ② = \(S \rightarrow Rf\).
• For \(T \rightarrow \epsilon\): Because \(\epsilon \in \text{FIRST}(T)\), we place \(T \rightarrow \epsilon\) in all columns corresponding to \(\text{FOLLOW}(T)\), which includes \(c\), \(f\), and \(\$\). Thus, ③ = \(T \rightarrow \epsilon\) and ④ = \(T \rightarrow \epsilon\).

Step 4: Conclusion.
All numbered entries are correctly filled as specified in option (A).