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.