# Connection between non determinism and LL(1) conflicts

I am trying to understand connection between non determinism of grammar and LL(1) conflicts introduced by it.

As per my understanding non deterministic context free grammar is a context free grammar in which at some point in time during parsing, multiple actions are allowed. Also I believe non determinism occurs when we have multiple productions in grammar with same prefix of production (right hand side) bodies. Also I know we eliminate non determinism by left factoring grammar.

Wikipedia article says:

1. We do left factoring to eliminate FIRST-FIRST conflicts. ref
2. Left recursion is a special case of FIRST-FIRST conflict. ref
3. Substitution is used for removing FIRST-FOLLOW conflict. However that may introduce FIRST-FIRST conflict.ref
4. Left recursion is eliminated using rule like below ref :
$$A\rightarrow A\alpha | \beta$$
ios converted to
$$A\rightarrow \beta A'$$
$$A'\rightarrow \alpha A' | \epsilon$$

I have following doubts:

1. Since both non determinism and FIRST-FIRST conflicts are removed with left factoring and since left recursion is special case of FIRST-FIRST conflict, is non determinism a reason behind FIRST-FIRST conflict and left recursion (and also for FIRST-FOLLOW conflict)? If yes, does non determinism cause anything else and there is nothing else apart from these three (FIRST-FIRST conflict, left recursion and FIRST-FOLLOW conflict) in which non determinism manifests?

2. Does the solutions (left factoring, substitution and left recursion removal rule) for removing above can also remove non determinism from all grammars?

3. I know LL grammar should be both non deterministic and unambiguous. Does ambiguity also manifests in some way in LL parsing table or grammar? I read ambiguity can be eliminated by enforcing association and precedence between grammar symbols and this resolves SHIFT-REDUCE conflicts in LR parsers. Is anything like this required for eliminating ambiguity to make grammar a valid LL grammar?

• "Does the solutions (left factoring, substitution and left recursion removal rule) for removing above can also remove non determinism from all grammars?" First, some languages are inherently non-deterministic. Whatever grammar is used to generated one of such languages, it will be non-deterministic grammar. (I am speaking loosely as non-determinism can have in-equivalent definitions.) Second, it is far from clear whether a grammar that generate a deterministic language can be transformed to a deterministic grammar by those three operations. – Apass.Jack Jun 9 at 18:59

2. Some deterministic grammars -- and even some deterministic context-free languages -- have no $$LL$$ parser. Such grammars are not necessarily ambiguous. An accurate deterministic parser obviously cannot be generated for an ambiguous grammar, but failure to generate a parser doesn't say anything about ambiguity.
• @anir: you're right; that was a mistake. If a CFG is deterministic then there is some $k$ for which an $LR(k)$ parser exists. The problem is that there is no way to find such a $k$ other than trying all of them. So if we run the LR algorithm with some value of $k$ and find a conflict, we don't know that the grammar is non-deterministic. It might be that we just need a larger $k$. – rici Jun 16 at 19:52