ToolSphere

Parse Tree Generator and Ambiguity Checker

Computer science

Draw the parse tree of a string for any grammar, get its leftmost and rightmost derivations, and find two trees that prove a grammar ambiguous.

Type a grammar and a string to draw its parse trees and compare derivations.

Two parse trees found: this string proves the grammar is ambiguous.

Grammar (one rule per line)

One rule per line, spaces between symbols: E -> E + T | T. Write ε (or eps) for an empty right side, one that matches nothing. The first rule is the start.

Two different parse trees for the same string: the grammar is ambiguous, and this string proves it.

Parse tree 1 of 2

EEid+EEid*Eid

leftmost derivation (5 steps)

  1. E
  2. ⇒ E + EE → E + E
  3. ⇒ id + EE → id
  4. ⇒ id + E * EE → E * E
  5. ⇒ id + id * EE → id
  6. ⇒ id + id * idE → id

rightmost derivation (5 steps)

  1. E
  2. ⇒ E + EE → E + E
  3. ⇒ E + E * EE → E * E
  4. ⇒ E + E * idE → id
  5. ⇒ E + id * idE → id
  6. ⇒ id + id * idE → id

One parse tree has exactly one leftmost and one rightmost derivation. Two leftmost derivations of the same string mean two trees, which is the definition of an ambiguous grammar.

Is the grammar ambiguous?

Checks the grammar's own strings, shortest first, up to 10 tokens, and stops at the first one with two parse trees.

On this browser only

Give feedback

Did this tool help?

Tell us what worked, what didn’t, or what you’d like next.

Opens Google Forms in a new tab with this tool’s name filled in. No sign-in or email required. Feedback is optional.

How to use Parse Tree Generator and Ambiguity Checker

  1. 1Type the grammar, one rule per line, or load an example such as the ambiguous E -> E + E | E * E grammar or the dangling else.
  2. 2Type the string to derive; spaces between tokens are optional.
  3. 3Read the verdict: no parse tree, exactly one, or two different trees, which proves the grammar is ambiguous.
  4. 4Switch between Tree 1 and Tree 2 to compare them, and read each tree's leftmost and rightmost derivation.
  5. 5Press Search for an ambiguous string to let the tool look for a short string with two parse trees.

About Parse Tree Generator and Ambiguity Checker

What this tool does

Questions about derivations, parse trees and ambiguity open every compiler design and theory of computation course. "Give the leftmost derivation of id + id * id", "draw its parse tree", "show the grammar is ambiguous". This tool answers all three for any context-free grammar you type, including left-recursive grammars and grammars with ε-productions. It draws each parse tree, writes the leftmost and rightmost derivations that build it, and when a string has two different parse trees it shows both. That pair of trees is exactly the proof an exam asks for.

Derivations and parse trees

A derivation starts from the start symbol and replaces one non-terminal at a time by the right-hand side of one of its rules until only terminals remain. In a leftmost derivation the replaced non-terminal is always the leftmost one. In a rightmost derivation it is always the rightmost one, and that is the order a bottom-up parser discovers, in reverse. A parse tree records which rule expanded each non-terminal and forgets the order, so each parse tree corresponds to exactly one leftmost derivation and exactly one rightmost derivation.

Worked example: id + id * id

With the layered expression grammar E → E + T | T, T → T * F | F, F → ( E ) | id, the string id + id * id has exactly one parse tree. The tool writes its derivations as:

Step Leftmost Rightmost
1 E + T E + T
2 T + T E + T * F
3 F + T E + T * id
4 id + T E + F * id
5 id + T * F E + id * id
6 id + F * F T + id * id
7 id + id * F F + id * id
8 id + id * id id + id * id

Both take eight steps because both use the same eight rules, just in a different order. In the tree, the multiplication sits below the addition, so it is evaluated first.

Ambiguity

A grammar is ambiguous when some string has two different parse trees, which is the same as two different leftmost derivations. The grammar E → E + E | E * E | ( E ) | id is the standard example. For id + id * id the tool finds two trees. In one, E + E is at the root and the multiplication sits underneath, which means id + (id * id). In the other, E * E is at the root, which means (id + id) * id. Both are valid trees for the same string, so the grammar is ambiguous. The layered grammar above describes the same expressions without ambiguity, because each precedence level has its own non-terminal.

Finding an ambiguous string

Proving a grammar ambiguous only takes one string with two trees. The search button lists the grammar's own strings shortest first, up to ten tokens, and parses each one until it finds a second tree. For the dangling-else grammar S → i E t S | i E t S e S | a with E → b it finds i b t i b t a e a. That is if b then if b then a else a, where the else can belong to either if. For S → a S b S | b S a S | ε it finds a b a b. When the search finds nothing, the tool says so plainly. Whether a grammar is ambiguous cannot be decided by any algorithm in general, so a clean search is evidence, not proof.

How it finds the trees

The tool parses the string with a memoised search over every way each rule can cover each part of the string, which works for left recursion and ε-productions alike. It stops after two trees, because two already settle the question. Rules that let a non-terminal derive itself over the same span, such as S → S, would allow infinitely many trees. Those repeated loops are skipped, and every tree without them is considered.

Common mistakes

  • Mixing leftmost and rightmost. Once you start replacing the leftmost non-terminal, every step must do the same.
  • Calling two derivations ambiguity. A leftmost and a rightmost derivation of the same tree do not make a grammar ambiguous. You need two leftmost derivations, or two trees.
  • Drawing ε away. A rule A → ε still gives A a child in the tree, labelled ε. The tool draws it.
  • Proving unambiguity from one string. One tree for one string shows nothing about other strings.

Related tools and guides

To remove the ambiguity of expressions, layer the grammar, then prepare it for top-down parsing with the left recursion and left factoring calculator and build its table in the LL(1) parser. Bottom-up parsing of the same grammars is in the LR parser and the operator precedence parser. To check whether a grammar in Chomsky normal form generates a string, see the CYK algorithm example.

Guides and tutorials

Frequently asked questions

How do you show that a grammar is ambiguous?

Find one string that has two different parse trees, or equivalently two different leftmost derivations. Draw both trees as the proof. Type the grammar and the string here to get both trees, or use the search to find a short string with two trees.

What is the difference between a leftmost and a rightmost derivation?

In a leftmost derivation every step replaces the leftmost non-terminal; in a rightmost derivation every step replaces the rightmost one. They use the same rules in a different order, and each parse tree has exactly one of each. A bottom-up parser builds the rightmost derivation in reverse.

Is E -> E + E | E * E | id ambiguous?

Yes. The string id + id * id has two parse trees: one with + at the root, meaning id + (id * id), and one with * at the root, meaning (id + id) * id. Rewriting it as E -> E + T | T, T -> T * F | F, F -> id removes the ambiguity.

Why is the dangling else grammar ambiguous?

In S -> i E t S | i E t S e S | a, the string i b t i b t a e a (if b then if b then a else a) has two parse trees: the else can belong to the inner if or the outer one. The tool's search finds exactly this string.

Can a tool prove that a grammar is not ambiguous?

Not in general: ambiguity of context-free grammars is undecidable. This tool can prove ambiguity by finding two trees, and it reports when none of the short strings it checked has two trees, but that is evidence rather than proof.

Does it work with left-recursive grammars and ε-productions?

Yes. The parser tries every way each rule can cover each part of the string, so left recursion such as E -> E + T and ε rules such as S -> ε are handled directly, with ε drawn as its own leaf in the tree.

How many parse trees does the tool show?

Up to two, because two trees already prove the grammar is ambiguous and are what an exam answer needs. Use the Tree 1 and Tree 2 buttons to switch between them, with each tree's derivations underneath.

What if my string has no parse tree?

Then it is not in the language of the grammar, and the tool says so. Check that the tokens match the terminals in your rules, for example id rather than a, and that spaces separate multi-letter symbols in the grammar.

What does it do with rules like S -> S?

A rule that lets a non-terminal derive itself over the same part of the string would allow infinitely many trees. The tool skips those repeated loops and counts every tree without them, which is what textbooks mean in practice.

Is a grammar with two derivations for a string always ambiguous?

Only if the derivations are both leftmost (or both rightmost) and different. A leftmost and a rightmost derivation of the same tree are always different but describe the same structure, so they say nothing about ambiguity.

Have a suggestion for Parse Tree Generator and Ambiguity Checker?Share your feedback ↗