Ambiguous Grammar - Recognizing Ambiguous Grammars

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:

    There’s only one way for an individual to remain upright, not to fall to pieces, not to sink into the mire of self-oblivion ... or self-contempt. That’s calmly to turn away from everything, to say, “Enough!” and, folding one’s useless arms across one’s empty breast, to retain the ultimate, the sole attainable virtue, the virtue of recognizing one’s own insignificance.
    Ivan Sergeevich Turgenev (1818–1883)

    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)

    The violent illiteracies of the graffiti, the clenched silence of the adolescent, the nonsense cries from the stage-happening, are resolutely strategic. The insurgent and the freak-out have broken off discourse with a cultural system which they despise as a cruel, antiquated fraud. They will not bandy words with it. Accept, even momentarily, the conventions of literate linguistic exchange, and you are caught in the net of the old values, of the grammars that can condescend or enslave.
    George Steiner (b. 1929)