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

Question

Which of the below relations does hold TRUE regarding GRAMMARS?

• A. $LL(1) \subset SLR(1) \subset LR(1)$
  
• B. $SLR(1) \subset \epsilon-\text{free}\; LL(1) \subset LR(1)$
  
• C. $\epsilon-\text{free}\;LL(1) \subset SLR(1) \subset LR(1)$
  
• D. $LL(1) \subset SLR(1) = LR(1)$

Comments

Why 'A' is wrong???

@Arjun

---

There are some grammar exists which are not SLR but they are LL(1) that's why A is wrong

---

Can you explain why C is correct??

---

How is B True?

---

Every $\epsilon$-free LL(1) is SLR(1) - you can see this in any Compiler text or even Wikipedia.

@sripo B is not true

---

If $\epsilon - \text{free LL(1)} = SLR(1)$ then how option C is correct?

---

every $\epsilon$-free LL(1) grammar is SLR(1) grammar means the set of $\epsilon$-free LL(1) grammars is within the set of  SLR(1) grammars.

To prove 2 sets A and B are equal ,  we have to prove that $A\subseteq B$  and $B\subseteq A$. So, if we consider  $\epsilon$-free LL(1) = SLR(1) is true then all the SLR(1) grammars should also be the subset of set of $\epsilon$-free LL(1) grammars which is not true.

---

if in case  $\epsilon $ free  grammar is  not LL(1)

A->Ax/y grammar but not LL(1) Also  $\epsilon $ free

ithink first option right it it hold any type of CFG

Answer 1

Answer : C

ϵ−free LL(1) ⊂ SLR(1) ⊂ LR(1)

because every ϵ−free LL(1) are SLR(1) and every SLR(1) are LR(1)