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?

  • $\begingroup$ Is this homework? $\endgroup$
    – Marcin
    Jan 18 '12 at 18:26
  • $\begingroup$ no its not, i am not even in school i was having a discussion with my friend and this question came up :) $\endgroup$
    – Mike G
    Jan 18 '12 at 18:31
  • 3
    $\begingroup$ I'm rather surprised this question got moved to cstheory. The faq says "research-level" questions. $\endgroup$
    – ccoakley
    Jan 18 '12 at 21:54
  • 2
    $\begingroup$ 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. $\endgroup$ Jan 19 '12 at 1:29

You can mechanically transform an LR(k) grammar into an LR(1) grammar (source)

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).

  • $\begingroup$ I think you have misread the question, i was asking if we have a grammar that is not LL nor LR parsable lets call it A can we have another grammar that is parsable by LR(1) and the Language of that LR grammar is the same as the language of grammar A $\endgroup$
    – Mike G
    Jan 18 '12 at 18:30
  • 1
    $\begingroup$ @MikeG: I've tried to clarify. If A happens to be a Context-Sensitve grammar for a language that requires an LBA, then no LR grammar exists for that language. If A happens to be a Context-Sensitive grammar for a language that is actually a simpler language, then an equivalent LR grammar can exist. So you have a set of grammars that can be simplified and a set of grammars that cannot. Or, you have a set of languages that can be recognized by LR grammars (and permit grammars that are more complex than LR) and a set that cannot. $\endgroup$
    – ccoakley
    Jan 18 '12 at 18:41

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.

  • $\begingroup$ "$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$. $\endgroup$
    – Sylvain
    Nov 10 '13 at 14:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.