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?
0
$\begingroup$
$\endgroup$
2
$\begingroup$
$\endgroup$
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.
1
$\begingroup$
$\endgroup$
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.
