Consider the following context-free grammar where the set of terminals is…
2021
Consider the following context-free grammar where the set of terminals is {a,b,c,d,f}.
\(\begin{array}{lll} \text{S} & \rightarrow & d \: a \: \text{T} \mid \text{R} \: f \\ \text{T} & \rightarrow & a \: \text{S} \: \mid \: b \: a \: \text{T} \: \mid \epsilon \\ \text{R} & \rightarrow & c \: a \: \text{T} \: \text{R} \: \mid \epsilon \end{array}\)
The following is a partially-filled LL(1) parsing table.
\(\begin{array} {c c c } & a & b & c & d & f & \$ \\\hline \text{S} & & & \boxed{1} & \text{S} \rightarrow da \text{T} & \boxed{2} & \\\hline \text{T} & \text{T} \rightarrow a\text{S} & \text{T} \rightarrow ba\text{T} & \boxed{3} & & \text{T} \rightarrow \varepsilon & \boxed{4}\\\hline \text{R} & & & \text{R} \rightarrow ca\text{T}\text{R} & & \text{R} \rightarrow \varepsilon & \end{array}\)
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.
\(\boxed{1}\;\text{S} \rightarrow \text{R}f \qquad \boxed{2}\;\text{S} \rightarrow \text{R}f \qquad \boxed{3}\; \text{T} \rightarrow \varepsilon \qquad \boxed{4}\;\text{T} \rightarrow \varepsilon\) - B.
\(\boxed{1}\;\text{blank} \qquad \boxed{2}\;\text{S} \rightarrow \text{R}f \qquad \boxed{3}\; \text{T} \rightarrow \varepsilon \qquad \boxed{4}\;\text{T} \rightarrow \varepsilon\) - C.
\(\boxed{1}\;\text{S} \rightarrow \text{R}f \qquad \boxed{2}\;\text{blank} \qquad \boxed{3}\; \text{blank} \qquad \boxed{4}\;\text{T} \rightarrow \varepsilon\) - D.
\(\boxed{1}\;\text{blank} \qquad \boxed{2}\;\text{S} \rightarrow \text{R}f \qquad \boxed{3}\; \text{blank} \qquad \boxed{4}\;\text{blank}\)
Attempted by 114 students.
Show answer & explanation
Correct answer: A
Solution overview:
Compute FIRST sets:
FIRST(T) = {a, b, ε} (T -> a S, T -> b a T, T -> ε).
FIRST(R) = {c, ε} (R -> c a T R, R -> ε).
FIRST(S) = {d} ∪ FIRST(R f). Since FIRST(R) contains c and ε, FIRST(S) = {d, c, f}.
Compute FOLLOW sets:
Start with FOLLOW(S) containing $ (S is the start symbol).
From S -> d a T and T -> b a T and R -> c a T R, T is followed by nothing or by R. This gives c from FIRST(R) and also FOLLOW(S) and FOLLOW(R).
From S -> R f, FOLLOW(R) contains f.
Collecting these gives FOLLOW(R) = {f} and FOLLOW(T) = {c, f, $} (and FOLLOW(S) contains $ and propagates into FOLLOW(T)).
Fill the parsing table using FIRST and FOLLOW:
Cell 1 (S row, c column): Use S -> R f because c ∈ FIRST(R).
Cell 2 (S row, f column): Use S -> R f because R can be ε, so R f can start with f.
Cell 3 (T row, c column): Use T -> ε because c ∈ FOLLOW(T).
Cell 4 (T row, $ column): Use T -> ε because $ ∈ FOLLOW(T).
Therefore the correct entries are: both S entries are S -> R f (for c and f), and both numbered T entries are T -> ε (for c and $).
A video solution is available for this question — log in and enroll to watch it.