Editing Ambiguous grammar (section)

== Recognizing ambiguous grammars ==
The [[decision problem]] of whether an arbitrary grammar is ambiguous is [[Undecidable problem|undecidable]] because it can be shown that it is equivalent to the [[Post correspondence problem]].{{sfn|Hopcroft|Motwani|Ullman|2006|loc=Theorem 9.20|p=415}} At least, there are tools implementing some [[semi-decidable|semi-decision procedure]] for detecting ambiguity of context-free grammars.<ref>{{cite conference | last1 = Axelsson | first1 = Roland | last2 = Heljanko | first2 = Keijo | last3 = Lange | first3 = Martin | year = 2008 | title = Analyzing Context-Free Grammars Using an Incremental SAT Solver | book-title = Proceedings of the 35th [[International Colloquium on Automata, Languages and Programming]] (ICALP'08), Reykjavik, Iceland | series = [[Lecture Notes in Computer Science]] | volume = 5126 | pages = 410–422 | publisher = Springer-Verlag | doi = 10.1007/978-3-540-70583-3_34 | isbn = 978-3-540-70582-6 | url = http://www.tcs.hut.fi/~kepa/publications/AxelssonHeljankoLange-ICALP08.pdf }}</ref>

The efficiency of parsing a context-free grammar is determined by the automaton that accepts it. [[Deterministic context-free grammar]]s are accepted by [[deterministic pushdown automata]] and can be parsed in linear time, for example by an [[LR parser]].<ref>{{Cite journal | last1 = Knuth | first1 = D. E. | authorlink = Donald Knuth | title = On the translation of languages from left to right | doi = 10.1016/S0019-9958(65)90426-2 | journal = Information and Control | volume = 8 | issue = 6 | pages = 607–639 | date = July 1965 | doi-access =  }}</ref> They are a strict subset of the [[context-free grammars]], which are accepted by [[pushdown automata]] and can be parsed in polynomial time, for example by the [[CYK algorithm]]. 

Unambiguous context-free grammars can be nondeterministic. For example, the language of even-length [[palindrome]]s on the alphabet of 0 and 1 has the unambiguous context-free grammar S → 0S0 | 1S1 | ε.  An arbitrary string of this language cannot be parsed without reading all its symbols first, which means that a pushdown automaton has to try alternative state transitions to accommodate for the different possible lengths of a semi-parsed string.{{sfn|Hopcroft|Motwani|Ullman|2006|pp=254-6}}

Nevertheless, removing grammar ambiguity may produce a deterministic context-free grammar and thus allow for more efficient parsing. Compiler generators such as [[YACC]] include features for resolving some kinds of ambiguity, such as by using the precedence and associativity constraints.