3 ms·
One thing I really like about LALR and LR parsers is that they warn you about all ambiguities. IMO that's one of the most useful things when designing a syntax.
by tomp 12y ago
One thing I really like about LALR and LR parsers is that they warn you about all ambiguities. IMO that's one of the most useful things when designing a syntax.
People (and Wikipedia) like to pretend that e.g. PEG grammars cannot be ambiguous, because the PEG "choice" operator is ordered. In reality, that doesn't make them unambiguous, it just hides the ambiguity. By the same logic, you could say that LR grammars cannot be ambiguous either; the parser generator will always produce a working parser. The difference is, LR parser generators warn you about the parts of the grammar where the generator had to make a choice (and their choices are well-documented and not arbitrary), while PEG parsers don't.
- wfunction 12y agoEr, 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.