Unambiguousness and determinism of CFGs for them to be LR

Question

I came across this statement:

Note that there are unambiguous grammars for which every LR parser construction method will produce a parsing action table with parsing action conflicts.

I was guessing what could be the characteristics of such grammars?

Then I came across this question which very well asks:

Why does there exist a conflict even though it is not ambiguous grammar?

The answer does not give straight answer to above "Why". But definitely says this:

A context-free language is LR(k) precisely if it is deterministic.

In this context, I have following guessings which I want confirmations for:

1. All LR grammars are unambiguous, merely because they need to be deterministic and set of deterministic languages is proper subset of unambiguous languages.
2. In other words, unambiguous languages which are non LR are those which are non deterministic.
3. Dragon book says we can enforce association and precedence to ensure unambiguousness of grammar by resolving conflicts. I also read that we do left factoring to convert non deterministic grammar to deterministic grammar.
   I am quite confused about what actually converts non LR grammar to LR after considering above two sentences and point 2. Is it enforcing association and/or precedence or left factoring. I feel it should be left factoring given determinism is absolutely necessary than unambiguousness and there must exist some ambiguous grammars which do not turn to LR by enforcing association and/or precedence. Am I correct with this? Left factoring eliminates FIRST-FIRST conflicts in LL grammar^ref. But does it help to eliminate SHIFT-REDUCE and REDUCE-REDUCE conflicts in LR grammars?

Answer 1

Your first and second points are correct, although you need to take more care distinguishing between properties of grammars and properties of languages.

A language is context free if (and only if) there exists a context free grammar for it. It is also deterministic if (and only if) there exists a deterministic context free grammar for it. That doesn't mean that all grammars for the language will be deterministic or even context-free; there are basically an infinitude of possible grammars for any language, deterministic and not, ambiguous and not, and not restricted to the smallest class in the Chomsky hierarchy.

In fact, figuring out whether a language has one of these properties is often not easy. While we can easily see which of Chomsky's classes a grammar belongs to, and we can easily determine whether or not a particular context-free grammar is, for example, $LR(k)$ for any given $k$, similar statements about languages are much harder. In particular, the following questions are undecidable, which means that no algorithm exists which will produce a correct answer for every possible input:

• Does a context-free grammar exist for a given language?

• Does an $LR(k)$ grammar exist for a given language?

• Does a deterministic grammar exist for a given language?

Some questions about grammars are also undecidable:

• Is there a $k$ for which an $LR(k)$ parser can be generated for a given grammar?

• Do two context-free grammars recognise the same language?

• Is a given context-free grammar ambiguous?

(There are many more, but these ones seemed relevant.)

Note that "undecidable" doesn't mean you can't ever figure it out. For certain languages and grammars it is quite possible to answer the above questions. But there is no algorithm which can generate a solution. Finding a solution requires luck and perseverance, and there's no guarantee you'll manage it. (This is somewhat like the problem of proving a given mathematical hypothesis.)

One of the consequences of all that undecidability is that there are no 100% reliable algorithms which can "remove ambiguity" from a grammar, make a grammar deterministic, and so on. All of the procedures recommended in the various textbooks you refer to (and internet sites) are just heuristics: they might work, but there are no guarantees. If you determine that a given grammar is not $LR(1)$, or not $LL(1)$, etc., you can try applying the various procedures mentioned, but you might not be able to find a transformation which works. And the mere fact that you didn't manage that transformation proves absolutely nothing about the language, although again there are cases in which you can prove that a given language has no deterministic grammar, or even that it has no unambiguous grammar. (Languages for which no unambiguous grammar exists are called "inherently ambiguous" and you can find examples by searching for that phrase, if you're interested.)

I understand that this may all seem unsatisfactory. I think you really want there to be some visible attribute of a grammar (or language) which you can point to and say, "because of this feature, this grammar is not $X$" (for some property $X$). But there really isn't a better characterisation of, for example, grammars which are not $LR(1)$ than "the $LR(1)$ parser generation algorithm failed to produce a parser for this language".

So, in short:

A grammar is deterministic if the $LR(k)$ parser generation algorithm works for some $k$, and non-deterministic if it doesn't work for any $k$. But you can't prove non-determinism that way, because you'd have to try all possible values of $k$ and that would literally take you forever.

Furthermore, even if a grammar is non-deterministic, it might or might not be ambiguous. There's no algorithm which can tell you that, either.

Finally, with respect to my answer which you quoted, I think it does explain why that particular grammar is non-deterministic: it's because you need to do the first reduction when you hit the middle of the sentence, but since you don't know where the middle of the sentence is until you reach the end (and the sentence could be arbitrarily long), you cannot know at which point in the input you need to do the first reduction. However, the language is certainly unambiguous: there is only one derivation which works.

(These statements are true of palindrome grammars regardless of how many symbols there are in the alphabet. But if the alphabet contains only a single symbol, then there is a different grammar which happens to be regular. In this particular case it's not hard to figure out what it is.)