Recognizing Ambiguous Grammars
The general decision problem of whether a grammar is ambiguous is undecidable because it can be shown that it is equivalent to the Post correspondence problem. At least, there are tools implementing some semi-decision procedure for detecting ambiguity of context-free grammars.
The efficiency of context-free grammar parsing is determined by by the automaton that accepts it. Deterministic context-free grammars are accepted by deterministic pushdown automata and can be parsed in linear time, for example by the LR parser. This is a subset of the context-free grammars which are accepted by the pushdown automaton and can by parsed in polynomial time, for example by the CYK algorithm. Unambiguous context-free grammars can be nondeterministic. For example, the language of even-length palindromes 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 letters first which means that a pushdown automaton has to try alternative state transisions to accommodate for the different possible lengths of a semi-parsed string. 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.
Read more about this topic: Ambiguous Grammar
Famous quotes containing the words recognizing, ambiguous and/or grammars:
“A radical is one of whom people say “He goes too far.” A conservative, on the other hand, is one who “doesn’t go far enough.” Then there is the reactionary, “one who doesn’t go at all.” All these terms are more or less objectionable, wherefore we have coined the term “progressive.” I should say that a progressive is one who insists upon recognizing new facts as they present themselves—one who adjusts legislation to these new facts.”
—Woodrow Wilson (1856–1924)
“The whole of natural theology ... resolves itself into one simple, though somewhat ambiguous proposition, That the cause or causes of order in the universe probably bear some remote analogy to human intelligence.”
—David Hume (1711–1776)
“A sure proportion of rogue and dunce finds its way into every school and requires a cruel share of time, and the gentle teacher, who wished to be a Providence to youth, is grown a martinet, sore with suspicions; knows as much vice as the judge of a police court, and his love of learning is lost in the routine of grammars and books of elements.”
—Ralph Waldo Emerson (1803–1882)