0
$\begingroup$

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

Improve this question
$\endgroup$
6
  • 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, 2019 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$
    – RajS
    Jun 29, 2019 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, 2019 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, 2019 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$
    – RajS
    Jun 30, 2019 at 7:52

0

Reset to default