24 votes 24 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$ Compiler Design gatecse-2005 compiler-design parsing normal + – Kathleen asked Sep 22, 2014 Kathleen 15.3k views answer comment Share Follow See 1 comment See all 1 1 comment reply Nitesh Singh 2 commented Jan 19, 2019 reply Follow Share no need to construct table just see the answer if it is unique standard relation then it is the answer. If not then make parsing diagram for CLR only because other will be same and extra state made in CLR then option B other wise option C 1 votes 1 votes Please log in or register to add a comment.
Best answer 38 votes 38 votes ans B Both in SLR(1) and LALR(1), states are the LR(0) items (LALR uses LR(1) items to form the states but then merges the ones having same items and different lookaheads) while in LR(1) the states are LR(1) set of items. Number of LR(0) items can never be greater than number of LR(1) items. So, $n_1 = n_3 \leq n_2$, B choice. If we construct the states for the grammar we can replace $\leq$ with $<$. Reference: https://gatecse.in/lr-parsing-part-4-slr-clr-lalr-and-summary/ Aditi Dan answered Dec 22, 2014 edited Nov 20, 2022 by Arjun Aditi Dan comment Share Follow See all 17 Comments See all 17 17 Comments reply Utsab commented Jan 19, 2016 reply Follow Share why 0 votes 0 votes Prateek kumar commented Aug 29, 2016 reply Follow Share @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 3 votes 3 votes rajan commented Sep 14, 2016 reply Follow Share @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 . 1 votes 1 votes Dulqar commented Oct 22, 2016 reply Follow Share 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 ? 0 votes 0 votes Dulqar commented Oct 22, 2016 reply Follow Share @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 ? 0 votes 0 votes pC commented Oct 22, 2016 i edited by pC Nov 16, 2016 reply Follow Share @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 33 votes 33 votes rajan commented Nov 16, 2016 reply Follow Share @pc kindly check ur clr it will having 10 states not 8 . and their is no conflict either S-R or R-R 1 votes 1 votes pC commented Nov 16, 2016 i edited by pC Nov 16, 2016 reply Follow Share @rajan What are the 10 states you are talking about ? Can you show the states ? We can discuss. I think It will be 8 states only. I didn't account for any conflicts here as the question is interested in olny finding number of states . 0 votes 0 votes rajan commented Nov 16, 2016 reply Follow Share yr just see S->(.S),) on S it will go S->(S.) , ) not on S->(S.),$ 1 votes 1 votes pC commented Nov 16, 2016 reply Follow Share @rajan , ys you are right ! I corrected my mistake . Thanks for pointing it out :) 1 votes 1 votes rajan commented Nov 16, 2016 reply Follow Share no problem bro 1 votes 1 votes Sonu Kumar 1 commented Jul 17, 2017 reply Follow Share I think, LALR(1) uses canonical collection of LR(1) items, but you have mentioned that it uses LR(0) items. 1 votes 1 votes sardendu commented Sep 23, 2018 reply Follow Share Option a and d is wrong since n2 is less than n3, which is not possible And to choose between b and c draw clr(1) graph you will get same item with different lookahead 0 votes 0 votes mehul vaidya commented Sep 25, 2018 reply Follow Share @pC please post this as answer 0 votes 0 votes KUSHAGRA गुप्ता commented Nov 2, 2019 i edited by KUSHAGRA गुप्ता Nov 2, 2019 reply Follow Share @Aditi Dan @pC @rajan Both in SLR(1) and LALR(1), states are the LR(0) items I think for LALR(1) it's is LR(1) Items only Even here also it's written same https://gateoverflow.in/478/gate2008-55 2 votes 2 votes abir_banerjee commented Oct 22, 2022 reply Follow Share @Lakshman Patel RJIT please edit the answer because only SLR(1) is collection of LR(0) items and LR(1) and LALR(1) are collection of LR(1) items. 1 votes 1 votes Arjun commented Nov 20, 2022 reply Follow Share @abir_banerjee That's not exactly true. Please see the answer now. 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes LALR(1) is formed by merging states of LR(1) ( also called CLR(1)), hence no of states in LALR(1) is less than no of states in LR(1), therefore n3 < n2. And SLR(1) and LALR(1) have same no of states, i.e ( n1 = n3). Hence n1 = n3 < n2 sujaygoswami answered Dec 29, 2021 sujaygoswami comment Share Follow See all 0 reply Please log in or register to add a comment.