The Gateway to Computer Science Excellence
+5 votes
Which of the below relations does hold TRUE regarding GRAMMARS?
  1. $LL(1) \subset SLR(1) \subset LR(1)$
  2. $SLR(1) \subset \epsilon-\text{free}\; LL(1) \subset LR(1)$
  3. $\epsilon-\text{free}\;LL(1) \subset SLR(1) \subset LR(1)$
  4. $LL(1) \subset SLR(1) = LR(1)$
in Compiler Design by Veteran (431k points) | 222 views

Why 'A' is wrong???


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

1 Answer

0 votes
Answer : C

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

because every ϵ−free LL(1) are SLR(1) and every SLR(1) are LR(1)
by Junior (987 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,367 answers
105,266 users