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:
- We do left factoring to eliminate FIRST-FIRST conflicts. ref
- Left recursion is a special case of FIRST-FIRST conflict. ref
- Substitution is used for removing FIRST-FOLLOW conflict. However that may introduce FIRST-FIRST conflict.ref
- 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:
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?
Does the solutions (left factoring, substitution and left recursion removal rule) for removing above can also remove non determinism from all grammars?
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?