Context-Free Grammars & Derivations

a parse tree

A derivation is a long verbal play-by-play of how a string was built; a parse tree is the picture that captures it all at once. It is a tree drawing whose shape shows how the pieces nest inside each other — the structural skeleton of the string. Where a derivation lists moves in some order, the tree throws away the irrelevant ordering and keeps only the structure.

Formally, a parse tree for a context-free grammar is a tree where the root is labelled with the start symbol, every internal node is labelled with a variable, and the children of a node labelled A, read left to right, spell out the right-hand side of some production rule A → α used to expand A. The leaves are labelled with terminals (or ε for an empty production). Read the leaves left to right and you get the generated string, called the yield of the tree. So each internal node is one application of one rule, and the whole tree records the entire derivation independently of the order the rules were applied.

The deep payoff is the relationship between trees and derivations: one parse tree corresponds to MANY derivations (all the orderings of independent rewrites), but to exactly ONE leftmost derivation and exactly ONE rightmost derivation. That is why the parse tree, not the derivation sequence, is the honest notion of a string's structure — and why ambiguity is defined in terms of trees: a grammar is ambiguous when some string has two distinct parse trees, meaning two genuinely different structures. Beware the false equation 'different derivation = different structure'; two derivations of one tree differ only in bookkeeping order.

For E → E + E | E * E | a, the string a + a * a has TWO parse trees: one where + is the root (a + (a*a)) and one where * is the root ((a+a) * a). Each tree yields the same string a + a * a but pictures a different grouping.

Children of a node spell a rule's right-hand side; the leaves left-to-right are the yield. Two trees for one string = ambiguity.

One parse tree corresponds to many derivations but to exactly one leftmost (and one rightmost) derivation. Two distinct derivations do NOT imply two structures — only two distinct parse trees do.

Also called
derivation treesyntax treeconcrete syntax tree語法樹推導樹