Ambiguous Grammar

In computer science, an ambiguous grammar is a formal grammar that can spawn a string in more than one way (that is, there is more than one parse tree for a string). A language is called essentially ambiguous if it can be generated only by ambiguous grammars.

The grammars of some programming languages are ambiguous. When parsing such languages, it is necessary to take into account semantic information in order to select the correct variant. For example, in C, the following entry:

  x * y;

can be interpreted as either:

declaring an identifier y type pointer -to- x , or
an expression in which x is multiplied by y and the result is ignored.

To choose between these interpretations, the compiler must consult its character table to find out if the declaration x was a typedef name in a given scope.

Example

Contextually Free Grammar

A → A + A | A - A | a

is ambiguous, as there are two left-sided outputs for line a + a + a:

A	→ A + A	A	→ A + A
	→ a + A		→ A + A + A
	→ a + A + A		→ a + A + A
	→ a + a + A		→ a + a + A
	→ a + a + a		→ a + a + a

Also, the grammar is ambiguous because there are two parsing trees for the string a + a - a:

However, the language that it spawns is not significantly ambiguous, since the following unambiguous grammar generates the same language:

A → A + a | A - a | a

Recognizing Ambiguous Grammar

The general task of determining whether a grammar is ambiguous is algorithmically unsolvable . There cannot be an algorithm that determines the ambiguity of the grammar, since the unsolvable problem of Post correspondence reduces to the ambiguity problem.

There is an obvious difficulty in parsing an ambiguous grammar by a deterministic analyzer , but non-deterministic analysis leads to a significant loss in efficiency. Most constructs requiring parsing can be recognized by unambiguous grammars. Some ambiguous grammars can be converted into unambiguous ones, but there is no general procedure for this transformation, just as there is no algorithm for determining the ambiguity of a grammar. Compiler generators, such as YACC , are capable of resolving some kinds of ambiguities, for example, by using priority and associativity constraints.

Substantially ambiguous languages

While some languages (the sets of strings generated by a grammar) have both unambiguous and ambiguous grammars, there are languages for which there is no unambiguous grammar. An example of a substantially ambiguous language is the union $\{a^{n}b^{m}c^{m}d^{n}|n,m>0\}$ ${\ displaystyle \ {a ^ {n} b ^ {m} c ^ {m} d ^ {n} | n, m> 0 \}}$ and $\{a^{n}b^{n}c^{m}d^{m}|n,m>0\}$ ${\ displaystyle \ {a ^ {n} b ^ {n} c ^ {m} d ^ {m} | n, m> 0 \}}$ . This is a context-free language as a union of context-free languages, but the Introduction to the theory of automata ... contains evidence that it is not possible to unambiguously parse strings in a (not context-free) subset $\{a^{n}b^{n}c^{n}d^{n}|n>0\}$ ${\ displaystyle \ {a ^ {n} b ^ {n} c ^ {n} d ^ {n} | n> 0 \}}$ being the intersection of these two languages.

Ambiguous Grammar

Example

Recognizing Ambiguous Grammar

Substantially ambiguous languages

More articles: