Ambiguity

Property of a string or a grammar.

Ambiguous String

A string is ambiguous iff it has more than one derivation tree.

Unambiguous Grammar

A grammar is unambiguous iff every string has exactly one derivation tree.

Example: $S → aSb\;|\;ab$

Ambiguous Grammar

A grammar $G$ is ambiguous iff its not unambiguous (i.e. there exists a string in $L(G)$ with multiple derivation trees). Ambiguity often arises due to operator precedence and associativity.

Some ambiguous grammars can be rewritten as an equivalent unambiguous grammar.

Associativity

Associativity defines how operators of the same precedence are grouped.

Left Associative

Grouping from left to right.

Right Associative

Grouping from right to left.

Precedence

Defines order of evaluation. For example, multiplication has higher precedence than addition.

When precedence is equal, associativity resolves ambiguity.

Examples:

• Left associative
  $5 − 3 − 2 = (5 − 3) − 2$

• Right associative
  4^3^2 = $4^{3^2}$

Examples

Grammar of arithmetic

$S → S+S\;|\;S-S\;|\;S*S\;|\;S/S\;|\;(S)\;|\;a$ is ambiguous because $a + a - a$ has 2 possible leftmost derivations.

The above grammar can be made unambiguous, using precedence + associativity:

• $S → S + T | T$
• $T → T * F | F$
• $F → (S) | a$

Precedence is defined for $*$ and $+$ using $S$, $T$ and $F$.

Dangling Else

Consider the grammar:

<stmt> →
    if (<expr>) <stmt>
  | if (<expr>) <stmt> else <stmt>
  | <other_stmt>

Example statement:

if (expr1) if (expr2) f(); else g();

Two interpretations:

if (expr1) {
    if (expr2) f();
}
else g();

if (expr1) {
    if (expr2) f();
    else g();
}

Programming languages usually adopt rule “else associates with the closest if.”