<p>You can mechanically transform an LR(k) grammar into an LR(1) grammar (<a href="http://en.wikipedia.org/wiki/LR_parser" rel="nofollow">source</a>)</p>

<p>This is not true for LR(*) grammars (k=inf). However, that statement doesn't mean that there isn't such a grammar for the same language. You might just need to rewrite the grammar.</p>

<p>Grammars exist that cannot be transformed, however. Languages for Context-Sensitive grammars can be more expressive than context-free grammars (can only be recognized by linear-bounded automata). Therefore, your hoped-for translation is possible for just a subset.</p>

<p>Update for clarification:</p>

<p>There are languages that can not be represented by LR grammars but do have a grammar that is not LR (the language requires something more powerful than LR). There are also grammars that are not LR that recognize a language that can be recognized by an LR grammar (the language just happens to have a complex grammar, but it is not required).</p>

CC BY-SA 3.0
2012-01-18T18:24:26.220Z
2012-01-18T18:39:52.647Z
ccoakley
<p>Explanation 1: if you know which $k$ it shall be, you can <em>easily</em> check if the grammar is $LR(k)$ and thus derive an $LR(1)$ Grammar for it. On the other hand you cannot even know if there is a $k \geq 0$ such that $G$ is $LR(k)$. </p>

<p>Different with "Yes and No": </p>

<p>Yes: $L(G_1)$ is deterministic, then it is immediately $LR(k)$ and thus $LR(1)$.
No: $L(G_1)$ is not deterministic. This means the language itself is inherently ambiguous  this in turn means that there is no Grammar $G_n$ which is not ambiguous. </p>

<p>Much more and much more detailed (and quite understandable, far better than I am able right now) can be found in the following two works. The second contains (iirc) the proof that $LL(k)$ is a (theoretically) weaker than $LR(k)$.</p>

<p>Knuth, D. E. (1965). <em>On the translation of languages from left to right</em>. </p>

<p>D. J. Rosenkrantz and R. E. Stearns. 1969. <em>Properties of deterministic top down grammars</em>. </p>

CC BY-SA 3.0
2013-11-10T14:48:30.153Z
"$L(G_1)$ is not deterministic.  This means the language itself is inherently ambiguous."  No, there exist non-deterministic languages that are not ambiguous; for instance $\{ww^R\mid w\in\{a,b\}^*\}$ the set of even-length palindromes is generated by the unambiguous grammar $S\to aSa\mid bSb\mid\varepsilon$.
Sylvain
CC BY-SA 3.0
2013-11-06T15:41:51.590Z
2013-11-06T15:41:51.590Z
jf2011
<p>If L(G1) is the language that is produced by grammar G1 and G1 is not LR(k) parsable (specifically speaking for k = 1). Does there exist a grammar Gx that is L(Gx) = L(G1) where Gx is LR(1) parsable ? If that is possible can it be generalized to all possible languages or just a subset?</p>

CC BY-SA 3.0
2012-01-18T18:26:45.757Z
Is this homework?
Marcin
CC BY-SA 3.0
2012-01-18T21:54:20.980Z
I'm rather surprised this question got moved to cstheory. The faq says "research-level" questions.
ccoakley
CC BY-SA 3.0
2012-01-19T01:29:42.430Z
One of the things you nearly always learn when you get taught the concept of languages and grammars is how to remove left-recursion from certain context-free grammars to make them LL(1), thus giving an example of a grammar that is not LL(1) but describes an LL(1) language. This is a big hint the same thing is probably true for LR(1). As another example, consider this language: S := S S, S := a. This *language* is simply the regular language 'a a+', but as the *grammar* is ambiguous it is not LR(k) for any k. I therefore think the migration was not warranted: this is far from research-level.
Alex ten Brink
<compilers>
Can any language be modeled as LR(k)
Mike G
# Can any language be modeled as LR(k)

(Asked by: username_0 on 2012-01-18)

If L(G1) is the language that is produced by grammar G1 and G1 is not LR(k) parsable (specifically speaking for k = 1). Does there exist a grammar Gx that is L(Gx) = L(G1) where Gx is LR(1) parsable ? If that is possible can it be generalized to all possible languages or just a subset?

**Tags:** compilers
> **Comments:**
> **username_1**: Is this homework?  
> **username_2**: I'm rather surprised this question got moved to cstheory. The faq says "research-level" questions.  
> **username_3**: One of the things you nearly always learn when you get taught the concept of languages and grammars is how to remove left-recursion from certain context-free grammars to make them LL(1), thus giving an example of a grammar that is not LL(1) but describes an LL(1) language. This is a big hint the same thing is probably true for LR(1). As another example, consider this language: S := S S, S := a. This *language* is simply the regular language 'a a+', but as the *grammar* is ambiguous it is not LR(k) for any k. I therefore think the migration was not warranted: this is far from research-level.  

---

## 2 answers

### Answer by username_2 on 2012-01-18. Score: 1

You can mechanically transform an LR(k) grammar into an LR(1) grammar ([source](http://en.wikipedia.org/wiki/LR_parser))

This is not true for LR(\*) grammars (k=inf). However, that statement doesn't mean that there isn't such a grammar for the same language. You might just need to rewrite the grammar.

Grammars exist that cannot be transformed, however. Languages for Context-Sensitive grammars can be more expressive than context-free grammars (can only be recognized by linear-bounded automata). Therefore, your hoped-for translation is possible for just a subset.

Update for clarification:

There are languages that can not be represented by LR grammars but do have a grammar that is not LR (the language requires something more powerful than LR). There are also grammars that are not LR that recognize a language that can be recognized by an LR grammar (the language just happens to have a complex grammar, but it is not required).


---

### Answer by username_4 on 2013-11-06. Score: 0

Explanation 1: if you know which $k$ it shall be, you can *easily* check if the grammar is $LR(k)$ and thus derive an $LR(1)$ Grammar for it. On the other hand you cannot even know if there is a $k \geq 0$ such that $G$ is $LR(k)$.

Different with "Yes and No":

Yes: $L(G\_1)$ is deterministic, then it is immediately $LR(k)$ and thus $LR(1)$.
No: $L(G\_1)$ is not deterministic. This means the language itself is inherently ambiguous this in turn means that there is no Grammar $G\_n$ which is not ambiguous.

Much more and much more detailed (and quite understandable, far better than I am able right now) can be found in the following two works. The second contains (iirc) the proof that $LL(k)$ is a (theoretically) weaker than $LR(k)$.

Knuth, D. E. (1965). *On the translation of languages from left to right*.

D. J. Rosenkrantz and R. E. Stearns. 1969. *Properties of deterministic top down grammars*.

> **Comments:**
> **username_5**: "$L(G_1)$ is not deterministic.  This means the language itself is inherently ambiguous."  No, there exist non-deterministic languages that are not ambiguous; for instance $\{ww^R\mid w\in\{a,b\}^*\}$ the set of even-length palindromes is generated by the unambiguous grammar $S\to aSa\mid bSb\mid\varepsilon$.  

---

