title: "Ambiguity"

Ambiguity

Definition. A context-free grammar is ambiguous if some string in its language has two or more distinct parse trees, equivalently two or more distinct leftmost derivations.

Two derivations that differ only in the order variables were replaced build the same tree and do not witness ambiguity; the definition is about trees for that reason. Ambiguity is a property of the grammar, not of the language: the expression grammar $E \to E + E \mid E \times E \mid (E) \mid a$ is ambiguous, while a grammar with one variable per precedence level generates the same language unambiguously, as shown in Lecture 5. A language for which every grammar is ambiguous is called inherently ambiguous.