GATE CSE 2025 | Set 2 | Question: 30

Question

​​Given a Context-Free Grammar $\text{G}$ as follows:
\[
\begin{array}{l}
S \rightarrow A a|b A c| d c \mid b d a \\
A \rightarrow d
\end{array}
\]

Which ONE of the following statements is TRUE?

• A. $\text{G}$ is neither $\operatorname{LALR}(1)$ nor $\operatorname{SLR}(1)$
• B. $\text{G}$ is $\text{CLR(1)}$, not $\text{LALR(1)}$
• C. $\text{G}$ is $\operatorname{LALR}(1), \operatorname{not} \operatorname{SLR}(1)$
• D. $\text{G}$ is $\operatorname{LALR}(1)$, also $\operatorname{SLR}(1)$

Comments

Source of Question:https://people.cs.vt.edu/~ryder/515/f05/homework/hw1ans

---

Option C is correct, as it is both CLR(1) and LALR(1) but not SLR(1)

---

someone please tell me in exam how i solve this type of question since its takes too much time to construct ... ......

Answer 1

Parsing table for SLR(1) Parser

$$
\begin{array}{|c|c|c|c|c|c|c|c|}
\hline
\text{State} & a & b & c & d & \$ & S & A \\
\hline
I_0 &   & s3 &   & s4 &   & 1 & 2 \\
\hline
I_1 &   &   &   &   & \text{acc} &   &   \\
\hline
I_2 & r3 &   &   &   &   &   &   \\
\hline
I_3 &   &   &   & s7 &   &   & 6 \\
\hline
I_4 & r4 &   & \color{red}{\text{s8 / r4}} &   &   &   &   \\
\hline
I_5 &   &   &   &   & r3 &   &   \\
\hline
I_6 &   &   & s9 &   &   &   &   \\
\hline
I_7 &  \color{red}{\text{s10 / r5}} &   & r4 &   &   &   &   \\
\hline
I_8 &   &   &   &   & r1 &   &   \\
\hline
I_9 &   &   &   &   & r2 &   &   \\
\hline
I_{10} &   &   &   &   & r5 &   &   \\
\hline
\end{array}
$$

• Has a shift-reduce conflict at I4

---

 

Parsing Table for CLR(1), LALR(1)

$$
\begin{array}{|c|c|c|c|c|c|c|c|}
\hline
\text{State} & a & b & c & d & \$ & S & A \\
\hline
I_0 &   & s3 &   & s4 &   & 1 & 2 \\
\hline
I_1 &   &   &   &   & \text{acc} &   &   \\
\hline
I_2 & r3 &   &   &   &   &   &   \\
\hline
I_3 &   &   &   & s7 &   &   & 6 \\
\hline
I_4 & r4 &   & s8 &   &   &   &   \\
\hline
I_5 &   &   &   &   & r3 &   &   \\
\hline
I_6 &   &   & s9 &   &   &   &   \\
\hline
I_7 & s10 &   & r4 &   &   &   &   \\
\hline
I_8 &   &   &   &   & r1 &   &   \\
\hline
I_9 &   &   &   &   & r2 &   &   \\
\hline
I_{10} &   &   &   &   & r5 &   &   \\
\hline
\end{array}
$$

 

No conflicts . $\therefore$ grammar is LR(1) and LALR(1)

$$\color{lime} \boxed{\text{Answer: C}}$$

Comments

Follow(A) = {a,c}
SLR(1) table
on I7(a column) = S10/R4 is also shift reduce conflict

---

Do you write these answers on your own? The quality of every answer and the formatting is top notch. Great job

Answer 2

We are given the grammar GG:

S → Aa | bAc | dc | bda  
A → d

We are to identify which class of LR grammars this belongs to:

• SLR(1)

• LALR(1)

• CLR(1)

Let’s go step by step.

We have:

• S → Aa | bAc | dc | bda

• A → d

Let’s identify possible FIRST and FOLLOW sets.

FIRST sets

• FIRST(A) = FIRST(d) = { d }

• FIRST(S): From the productions:

  • Aa → starts with A → d → so FIRST(Aa) = { d }

  • bAc → starts with b

  • dc → starts with d

  • bda → starts with b

So FIRST(S) = { d, b }

FOLLOW sets

We need FOLLOW(A), because A appears in right-hand sides.

• In production S → Aa:
  FOLLOW(A) includes { a }

• In production S → bAc:
  FOLLOW(A) includes { c }

So FOLLOW(A) = { a, c }

Let’s analyze the parsing table construction for SLR(1).

In SLR(1), the reduce actions are placed based on FOLLOW sets only.

We note that A → d is the only production for A.

So when A → d is completed, the parser will try to reduce A → d in states where the lookahead is in FOLLOW(A) = { a, c }

Now, look at productions:

• S → Aa → A followed by a

• S → bAc → A followed by c

So, in states after reducing A → d, both terminals a and c may trigger reductions.

If, however, in the parser state, there is a shift on a or c also possible, SLR(1) will show a shift-reduce conflict.

But in LALR(1) and CLR(1), the parser distinguishes the exact lookaheads in those specific contexts, possibly avoiding the conflict.

• SLR(1) may have shift-reduce conflicts due to using FOLLOW(A) = {a, c} too broadly.

• LALR(1) uses more precise lookaheads per state — likely resolves the conflict.

• CLR(1) (canonical LR) has even more precision (uses full LR(1) items).

Hence:

• The grammar is LALR(1) and SLR(1)

  • only if no conflicts occur in FOLLOW(A).

• If a conflict exists in SLR(1) but is resolved in LALR(1), then it's LALR(1), not SLR(1).

• If only CLR(1) works, then it's CLR(1), not LALR(1).

This grammar does cause an SLR(1) conflict but is parsable by LALR(1).

C) G is LALR(1), not SLR(1)

Answer 3

Not LL(1) , Not SLR(1) but
both CLR(1) and LALR(1)
So Option C

S->d. ,  c 
[A->d. , c]   as well as  [A->d. ,  a]  both the states causing  conflict for SLR(1)

Answer 4

So the answer is C

Answer 5

Easiest and Shortest Solution👍

$\text{The trick here is to identify the productions that can end in between it means }$

$\text{the production that can show reduce moves in between and here that production is last one }$

$\text{ which is second one $ A  \rightarrow d $ .}$

---

$\text{Now just we have to do one thing have to see which production will be there stilll in processing }$

$\text{while this production has ended that can be followed using the $$ FOLLOW(A) = \{a, c\} $$ .}$

$\text{So look for production like this where $ S  \rightarrow dc $}$

$\text{Because this production will have this situation $ A  \rightarrow d.c $ }$

$\text{and we were looking for this ambiguity that is which means in general we can say any symbol $ A  \rightarrow \alpha $ }$

$\text{and there is a production that is of the form $ S  \rightarrow \alpha follow(A) $ then there is problem. }$

---

$\text{Also if the problem is occuring due to this shortness of production of one state,}$

$\text{ its mostly chance it will be resolved in LALR}$

Comments

Bro, if you have time, can you explain this a bit more clearly?

---

me is saying the grammar is not SLR(1) because of shift reduce conflict that's why may be it is resolved by LALR

rather than first check lalr(1) then go for SLR(1) u can get easily marks and time same

Answer 6

Answer: C

This grammar is a classic example used to illustrate the gap between SLR(1) and LALR(1) parsing power. Building the LR(0)/canonical item sets for this grammar reveals a state where two different reduce actions (A→dA→d competing against other productions) become ambiguous only when using the coarser, context-blind FOLLOW-set-based lookahead that SLR(1) relies on — because SLR(1) uses the same global FOLLOW(A)FOLLOW(A) set everywhere AA could be reduced, regardless of the surrounding context in each specific state, and this particular grammar has states where that global FOLLOW set is too imprecise, causing a genuine reduce-reduce conflict under SLR(1).

LALR(1), by contrast, computes lookahead sets per LR(0) state (context-specific, based on merging LR(1) item sets with identical cores), which is precise enough to correctly disambiguate this same situation without any conflict.