13 ms·

It's undecidable for context-free grammars, but LR grammars are a deterministic subset of context-free grammars. If I understand "deterministic" correctly, it i

• wfunction 12y ago
  No, 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.