Given a Context-Free Grammar 𝐺 as follows: 𝑆 β†’ π΄π‘Ž | 𝑏𝐴𝑐 | 𝑑𝑐 | π‘π‘‘π‘Žβ€¦

2025

Given a Context-Free Grammar 𝐺 as follows:

𝑆 β†’ π΄π‘Ž | 𝑏𝐴𝑐 | 𝑑𝑐 | π‘π‘‘π‘Ž

𝐴 β†’ 𝑑

Which ONE of the following statements is TRUE?

  1. A.

    𝐺 is neither LALR(1) nor SLR(1)

  2. B.

    𝐺 is CLR(1), not LALR(1)

  3. C.

    𝐺 is LALR(1), not SLR(1)

  4. D.

    𝐺 is LALR(1), also SLR(1)

Attempted by 82 students.

Show answer & explanation

Correct answer: C

Classification result: The grammar is LALR(1), not SLR(1).

Reasoning and key steps:

  • Grammar productions: S β†’ A a | b A c | d c | b d a ; A β†’ d.

  • Compute FOLLOW(A): A appears in S β†’ A a and S β†’ b A c, so FOLLOW(A) = {a, c}.

  • Why SLR(1) fails: consider the LR(0) state reached after reading a single terminal d. That state contains the items S β†’ d Β· c and A β†’ d Β·. Under SLR(1) a reduction A β†’ d is allowed on any lookahead in FOLLOW(A), including c. On lookahead c the parser therefore has both a shift action (for S β†’ d c) and a reduction action (for A β†’ d), producing a shift–reduce conflict. Hence the grammar is not SLR(1).

  • Why LR(1)/LALR(1) succeed: canonical LR(1) attaches lookaheads to items, distinguishing the two contexts where A β†’ d completes. One LR(1) item for A β†’ d occurs with lookahead c (when coming from S β†’ d c) and another with lookahead a (when coming from b d a). These contexts do not introduce a conflicting action in LR(1).

  • LALR(1) merges LR(1) states that have identical LR(0) cores. In this grammar the LR(1) states completing A β†’ d do not have identical cores with conflicting lookaheads, so LALR(1) does not introduce a conflict and the grammar remains parsable by an LALR(1) parser.

  • Conclusion: the correct statement is the one that says the grammar is LALR(1) but not SLR(1). Note that the original answer flag in the question incorrectly marked the statement that the grammar is both LALR(1) and SLR(1) as correct; that mark is wrong given the SLR(1) conflict explained above.

A video solution is available for this question β€” log in and enroll to watch it.

Explore the full course: Gate Guidance By Sanchit Sir