Discussion
Consider the following context-free grammar where the start symbol is \(S\) and the set of terminals is \(\{a,b,c,d\}\).
\(S \to AaAb \mid BbBa\)
\(A \to cS \mid \epsilon\)
\(B \to dS \mid \epsilon\)
The following is a partially-filled LL(1) parsing table.
| \(a\) | \(b\) | \(c\) | \(d\) | $ | |
|---|---|---|---|---|---|
| \(S\) | \(S \to AaAb\) | \(S \to BbBa\) | (1) | (2) | |
| \(A\) | \(A \to \epsilon\) | (3) | \(A \to cS\) | ||
| \(B\) | (4) | \(B \to \epsilon\) | \(B \to dS\) |
Which one of the following options represents the CORRECT combination for the numbered cells in the parsing table?
Note: In the options, "blank" denotes that the corresponding cell is empty.
Answer: A
The correct combination is (1) \(S \to AaAb\), (2) \(S \to BbBa\), (3) \(A \to \epsilon\), (4) \(B \to \epsilon\).
FIRST sets decide the S row. \(AaAb\) can begin with c (from \(A \to cS\)) or, with A empty, with a, so FIRST\((AaAb) = \{a, c\}\); likewise FIRST\((BbBa) = \{b, d\}\). So cell (1), under c, holds \(S \to AaAb\) and cell (2), under d, holds \(S \to BbBa\).
An \(\epsilon\)-production goes under every terminal in the FOLLOW set. In \(S \to AaAb\), A is followed by a and by b, so FOLLOW\((A) = \{a, b\}\) and cell (3), under b, is \(A \to \epsilon\). In \(S \to BbBa\), B is followed by b and by a, so cell (4), under a, is \(B \to \epsilon\).
The options swapping (1) and (2) mix up the FIRST sets, and leaving (3) and (4) blank ignores the FOLLOW sets.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development