search
Log In
4 votes
1.1k views

Which of the following statements is FALSE?

  1. Any DCFL has an equivalent grammar that can be parsed by a SLR(1) parser with end string delimiter
  2. Languages of grammars parsed by LR(2) parsers is a strict super set of the languages of grammars parsed by LR(1) parsers
  3. Languages of grammars parsed by LL(2) parsers is a strict super set of the languages of grammars parsed by LL(1) parsers
  4. There is no DCFL which is not having a grammar that can be parsed by a LR(1) parser
in Compiler Design 1.1k views
0
d false
0
Which is that DCFL?
0

@Arjun Sir, is the answer C?

my reasoning is as follows,

consider a grammar

S -> aA/aB

A -> cA/c

B -> bB/b

The above grammar is LL(2).

now the above grammar can be converted into LL(1) as follows

S -> aS'

S' -> cA/ϵ

S' -> bB/ϵ

similarly every other LL(2) grammar should be convertable to LL(1) grammar.

                    

2
No, that is wrong. For every $k$ Language of LL(k) is a strict subset of Language of LL(k+1)
0

@Arjun Sir, Option A holds for both SLR(1) and LR(0) then?

1
Yes. It does.
2
$B?$

as, $Lang(LR(2))=Lang(LR(1))$
0
Yes.
0

@Arjun Option A holds for both SLR(1) and LR(0) then?

https://gatecse.in/category/compiler-design/

Sir, here it is mentioned that 

Language of LR(0) (set of all LR(0) grammars) is same as "DCFL having prefix property"

Then how can Option A hold true for LR(0)?

1
Yes. It does. SLR parser uses LR(0) items only.
0

Reffering from the diagram in... https://gateoverflow.in/1470/gate1999-1-17#16773

Iam confused how B is false.  @Arjun sir please help. which one of them is true.

0

@suraj20041995 diagram is referring to parsers…..In question languages of grammar is mentioned….

refer this  -https://gatecse.in/lr-parsing-part-2-language-of-ll-and-lr-grammars/

 

important points

 

2 Answers

0 votes
B is false because LR(k) is equivalent to LR(k+1) grammar not any superset relationship
0 votes
Answer is B

LR(0) ⊂ LR(1) = LR(2) ........LR(k) = LR(k+1)  ; for k >= 1 : LR(k)=LR(k+1)

so, Languages of grammars parsed by LR(2) parsers is not a strict super set of the languages of grammars parsed by LR(1) parsers

although they both are same ;

if you compare their grammars :

LR(0) ⊂ LR(1) ⊂ LR(2) ........LR(k) ⊂ LR(k+1)
0
Why you have mentioned LR(2) as a superset of LR(1)
0

1 . LR(2) Grammar is super-set of LR(1) grammar .

2 . Languages of grammars parsed by LR(2) parsers is same as Languages of grammars parsed by LR(1) parsers

please make sure , 1 statement is talking about grammar , 2 is talking about Language

Answer:

Related questions

2 votes
2 answers
1
484 views
Which of the following statements regarding $LR(0)$ parser is FALSE? A $LR(0)$ configurating set cannot have multiple reduce items A $LR(0)$ configurating set cannot have both shift as well as reduce items If a reduce item is present in a $LR(0)$ configurating set it cannot have any other item A $LR(0)$ parser can parse any regular grammar
asked Jan 26, 2019 in Compiler Design Arjun 484 views
2 votes
2 answers
2
535 views
Which of the following sentences regarding Viable prefixes is/are CORRECT? Viable prefixes is the set of prefixes of right-sentential forms that can appear on the stack of a shift-reduce parser Viable prefixes is the set of prefixes of right-sentential forms that do not extend past the end of the ... prefixes can be recognized using a DFA Only (i) Only (ii) Only (i) and (ii) (i), (ii) and (iii)
asked Jan 26, 2019 in Compiler Design Arjun 535 views
4 votes
1 answer
3
452 views
Which of the following is TRUE regarding LL(0) grammar? We can have a LL(0) grammar for any regular language We can have a LL(0) grammar for a regular language only if it does not contain empty string We can have a LL(0) grammar for any regular language if and only if it has prefix property We can have a LL(0) grammar for only single string languages
asked Jan 26, 2019 in Compiler Design Arjun 452 views
3 votes
1 answer
4
372 views
Match the following: $\begin{array}{|cc|cc|} \hline (i) &LL(1)&(A)& \text{bottom-up} \\ \hline (ii)& \text{Recursive Descent}& (B) &\text{Predictive} \\ \hline (iii) &\text{Recursive Ascent}& (C)& \text{Top-down} \\ \hline (iv) &LR(1) &(D)& \text{Deterministic CFL} \\ \hline \end{array}$ i-b; ii-c; iii-a; iv-d i-d; ii-a; iii-c; iv-d i-c; ii-b; iii-d; iv-a i-a; ii-c; iii-b; iv-d
asked Jan 26, 2019 in Compiler Design Arjun 372 views
...