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

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}$

Proving Ambiguity

To prove a grammar is ambiguous, exhibit 1 string with 2 distinct leftmost derivations.

Approach

• Identify productions with 2 or more non-terminals on the RHS. Split-point ambiguity can only arise there.
• Determine what strings each non-terminal generates.
• Find a string derivable from such a production where the split between adjacent non-terminals is not unique.
• Construct 2 explicit leftmost derivations.

Example

Grammar: $S \to a \mid Sa \mid bSS \mid SSb \mid SbS$

From $S \to a$ and $S \to Sa$, $S$ generates all strings of 1 or more $a$s.

The production $S \to bSS$ derives $b$ followed by 2 adjacent strings from $L(S)$. For the suffix $aaa$, 2 valid splits exist:

• $a \mid aa$
• $aa \mid a$

So $baaa$ has 2 distinct leftmost derivations.

Derivation 1:

S ⟹ bSS ⟹ bSaS ⟹ baaS ⟹ baaa

Derivation 2:

S ⟹ bSS ⟹ baS ⟹ baSa ⟹ baaa

Parse tree 1:

      S
    / | \
   b  S   S
     / \  |
    S   a a
    |
    a

Parse tree 2:

      S
    / | \
   b  S   S
      |  / \
      a  S  a
         |
         a

Examples

Grammar of arithmetic

Ambiguous because $a + a - a$ has 2 possible leftmost derivations.

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

• $S → S + T\;|\; S - T\; |\; T$
• $T → T * F\;|\; T / F\; |\; F$
• $F → (S)\; |\; a$

Each non-terminal corresponds to 1 precedence level. Operators at lower precedence sit closer to $S$ in the hierarchy, so they appear higher in any parse tree and bind less tightly. Left-recursion on each rule ($S \to S + T$, $T \to T * F$) enforces left associativity.

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.”