Consider the grammar: A → AB ∣ a B → *AC | Cb | e C → +ABc | e We are…
Consider the grammar:
A → AB ∣ a
B → *AC | Cb | e
C → +ABc | e
We are constructing a Canonical LR(1) (CLR(1)) parser for the above grammar.
Let I₀ be the initial state of the LR(1) parser.
When the parser reads symbol A from state I₀, it moves to a new state.
What is the next state reached on input A from state I₀, and what are the productions (items) contained in that state?
Answer: C. S' → A•, {$} A → A • B, {$,*,+,e} B → • AC, {$,,+,e} B → • Cb, {$,*,+,e} B → • e, {$,*,+,e} C → • +ABc, {b} C → • e, {b} — Canonical LR(1) state reached by goto(I0, A): S' → A •, { $ } A → A • B, { $, *, +, b } B → • * A C, { $, *, +, b } B → • C b, { $, *, +, b } B → • e, { $, *,…
- A.
S' → A•, $
A → A • B, $
B → • *AC, $
B → • Cb, $
B → • e, b
C → • +ABc, b
C → • e, b
- B.
S' → A•, {$}
A → A • B, {$,*,+}
B → • AC, {$,,+}
B → • Cb, {$,*,+}
B → • e, {$,*,+}
C → • +ABc, {b}
C → • e, {b}
- C.
S' → A•, {$}
A → A • B, {$,*,+,e}
B → • AC, {$,,+,e}
B → • Cb, {$,*,+,e}
B → • e, {$,*,+,e}
C → • +ABc, {b}
C → • e, {b}
- D.
S' → A•, {$}
A → A • B, {$,*,+,e}
B → • AC, {$,,+,e}
B → • Cb, {$,*,+,e}
B → • e, {$,*,+,e}
C → • +ABc, {$,b}
C → • e, {$,b}
Attempted by 40 students.
Show answer & explanation
Correct answer: C
Canonical LR(1) state reached by goto(I0, A):
S' → A •, { $ }
A → A • B, { $, *, +, b }
B → • * A C, { $, *, +, b }
B → • C b, { $, *, +, b }
B → • e, { $, *, +, b }
C → • + A B c, { b }
C → • e, { b }
Notes: The lookahead set { $, *, +, b } for the B items comes from computing FIRST(B $) when expanding A → A • B: FIRST(B) = { '*', '+', 'b', ε }, and because B can derive ε we also include $.
A video solution is available for this question — log in and enroll to watch it.