4 ms·
Er, no, they don't. Detecting ambiguities is undecidable [1] -- LALR and LR parsers don't tell you about ambiguities. They only tell you about shift and reduce
by wfunction 12y ago
Er, no, they don't. Detecting ambiguities is undecidable [1] -- LALR and LR parsers don't tell you about ambiguities. They only tell you about shift and reduce conflicts. Those do not necessarily imply the existence of ambiguities.
[1] https://en.wikipedia.org/wiki/Ambiguous_grammar#Recognizing_ambiguous_grammars https://en.wikipedia.org/wiki/Ambiguous_grammar#Recognizing_...
- tomp 12y agoIt's undecidable for context-free grammars, but LR grammars are a deterministic subset of context-free grammars. If I understand "deterministic" correctly, it implies unambiguous.
- wfunction 12y agoNo, conflicts in LR grammars imply nothing about the ambiguity of the grammar. Only the absence of conflicts implies the grammar is unambiguous. Remember that ambiguity only refers to whether or not there can be multiple derivations for the same string, not whether the parser action is ambiguous. For example, consider: S: "a" "b" "c" | A "b" "d" A: "a" This LR(1) grammar has a shift/reduce conflict, but it is unambiguous. You could even make it worse by: S: "a" B "c" | A B "d" A: "a" B: "b" | B "b" in which interpreting this as an LR(k) grammar for all k < ∞ results in conflicts even though the grammar is still unambiguous.