Ambiguous grammar

Ambiguous grammar

In computer science, a grammar is said to be an ambiguous grammar if there is some string that it can generate in more than one way (i.e., the string has more than one parse tree or more than one leftmost derivation). A language is inherently ambiguous if it can only be generated by ambiguous grammars.

Some programming languages have ambiguous grammars; in this case, semantic information is needed to select the intended parse of an ambiguous construct. For example, in C the following:

x * y ;

can be interpreted either as the declaration of an identifier y of type pointer to x, or as an expression in which x is multiplied by y and the result is discarded. To choose between the two possible interpretations, a compiler must consult its symbol table to find out whether x has been declared as a typedef name that is visible at this point.

Example

The context free grammar:A → A + A | A − A | ais ambiguous since there are two leftmost derivations for the string a + a + a:

As another example, the grammar is ambiguous since there are two parse trees for the string a + a − a::

The language that it generates, however, is not inherently ambiguous; the following is a non-ambiguous grammar generating the same language::A → A + a | A − a | a

Recognizing an ambiguous grammar

The general question of whether a grammar is not ambiguous is undecidable. No algorithm can exist to determine the ambiguity of a grammar because the undecidable Post correspondence problem can be encoded as an ambiguity problem.

There is an obvious difficulty in parsing an ambiguous grammar by a deterministic parser (see deterministic context-free grammar) but nondeterministic parsing imposes a great efficiency penalty. Most constructs of interest to parsing can be recognized by unambiguous grammars. Some ambiguous grammars can be converted into unambiguous grammars, but no general procedure for doing this is possible just as no algorithm exists for detecting ambiguous grammars. Compiler generators such as YACC include features for disambiguating some kinds of ambiguity, such as by using the precedence and associativity constraints.

Inherently ambiguous languages

While some languages (the set of strings that can be generated by a grammar) have both ambiguous and unambiguous grammars, there exist languages for which no unambiguous grammar can exist. An example of an inherently ambiguous language is the union of {a^n b^m c^m d^n | n, m > 0} with {a^n b^n c^m d^m | n, m > 0}. This is context-free, since it is a union of context-free languages, but "Introduction to Automata Theory..." contains a proof that there is no way to unambiguously parse strings in the (non-context-free) subset {a^n b^n c^n d^n | n > 0} which is the intersection of the two languages.

External links

* [http://www.brics.dk/grammar dk.brics.grammar - a grammar ambiguity analyzer]

References

*"Programming Languages: Design and Implementation", T. Pratt, M. Zelkowitz. Prentice Hall, 2001
*"Introduction to Automata Theory, Languages and Computation." Hopcroft, Motwani, Ullman. Addison Wesley. 2001
* [http://www.inf.unibz.it/~artale/Compiler/slide4.pdf "Lecture slides about generating parsing tables"] , by Professor Alessandro Artale, researcher and lecturer at the Free University of Bolzano (from page 11).


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Grammar — is the field of linguistics that covers the rules governing the use of any given natural language. It includes morphology and syntax, often complemented by phonetics, phonology, semantics, and pragmatics. Each language has its own distinct… …   Wikipedia

  • Context-free grammar — In formal language theory, a context free grammar (CFG) is a formal grammar in which every production rule is of the form V → w where V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals (w can be empty). The… …   Wikipedia

  • Formal grammar — In formal semantics, computer science and linguistics, a formal grammar (also called formation rules) is a precise description of a formal language ndash; that is, of a set of strings over some alphabet. In other words, a grammar describes which… …   Wikipedia

  • Stochastic context-free grammar — A stochastic context free grammar (SCFG; also probabilistic context free grammar, PCFG) is a context free grammar in which each production is augmented with a probability. The probability of a derivation (parse) is then the product of the… …   Wikipedia

  • HEBREW GRAMMAR — The following entry is divided into two sections: an Introduction for the non specialist and (II) a detailed survey. [i] HEBREW GRAMMAR: AN INTRODUCTION There are four main phases in the history of the Hebrew language: the biblical or classical,… …   Encyclopedia of Judaism

  • Parsing expression grammar — A parsing expression grammar, or PEG, is a type of analytic formal grammar that describes a formal language in terms of a set of rules for recognizing strings in the language. A parsing expression grammar essentially represents a recursive… …   Wikipedia

  • Hungarian grammar — Hungarian language Closeup view of a Hungarian keybo …   Wikipedia

  • Esperanto grammar — Esperanto is a constructed auxiliary language. A highly regular grammar makes Esperanto much easier to learn than most other languages of the world, though particular features may be more or less advantageous or difficult depending on the… …   Wikipedia

  • Japanese grammar — The Japanese language has a highly regular agglutinative verb morphology, with both productive and fixed elements. Typologically, its most prominent feature is topic creation: Japanese has prominent topics (although it is possible for topics and… …   Wikipedia

  • All Saints Greek Orthodox Grammar School — Infobox Aust school private name = All Saints Greek Orthodox Grammar School motto = ΣΤΩΜΕΝ ΚΑΛΩΣ Let us stand well established = 1990 type = Independent, Co educational, Day school denomination = Christian Orthodox slogan = key people = Mr.… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”