0
$\begingroup$

I am studying CLR Parser and have a query about Grammar. If a Grammar can't be parsed using CLR(1) Parser ( i.e LR(1)) parser is it necessarily ambiguous?

Is it possible that a grammar which is unambiguous can't be parsed using CLR Parser?

|cite|improve this question
$\endgroup$
2
$\begingroup$

A grammar may be may unambiguous, but not parsable by a LR(k) parser. It is actually possible that a language has an unambiguous grammar, but cannot be parsed deterministically by any PDA, hence has no LR(k) parser.

For example the language $\{a^nb^n\mid n>0\}\cup\{a^nb^{2n}\mid n>0\}$. It is clearly unambiguous (it is easy to write an unambiguous grammar for it). But, informally, there is just no way you can decide which way you want to parse before you have read all the $a$ and as many $b$.

An ambiguous grammar may define a language that has another grammar that is not ambiguous, and may even be CLR(1) or LR(0). Actually, you can just take an LR(0) grammar and add a few useless rule to make it ambiguous without changing the language.

However, there are context-free languages that are inherently ambiguous, i.e. that can only be defined by an ambiguous grammar. And of course, there is no way an inherently ambiguous language can be parsed deterministically.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanx.. i get a better picture of it now :) $\endgroup$ – Ana Dec 20 '14 at 14:34
1
$\begingroup$

I found the answer. A Grammar if not CLR(1) may be unambiguous... but if a grammar is ambiguous cant be CLR(1) grammar. For details you can consider this paper from stanford.

|cite|improve this answer
$\endgroup$

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.