GATE CSE 2003 | Question: 17

Question

Assume that the SLR parser for a grammar G has $n_1$ states and the LALR parser for G has $n_2$ states. The relationship between $n_1$ and $n_2$ is

• A. $n_1$ is necessarily less than $n_2$
• B. $n_1$ is necessarily equal to $n_2$
• C. $n_1$ is necessarily greater than $n_2$
• D. None of the above

Comments

please explain me why n1 is necessarily equal to n2 and why not n1 is necessarily less than n2.

---

states in LALR (n2) necessarily equal [and even can be less in LR(1) ]   than in SLR (n1) states bcz many of the states having same lookahead can be combined 

---

in LALR the number of states does not increase based on the look ahead like LR(1), it merges the states having same core item and different lookahead into 1 in LALR(1) so number of states in LALR(1) and SLR(1) are same

---

$$\text{Number of states: } \mathbf{\text{LR}(0) = \text{SLR}(1) = \text{LALR}(1) \le \text{LR}(1)}$$

Answer 1

no. of states in $\text{SLR}$ and $\text{LALR}$ are equal.

and no. of states in $\text{SLR}$ and $\text{LALR}$ are less than or equal to $\text{LR(1).}$

Correct Answer: $B$

Comments

@Rishabh HEre comparision is asked for SLR(1) and LALR(1) in questions and no. in states in both these are equal.

---

yes n2(no of states in LALR)<=n1(no of states in S;R)
But, ( '=' is less stricter condn that '<')
So, n2 < n1 is not a necessity, we can have n2=n1 too for LALR and SLR parser.

---

Here are some Handouts from stanford if someone having any  doubt can refer these 

Microsoft Word - 11-LALR-Parsing.doc (ans for the above question ).

CS106X Handout #01(more details about slr, clr parsers)

 

Answer 2

no of states

$CLR(1)>=LR(0)=SLR(1)=LALR(1)$

Answer 3

ans b)

Comments

I think it should be less than equal to?

---

So pls explain whether it is less than equals to or only equal?

Answer 4

In the LALR parser, we only consider the core part of LR(1) items while merging. And in the SLR parser, we only have the core part.
So in LR(1) parser, the increased number of states may appear due to differences in the lookaheads.
Once you ignore the lookaheads in LR(1), the SLR and LALR parsers look the same.