Definition: Ambiguous and Unambiguous Grammars

A grammar $G$ is called ambiguous if there is a string $\omega$ in the language generated from the grammar $L(G)$ such that it has at least two different abstract syntax trees $\operatorname{AST}_G(\omega)\neq \operatorname{AST}^\prime_G(\omega).$

If for all $\omega\in L(G)$ there are unique abstract syntax trees $\operatorname{AST}_G(\omega),$ the grammar is called unambiguous.

Examples: 1


Thank you to the contributors under CC BY-SA 4.0!

Github:
bookofproofs


References

Bibliography

  1. Erk, Katrin; Priese, Lutz: "Theoretische Informatik", Springer Verlag, 2000, 2nd Edition
  2. Hoffmann, Dirk: "Theoretische Informatik, 3. Auflage", Hanser, 2015