Grammar Design

Ambiguity, Conflicts, and Why Parsers Break

A deep dive into why some grammars fail, what ambiguity means, and how to fix it before building your parser.

Concept

1. What is Ambiguity in a Grammar?

A Context Free Grammar (CFG) is ambiguous if:

A single string can be generated by more than one valid parse tree.

This means the grammar does not define a unique structure for some inputs. The compiler won't know which interpretation is the "correct" one.

Example

Grammar
E → E + E | E * E | id
Input String
id + id * id

This string can be interpreted in two ways. Both are perfectly valid according to the grammar rules:

Case 1: + has higher grouping

    +
   / \
 id   *
     / \
   id  id

Evaluates like: (id) + (id * id)

Case 2: * has higher grouping

    *
   / \
  +   id
 / \
id id

Evaluates like: (id + id) * (id)

Result: Same input. Different structure. This is ambiguity.

2. Why Ambiguity is a Problem

Compilers must decide:

  • Order of operations
  • Structure of expressions
  • Meaning of program

If ambiguity exists:

  • Parsing tables produce conflicts.
  • Multiple parse trees exist.
  • Compiler behavior becomes undefined.

3. Ambiguity vs Regular Expressions

Regular expressions:

  • Do not form hierarchical structures.
  • Do not generate parse trees.
  • Are inherently unambiguous.

CFGs:

  • Build hierarchical structure.
  • Can generate multiple parse trees.
  • Can become ambiguous if poorly designed.
Solutions

4. How to Remove Ambiguity

There is no universal automatic fix. Ambiguity is removed by grammar design rules.

Method 1: Precedence Rules

Original (Ambiguous)
E → E + E | E * E | id
Rewritten (Deterministic)
E → E + T | T
T → T * F | F
F → id

Now * has higher precedence than +. The structure is forced to be deterministic.

Method 2: Associativity Control

Forcing left-associative grouping:

E → E + T
T → T * F

This forces the parser to group operations from left to right (e.g. a + b + c becomes (a + b) + c).

Method 3: Remove Left Recursion (LL Parsers)

Left Recursive
E → E + T | T
Right Recursive
E → T E'
E' → + T E' | ε

This doesn't remove ambiguity alone, but makes the grammar usable in Top-Down LL parsing (preventing infinite loops).

Method 4: Left Factoring

When multiple productions share a prefix:

Conflicting Prefix
S → iEtS | iEtSeS | a
Factored
S → iEtS S' | a
S' → eS | ε

This delays the decision until enough tokens have been read, removing conflict during parsing.

5. Important Insight

Ambiguity is not a parsing bug. It is a grammar design problem.

A good programming language grammar must be:

  • Unambiguous
  • Deterministic under parsing rules
  • Structurally consistent

6. Link to Parser Conflicts

Ambiguity often leads to:

  • Shift/Reduce conflicts
  • Reduce/Reduce conflicts
  • LL(1) table collisions
But note: Not all conflicts come from ambiguity, and not all ambiguity causes visible conflicts immediately.

7. Summary

A grammar is ambiguous if a string has multiple parse trees. To remove it, define precedence, set associativity, remove left recursion, apply left factoring, or redesign the grammar entirely.

The Goal: One Input → One Structure → One Meaning
◀
Prev
Practice
Home
Intro
▶