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)?
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)?
Show Hint
- A
- B
- C
- D
The Correct Option is A
Solution and Explanation
Step 1: Compute FIRST sets.
FIRST(S) = { d, c, f }
FIRST(T) = { a, b, ε }
FIRST(R) = { c, ε }
Step 2: Compute FOLLOW sets.
From the given grammar productions:
FOLLOW(S) = { $, f }
FOLLOW(T) = { c, f, $ }
FOLLOW(R) = { f }
Step 3: Construct the LL(1) parsing table.
For production S → Rf:
FIRST(Rf) = { c, f }
Therefore, the parsing table entries under terminals c and f will contain the production S → Rf.
Hence:
① = S → Rf
② = S → Rf
For production T → ε:
Since ε ∈ FIRST(T), this production is placed in all columns
corresponding to FOLLOW(T).
FOLLOW(T) = { c, f, $ }
Thus:
③ = T → ε
④ = T → ε
Final Conclusion:
All numbered entries in the LL(1) parsing table are correctly filled
as described in option (A).
Top Questions on Parsing
- Which one of the following statements is TRUE?
Consider the augmented grammar with \(\{+,* , (, ), id\}\) as the set of terminals. \[ S' \rightarrow S \] \[ S \rightarrow S + R \mid R \] \[ R \rightarrow R^{\,*} P \mid P \] \[ P \rightarrow (S) \mid id \] If \(I_0\) is the set of two LR(0) items \(\{[S' \rightarrow S.], [S \rightarrow S. + R]\}\), then \(goto(\text{closure}(I_0), +)\) contains exactly \(\underline{\hspace{1cm}}\) items.
Consider the following ANSI C program:
int main() { Integer x; return 0; }Which one of the following phases in a seven-phase C compiler will throw an error?
Consider the following augmented grammar with terminals {#, @, <, >, a, b, c}.
$S' → S$
$S → S\#cS$
$S → SS$
$S → S@$
$S → <S>$
$S → a$
$S → b$
$S → c$Let I0 = CLOSURE({ S' → • S }). The number of items in the set GOTO(GOTO(I0, <), <) is .
- Want to practice more? Try solving extra ecology questions todayView All Questions