in Compiler Design
11,132 views
26 votes
26 votes

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

  1. $n_1$ is necessarily less than $n_2$
  2. $n_1$ is necessarily equal to $n_2$
  3. $n_1$ is necessarily greater than $n_2$
  4. None of the above
in Compiler Design
11.1k views

1 comment

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

4 Answers

37 votes
37 votes
Best answer
no of states in SLR and LALR are equal

and no of states in SLR and LALR are less than or equal to LR(1)

Correct Answer: $B$
edited by

4 Comments

Answer should be D. Right?

Because no of states in SLR and LALR are less than or equal to LR(1)

0
0
@Rishabh HEre comparision is asked for SLR(1) and LALR(1) in questions and no. in states in both these are equal.
1
1
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.
0
0
23 votes
23 votes
no of states

CLR(1)>=LR(0)=SLR(1)=LALR(1)
by
5 votes
5 votes
ans b)

2 Comments

I think it should be less than equal to?
1
1
So pls explain whether it is less than equals to or only equal?
0
0
0 votes
0 votes
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.
Answer:

Related questions