why there will be ambiguous grammar?

[ethanph]

hi, all
I know what's the ambiguous grammar, but i am not clear why there will be ambiguous grammar? in other words, what's the essential reason that leading the ambiguous grammar?

thanks!

[CalmLogic]

I don't know if this answers your question, but here is a practical example:

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.

Ambiguous grammar - Wikipedia, the free encyclopedia

[grabanca]

An ambiguous grammar is a grammar that generates a language L and there exist one word w in L such that there are 2 or more different possible parsings for it.

For example

S-> SS | 0

is ambiguous. The string 000 is part of the generated language and can be parsed 2 different ways:
1. S->SS -> 0 S -> 0 S S-> 0 0 S -> 0 0 0
2. S->SS -> SS S -> 0 S S-> 0 0 S -> 0 0 0

[ethanph]

i know this, but actually I'd like to ask how to determine one grammar is an ambiguoius grammar, such like your example, S-> SS|0 the only method is just to illustrate an example? if the grammar is very complicated, then maybe we can not obtain an example soon

[iamdaisy]

Recognizing an ambiguous grammar

The general question of whether a grammar is ambiguous is undecidable. No algorithm can exist to determine the ambiguity of a grammar because if so, the undecidable halting problem could be encoded as an ambiguity problem.

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^nb^mc^md^n | n,m > 0} with {a^nb^nc^md^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^nb^nc^nd^n | n > 0} which is the intersection of the two languages.


frm WIKI