Consider the following context-free grammar where the start symbol is π andβ¦
2024
Consider the following context-free grammar where the start symbol is π and the set of terminals is {π,π,π,π}.
Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β π β π΄ππ΄π | π΅ππ΅π
Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β π΄ β ππ | π
Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β π΅ β ππ | π
The following is a partially-filled LL(1) parsing table
a | b | c | d | $ | |
S | π β π΄ππ΄π | π β π΅ππ΅π | (1) | (2) | |
A | Β π΄ βΒ π | (3) | π΄ βΒ ππ | ||
B | (4) | π΅Β βΒ π | π΅Β βΒ ππ |
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.
- A.
(1) π β π΄ππ΄π (2) π β π΅ππ΅π (3) π΄ β π (4) π΅ β π
- B.
(1) π β π΅ππ΅π (2) π β π΄ππ΄π (3) π΄ β π (4) π΅ β π
- C.
(1) π β π΄ππ΄π (2) π β π΅ππ΅π (3) blank (4) blank
- D.
(1) π β π΅ππ΅π (2) π β π΄ππ΄π (3) blank (4) blank
Attempted by 96 students.
Show answer & explanation
Correct answer: A
Key idea: compute FIRST and FOLLOW to fill the LL(1) table.
FIRST and FOLLOW sets (relevant parts):
FIRST(A) = {c, Ξ΅}; FIRST(B) = {d, Ξ΅}.
For S β A a A b, FIRST contains {c} from A and also 'a' because A can be Ξ΅ β so this production is predicted on lookahead 'c' or 'a'.
For S β B b B a, FIRST contains {d} from B and also 'b' because B can be Ξ΅ β so this production is predicted on lookahead 'd' or 'b'.
FOLLOW(A) = {a, b} and FOLLOW(B) = {a, b}, so A β Ξ΅ and B β Ξ΅ appear in the table cells for those terminals.
Therefore the correct entries for the numbered cells are:
(1) S β A a A b
(2) S β B b B a
(3) A β Ξ΅
(4) B β Ξ΅
This matches the option that assigns those productions to the numbered cells.
A video solution is available for this question β log in and enroll to watch it.