patternMinor
Connection between non determinism and LL(1) conflicts
Viewed 0 times
nonbetweenandconflictsdeterminismconnection
Problem
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:
$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?
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?
Solution
-
No algorithm can remove non-determinism (or ambiguity) from every grammar, not even for every grammar for a language which has a deterministic grammar.
-
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.
-
Yacc-style precedence/associativity declarations do not, in general, solve grammar ambiguity. But they do work for a couple of common simple cases (operator precedence, dangling else) allowing for the use of simpler grammars. That's handy in practice, but it's a very limited technique.
No algorithm can remove non-determinism (or ambiguity) from every grammar, not even for every grammar for a language which has a deterministic grammar.
-
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.
-
Yacc-style precedence/associativity declarations do not, in general, solve grammar ambiguity. But they do work for a couple of common simple cases (operator precedence, dangling else) allowing for the use of simpler grammars. That's handy in practice, but it's a very limited technique.
Context
StackExchange Computer Science Q#110397, answer score: 3
Revisions (0)
No revisions yet.