Derivation tree for a context-free grammar
Type a grammar and a string. If the grammar can produce the string, you get the leftmost derivation and watch it build the parse tree, one rule at a time. If it cannot, you are told so.
One rule per line, alternatives separated by |. Uppercase letters are variables, ε is the empty string, and the first rule’s variable is the start symbol. Violet variables are still waiting to be rewritten; green squares are the terminals that make up the string.
Start with the start symbol
The root of the tree is the variable of the first rule, and the sentential form is just that variable.
Rewrite the leftmost variable
Pick the first variable in the current form and replace it by one of its right-hand sides. In the tree, that variable gets one child per symbol of the right-hand side.
Repeat until only terminals are left
Every step makes the tree one level deeper somewhere. When no variable remains, the leaves read left to right spell the string.
Which rule to pick?
That is the hard part, and what a parser is for. This page uses Earley’s algorithm to find a derivation first, then replays it for you step by step.
What is the difference between a derivation and a parse tree?
A derivation is a sequence of sentential forms; a parse tree records which rule rewrote which variable, without fixing an order. Every parse tree has exactly one leftmost derivation, which is the one shown here.
My grammar is ambiguous. Which tree do I get?
All of them, up to twelve. When a string has more than one parse tree you are told the grammar is ambiguous and can switch between the trees; each plays its own leftmost derivation. Try E -> E+E | E*E | x with x+x*x: one tree means (x+x)*x, the other x+(x*x). Trees that only differ by a variable deriving itself over the same stretch (S ⇒ SS ⇒ S) are left out, because there are infinitely many of them.
Does it work with left recursion and ε-rules?
Yes. Rules like E -> E+T or S -> SS | ε are fine here, unlike in the grammar-to-PDA construction, where they make the machine explore without bound.
Can I turn the grammar into a machine?
Yes: “Grammar → PDA” in the run bar takes the grammar you typed to the CFG to PDA converter.