Consider the following grammar. S -> S * E S -> E E -> F + E E -> F F -> id…
2006
Consider the following grammar.
S -> S * E
S -> E
E -> F + E
E -> F
F -> idConsider the following LR(0) items corresponding to the grammar above.
(i) S -> S * .E
(ii) E -> F. + E
(iii) E -> F + .E Given the items above, which two of them will appear in the same set in the canonical sets-of-items for the grammar?
- A.
(i) and (ii)
- B.
(ii) and (iii)
- C.
(i) and (iii)
- D.
None of the above
Attempted by 70 students.
Show answer & explanation
Correct answer: D
Answer: None of the above.
Explanation:
S -> S * .E : appears in the state reached after shifting '*' following an S; this state expects an E next and its closure contains the productions for E with the dot at the beginning.
E -> F. + E : appears in the state reached after completing F (the dot is after F); this state expects a '+' next and contains items with the dot after F.
E -> F + .E : appears in the state reached after shifting '+'; the dot is before E and the closure adds E productions with the dot at the beginning, but the core of the state includes the preceding '+'
Because each item corresponds to a different parsing context (one after '*', one after finishing F, and one after '+'), they occur in three distinct canonical LR(0) item sets. Therefore none of the given pairs appear together in the same set.
A video solution is available for this question — log in and enroll to watch it.