The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+14 votes

Consider the grammar:

$$S \rightarrow (S) \mid a$$

Let the number of states in SLR (1), LR(1) and LALR(1) parsers for the grammar be $n_1, n_2$ and $n_3$ respectively. The following relationship holds good:

- $n_1 < n_2 < n_3$
- $n_1 = n_3 < n_2$
- $n_1 = n_2 = n_3$
- $n_1 \geq n_3 \geq n_2$

+23 votes

Best answer

+1

@utsab if you try to draw the SLR(1) you would get 6 states and the given grammar is LR(0) so must be SLR(1),LALR(1),CLR(1)/LR(1) now if you try to draw LR(1) table

you would get 7 states and there 2 states will differ by only look ahead symbols

1) s->(.s), &

s->.(s), )

s->.a, )

2) s->(.s), )

s->.(s), )

s->.a, ) // you can minimizes the number of states by merging them and minimized CLR(1) is known as LALR(1) so you will get same number of states as SLR(1)

Answers would be (B) n1=n3<n2

you would get 7 states and there 2 states will differ by only look ahead symbols

1) s->(.s), &

s->.(s), )

s->.a, )

2) s->(.s), )

s->.(s), )

s->.a, ) // you can minimizes the number of states by merging them and minimized CLR(1) is known as LALR(1) so you will get same number of states as SLR(1)

Answers would be (B) n1=n3<n2

0

@arjun sir in this type of question where grammer are given and

Let the number of states in SLR (1), LR(1) and LALR(1) parsers for the grammar be n1 ,n2 and n3 respectively . so as we know in general n1=n3<n2 is it valid for any type of given grammer in question ?? or we go on the basis of given grammer and makes the state transition digram and count the no of states for each parser and then we will give the answer .

Let the number of states in SLR (1), LR(1) and LALR(1) parsers for the grammar be n1 ,n2 and n3 respectively . so as we know in general n1=n3<n2 is it valid for any type of given grammer in question ?? or we go on the basis of given grammer and makes the state transition digram and count the no of states for each parser and then we will give the answer .

–1

n1 = n3 < n2 is in general true ?

but it could also be n1 = n2 = n3 right ??

We should draw diagram for finding out . Don't we ?

but it could also be n1 = n2 = n3 right ??

We should draw diagram for finding out . Don't we ?

0

@arjun sir , is SLR(1) posible ?

r : S->(S)

r2: S->a

both will be placed under follow of S ?

Wont there be a reduce reduce conflict ?

r : S->(S)

r2: S->a

both will be placed under follow of S ?

Wont there be a reduce reduce conflict ?

+3

@Das there will no conflicts in SLR. Because reductions will be in two different states.

Although n1=n3 <= n2 is the general relationship between states. We must draw the state diagram for CLR to confirm. Reason behind selecting CLR is, if we draw it's diagram then we would guess what would happen in SLR and LALR

SLR - 6 states

CLR - 10 states

LALR - 6 states

+1

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.1k
- Digital Logic 2k
- Programming & DS 3.7k
- Algorithms 3.1k
- Theory of Computation 3.9k
- Compiler Design 1.5k
- Databases 2.9k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 1k
- Others 1.3k
- Admissions 449
- Exam Queries 428
- Tier 1 Placement Questions 17
- Job Queries 55
- Projects 8

35,499 questions

42,765 answers

121,499 comments

42,151 users