0
$\begingroup$

This question already has an answer here:

I know that:

Point 1: Set of languages accepted by $LR(0)$ parsers $\subset$ Set of languages accepted by $SLR(1)$ parsers

Does this logic hold for higher $k$'s? That is, does following fact hold?

Point 2: Set of languages accepted by $LR(k)$ parsers $\subset$ Set of languages accepted by $SLR(k+1)$ parsers, for $k=1,2,...$

Also I have just came across the fact that every $LR(k)$ language is parseable by $LR(1)$ parser. So, I guess, point 2 seems trivial for $k>2$ and all we need to prove is:

Whether $LR(1)\subset SLR(2)$ ?

Is it so?

PS: I have not read this paper and dont know if it is related, but linking it anyway: SLR(k) covering for LR(k) grammars

$\endgroup$

marked as duplicate by rici, Evil, Discrete lizard Jun 29 at 19:24

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ In the proposed duplicate (a FAQ), see LR in the second half, which deals with languages: $LR(0) \subset SLR(1) = LALR(1) = LR(1) = SLR(k) = LALR(k) = LR(k) = LR$ $\endgroup$ – rici Jun 29 at 15:32
  • $\begingroup$ First of all super thanks to point me to an excellent post. The point you stated in above comment seems to be in the context of languages & I was asking in the context of grammar. The linked post does not say anything about comparing $LR(k)$ & $SLR(k+1)$ for $k>=1$ for grammars. Also it states $LR(0)⊂LR(1)⊂LR(2)⊂⋯⊂LR(k)$ for grammars and your earlier answer says for every $LR(k)$ ($k>1$) grammar there is equivalent $LR(1)$ grammar. Doesn't these two statements somewhat contradict each other? I guess am misinterpreting something. But exactly what? $\endgroup$ – anir Jun 29 at 20:36
  • 1
    $\begingroup$ 1. Everything in your question refers to languages. 2. I don't believe there is a containment relationship between $LR(k)$ and $SLR(k+1)$ grammars. There are $LR(k)$ grammars which are not $SLR(j)$ for any $j$. 3. There is no contradiction. A grammar is not the same as another grammar, even if they recognise the same language, and even if one has been mechanically transformed into the other. Two grammars are the same only if their individual components are identical (sets of symbols, productions, start symbol). $\endgroup$ – rici Jun 29 at 23:34
  • 1
    $\begingroup$ So what I said in the other answers is that for every $LR(k)$ grammar, you can produce an $LR(1)$ grammar which recognises the same language, and moreover any derivation priduced by one of the grammars can be mechanically transformed into the derivation which would be produced by the other. That means they are equivalent. But they're still not equal. $\endgroup$ – rici Jun 29 at 23:43
  • $\begingroup$ (1) Does "$LR(1)\subset LR(k)$" mean "set of languages accepted by $LR(1)$ grammars is subset of set of languages accepted by $LR(k)$" grammars? (2) If for every $LR(k)$ grammar, there is equivalent $LR(1)$ grammar, then doesnt that mean set of languages accepted by $LR(k)$ grammars is same as set of languages accepted by $LR(1)$ grammars? (3) If (1) and (2) are correct, dont they contradict each other? Where I am making mistake? 😔 $\endgroup$ – anir Jun 30 at 7:52