GATE Overflow | Compiler Design | Test 1 | Parsing | Question: 4

Question

Which of the following statements is FALSE?

• A. In a SLR(1) parser, it is allowable for both shift and reduce items to be in the same state
  
• B. In a SLR(1) parser, it is allowable for multiple reduce items to be in the same state
  
• C. All SLR(1) grammars are LR(0)
  
• D. All LR(0) grammars are SLR(1)

Comments

C.

LR(0) < SLR(1) < LALR(1) < LR(1)

LL(1) < LR(1) and LL(0) < LR(0)

LL(k) < LR(k)

---

Is this question is for TRUE statement?

---

main key points for both option a and b are that 

 

They are talking about items not conflicts

Answer 1

1. In a SLR(1) parser, it is allowable for both shift and reduce items to be in the same state 

                     even though it leads to SR conflict but it is allow

        2. In a SLR(1) parser, it is allowable for multiple reduce items to be in the same state 

                     even though it leads to SR conflict but it is allow

       3. All SLR(1) grammars are LR(0) 

                  this statement is wrong. Reason is

                  LR(0)<SLR(1)<LALR(1)<CLR(1)

                   --> if a grammar is LR(0) then it is also SLR(1),LALR(1),CLR(1).

                   --> if a grammar is SLR(1) then it is also LALR(1),CLR(1).

                   --> if a grammar is LALR(1) then it is also CLR(1).

        4.All LR(0) grammars are SLR(1)

Therefore C is Correct.

Comments

How SLR(1) parser will allow both shift and reduce/reduce and reduce items to be in the same state?

---

On option A and B is true because of lookahead symbol ???

Plz explain why Option A and B is true

---

In SLR(1) table we place the reduce moves  in FOLLOW(LHS of the production).

So if we have , $A \rightarrow \alpha. $ and $B \rightarrow \beta. $ in same state then if $FOLLOW(A) \cap FOLLOW(B) = \phi$ then there will be no R-R conflict in SLR(1) since these reduce moves will be placed n different cells.

similarly,

if we have , $A \rightarrow \alpha . C $ and $B \rightarrow \beta. $ in same state then if $FOLLOW(B) \neq \ cell \ at \ which \ shift \ move \ will \ be \ placed $ then there will be no conflict in SLR(1)