0
$\begingroup$

There is no algorithm that, given an arbitrary grammar, decides if it's ambiguous or not. However, Are there any sufficient conditions that make it easier to tell that a grammar is unambiguous?

For example, if I'm not mistaken, it can be algorithmically checked if a grammar contains no conflicts under LR(1), LALR(1) or LL(1); if so, is there any implication like "If the grammar has no conflicts under LL(1) then it is unambiguous" or something like that?

$\endgroup$
2
$\begingroup$

If you can construct a deterministic parser corresponding to a grammar, then the grammar is clearly the unambiguous. (If it were ambiguous, there would need to be a point in some parse which admitted more than one parse action, violating the presumption of determinism.)

All of the algorithms you mention for constructing a parser either produce a deterministic parser for a grammar or report conflicts. So the absence of conflicts implies unambiguity.

Note that there might exist parsing algorithms which produce parsers which do not precisely correspond to the grammar. For example, yacc/bison use an algorithm which resolves conflicts, either using precedence declarations or through some default resolution rules. The resulting parser is then unambiguous, but it is no longer capable of producing the same set of derivations as the original grammar. Indeed, it might not even be able to recognise the same sentences.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.