The following grammar is: S → Aa | bAc | dc | bda A → a
2020
The following grammar is:
S → Aa | bAc | dc | bda
A → a
Answer: D. LALR(1) and SLR(1) — CONCEPT: A state in the canonical LR(0) automaton carries a shift-reduce or reduce-reduce conflict only when TWO DIFFERENT items in that SAME state compete…
- A.
Neither LALR(1) nor SLR(1)
- B.
LALR(1) but not SLR(1)
- C.
Not LALR(1) but SLR(1)
- D.
LALR(1) and SLR(1)
Attempted by 167 students.
Show answer & explanation
Correct answer: D
CONCEPT: A state in the canonical LR(0) automaton carries a shift-reduce or reduce-reduce conflict only when TWO DIFFERENT items in that SAME state compete for the same lookahead symbol. SLR(1) restricts each reduce action to the lookaheads in FOLLOW of the reduced nonterminal — one GLOBAL, context-blind set covering every place that nonterminal ever appears in the grammar. LALR(1) instead computes, per state, the precise lookaheads a valid derivation can actually deliver there, which is never broader than FOLLOW (FOLLOW is the union across every context, not just the ones reaching this one state) — so wherever SLR(1)'s coarser FOLLOW-based check already avoids a clash in a state, LALR(1)'s narrower, state-specific lookaheads cannot manufacture a new clash there. So if a state in this grammar's LR(0) automaton never holds more than one completed item, and never holds a completed item alongside a shift action on the same symbol, there is only ONE production's item present to begin with — no amount of lookahead splitting can introduce a second, competing item into that state, so both SLR(1) and LALR(1) succeed there.
APPLICATION:
FOLLOW(A): A occurs in S → Aa (followed by 'a') and S → bAc (followed by 'c'), so FOLLOW(A) = {a, c}.
Build the canonical LR(0) item sets. The start state contains S′→•S, S→•Aa, S→•bAc, S→•dc, S→•bda, A→•a.
On symbol 'a' from the start state, the automaton moves to the state {A→a•} — a single completed item with no other item sharing that state.
After prefix 'b', the state {S→b•Ac, S→b•da, A→•a} also transitions on 'a' to that SAME state {A→a•} (identical item set), so the two paths converge on one state instead of colliding inside it.
Every other position that completes a handle — {S→Aa•}, {S→dc•}, {S→bAc•}, {S→bda•} — is likewise reached as a state containing exactly that one completed item, with no shift action or second reduce competing for any symbol in that same state.
So no state in the LR(0) automaton ever holds two competing actions on the same input symbol — the construction has zero shift-reduce or reduce-reduce conflicts even before any lookahead restriction is applied.
CROSS-CHECK: Every reduce-bearing state found above — {A→a•}, {S→Aa•}, {S→dc•}, {S→bAc•}, {S→bda•} — carries exactly one item, so there is never a second, competing item for LALR(1)'s finer per-state lookaheads to clash with. The FOLLOW(A) = {a, c} overlap only matters when it forces two DIFFERENT items into the same state, which never happens here. So the grammar succeeds under SLR(1) (the coarser check), and therefore also under LALR(1), whose lookaheads are never broader than SLR(1)'s.
Result: the grammar is parsable by both SLR(1) and LALR(1).
Explore the full course: Iocl Engineers Officers Grade A Paper 2