ToolSphere
Back to all articles
student

Ambiguous Grammar Examples With Parse Trees

2026-11-0310 min read

Try it: free Parse Tree Generator and Ambiguity Checker

Draw parse trees and see leftmost and rightmost derivations

Open →

A context-free grammar is ambiguous when at least one terminal string has two distinct parse trees. The trees must use the same grammar and produce the same ordered terminal leaves. Two different strings, two traversal orders of one tree or a drawing laid out differently do not establish ambiguity.

The parse tree generator supplies the trees, leftmost derivations and bounded-search witnesses below. Every witness and derivation is generated by its library. The expression grammar, dangling-else grammar and equal-count grammar demonstrate different reasons a recursive description can admit more than one structure.

What counts as a witness

A witness contains a terminal string and two valid trees. Equivalently, two distinct leftmost derivations for that string demonstrate the different choices of tree structure. Merely comparing a leftmost derivation with a rightmost derivation is not enough, because the same tree normally has both.

In a leftmost derivation, expand the leftmost unexpanded nonterminal at every step. An epsilon rule removes that nonterminal without inserting a terminal. The tables preserve those steps, including repeated-looking forms and empty subphrases, so the claimed trees can be checked against the productions.

Expressions without precedence

E -> E + E | E * E | id

This grammar gives addition and multiplication the same recursive expression slot. It also leaves repeated additions without an associativity rule. The search starts with short terminal strings rather than assuming a particular witness must be shortest.

The library's bounded search finds id + id + id after checking 4 generated strings. The two returned trees, as indented trees, are:

Tree 1:
E
├─ E
│  └─ id
├─ +
└─ E
   ├─ E
   │  └─ id
   ├─ +
   └─ E
      └─ id

Tree 2:
E
├─ E
│  ├─ E
│  │  └─ id
│  ├─ +
│  └─ E
│     └─ id
├─ +
└─ E
   └─ id

Branches show ordered children beneath each grammar variable. Terminal leaves occur without a production expansion. Both trees have the same leaf sequence, while their internal child structure differs.

Leftmost derivation for tree 1

Begin with E. At every row expand the leftmost remaining nonterminal:

Rule applied Resulting sentential form
E → E + E E + E
E → id id + E
E → E + E id + E + E
E → id id + id + E
E → id id + id + id

Leftmost derivation for tree 2

Begin with E. At every row expand the leftmost remaining nonterminal:

Rule applied Resulting sentential form
E → E + E E + E
E → E + E E + E + E
E → id id + E + E
E → id id + id + E
E → id id + id + id

The trees prove ambiguity even if your usual arithmetic convention would prefer one grouping. That convention has not been encoded by these grammar rules. Use separate expression/term/factor variables or an explicitly documented parser conflict policy when a language needs one interpretation.

The dangling else

S -> i E t S | i E t S e S | a
E -> b

Here i means if, b is the condition token, t means then, e means else, and a is an atomic statement. The grammar allows a statement with or without an else. A nested conditional can leave the else attached to either eligible if.

The library's bounded search finds i b t i b t a e a after checking 5 generated strings. The two returned trees, as indented trees, are:

Tree 1:
S
├─ i
├─ E
│  └─ b
├─ t
└─ S
   ├─ i
   ├─ E
   │  └─ b
   ├─ t
   ├─ S
   │  └─ a
   ├─ e
   └─ S
      └─ a

Tree 2:
S
├─ i
├─ E
│  └─ b
├─ t
├─ S
│  ├─ i
│  ├─ E
│  │  └─ b
│  ├─ t
│  └─ S
│     └─ a
├─ e
└─ S
   └─ a

Branches show ordered children beneath each grammar variable. Terminal leaves occur without a production expansion. Both trees have the same leaf sequence, while their internal child structure differs.

Leftmost derivation for tree 1

Begin with S. At every row expand the leftmost remaining nonterminal:

Rule applied Resulting sentential form
S → i E t S i E t S
E → b i b t S
S → i E t S e S i b t i E t S e S
E → b i b t i b t S e S
S → a i b t i b t a e S
S → a i b t i b t a e a

Leftmost derivation for tree 2

Begin with S. At every row expand the leftmost remaining nonterminal:

Rule applied Resulting sentential form
S → i E t S e S i E t S e S
E → b i b t S e S
S → i E t S i b t i E t S e S
E → b i b t i b t S e S
S → a i b t i b t a e S
S → a i b t i b t a e a

Choosing the nearest unmatched if is a conventional disambiguation policy. It does not make the grammar as written unambiguous. Left factoring can expose a shared prefix while retaining the decision conflict over the optional else.

Two balanced-count decompositions

S -> a S b S | b S a S | ε

The rule branches put one a and one b around independently generated subphrases. Equal terminal counts describe its language, but that count invariant does not force a unique decomposition into these recursive branches.

The library's bounded search finds a b a b after checking 5 generated strings. The two returned trees, as indented trees, are:

Tree 1:
S
├─ a
├─ S
│  └─ ε
├─ b
└─ S
   ├─ a
   ├─ S
   │  └─ ε
   ├─ b
   └─ S
      └─ ε

Tree 2:
S
├─ a
├─ S
│  ├─ b
│  ├─ S
│  │  └─ ε
│  ├─ a
│  └─ S
│     └─ ε
├─ b
└─ S
   └─ ε

Branches show ordered children beneath each grammar variable. Terminal leaves occur without a production expansion. Both trees have the same leaf sequence, while their internal child structure differs.

Leftmost derivation for tree 1

Begin with S. At every row expand the leftmost remaining nonterminal:

Rule applied Resulting sentential form
S → a S b S a S b S
S → ε a b S
S → a S b S a b a S b S
S → ε a b a b S
S → ε a b a b

Leftmost derivation for tree 2

Begin with S. At every row expand the leftmost remaining nonterminal:

Rule applied Resulting sentential form
S → a S b S a S b S
S → b S a S a b S a S b S
S → ε a b a S b S
S → ε a b a b S
S → ε a b a b

The two derivations choose different recursive splits of the same terminal string. A grammar generating the same equal-count language can use a different decomposition strategy; that does not retroactively remove these two trees from the given grammar.

Bounded search is evidence, not a decision procedure

The tool enumerates short generated strings and asks its parse-tree search for distinct trees. Finding two trees is a positive ambiguity witness. Finding none within a chosen bound does not prove the grammar unambiguous: a longer witness may exist, or the search may reach its exploration limit. General CFG ambiguity is not decidable by a universal terminating procedure.

Unit and epsilon cycles need additional care. The tree library cuts repeated expansion of the same nonterminal over the same token span, avoiding infinitely many cycle-expanded versions. Its output is a bounded teaching search rather than a count of every finite tree in a cyclic grammar. The examples above exhibit distinct finite structures without relying on padding a tree with a unit cycle.

Check the leaves before interpreting a diagram

Read both trees from left to right and compare their terminal sequences. Verify that every internal node uses an actual grammar production. Then compare the point where the structures branch differently: an expression grouping, an else attachment or a recursive span split. The indented trees above are useful when screen layout makes a wide drawn tree hard to compare.

A grammar's ambiguity and a parser's conflict are related but different properties. A conflict in a restricted parsing method does not by itself prove ambiguity. Conversely, an explicit precedence policy can choose a parse for an ambiguous expression grammar without changing that grammar's mathematical set of trees.

Use the LR parser to inspect conflicts and declared precedence. The left-recursion tool shows grammar rewrites; removing recursion or factoring common prefixes is not a general ambiguity cure. The compiler lab links the examples to the surrounding parsing exercises.

For a related walkthrough, read Left Recursion and Left Factoring Examples.

Looking for other tools?

Explore ToolSphere Homepage →