Editing Ambiguous grammar (section)

{{Short description|Type of a context-free grammar}}
In [[computer science]], an '''ambiguous grammar''' is a [[context-free grammar]] for which there exists a [[string (computer science)|string]] that can have more than one [[leftmost derivation]] or [[parse tree]].<ref name="Levelt2008">{{cite book|author=Willem J. M. Levelt|title=An Introduction to the Theory of Formal Languages and Automata|url=https://books.google.com/books?id=tFvtwGYNe7kC&q=%22leftmost+derivation%22+%22ambiguous%22|year=2008|publisher=John Benjamins Publishing|isbn=978-90-272-3250-2}}</ref>{{sfn|Hopcroft|Motwani|Ullman|2006|p=217}} Every non-empty [[context-free language]] admits an ambiguous grammar by introducing e.g. a duplicate rule. A language that only admits ambiguous grammars is called an [[#Inherently ambiguous languages|inherently ambiguous language]]. [[Deterministic context-free grammar]]s are always unambiguous, and are an important subclass of unambiguous grammars; there are non-deterministic unambiguous grammars, however.

For computer [[programming language]]s, the reference grammar is often ambiguous, due to issues such as the [[dangling else]] problem. If present, these ambiguities are generally resolved by adding precedence rules or other [[context-sensitive grammar|context-sensitive]] parsing rules, so the overall phrase grammar is unambiguous.{{citation needed|date=January 2018}} Some parsing algorithms (such as [[Earley parser|Earley]]<ref>{{cite journal|last1=Scott|first1=Elizabeth|title=SPPF-Style Parsing From Earley Recognizers|journal=Electronic Notes in Theoretical Computer Science|date=April 1, 2008|volume=203|issue=2|pages=53–67|doi=10.1016/j.entcs.2008.03.044|doi-access=free}}</ref> or [[Generalized LR parser|GLR]] parsers) can generate sets of parse trees (or "parse forests") from strings that are [[syntactically ambiguous]].<ref>Tomita, Masaru. "[http://anthology.aclweb.org/J/J87/J87-1004.pdf An efficient augmented-context-free parsing algorithm]." Computational linguistics 13.1-2 (1987): 31-46.</ref>