Derivations and Parse Trees
A context-free grammar
tells you which strings are legal, but it does so procedurally: to prove a string belongs, you
must actually derive it — start from S and rewrite
nonterminals, one production at a time, until nothing but terminals remains. Each rewrite is a step, and
the record of those steps is a derivation. The parse tree is the same event seen from
above: a picture of which productions were used and where, with the order thrown away.
This split — the linear derivation versus the two-dimensional tree — is the quiet
engine of the whole subject. A parser's job is to recover the tree; the two standard families of parsers
are named after the two standard orders of derivation. So it pays to get the vocabulary exactly right
before any algorithm arrives.
The derivation relation
Write \alpha A \beta \Rightarrow \alpha \gamma \beta — read "derives in one
step" — when a single production A \to \gamma is applied to one nonterminal
inside the string \alpha A \beta. Chain the arrow: \Rightarrow^{*}
means "derives in zero or more steps", and \Rightarrow^{+} means "in one or
more". A string reachable from the start symbol,
S \;\Rightarrow^{*}\; \sigma \qquad \sigma \in (V \cup T)^{*},
is called a sentential form. If \sigma happens to contain
only terminals it is a sentence — an actual member of the language. So the
language generated by G is precisely the set of sentences:
L(G) \;=\; \{\, w \in T^{*} \;\mid\; S \Rightarrow^{*} w \,\}.
Every intermediate line — E + T, then T + T, then
F + T, … — is a sentential form on the road from
E to the final sentence.
Leftmost and rightmost: which nonterminal do you rewrite?
At most steps a sentential form has several nonterminals, and you must choose which one to
expand. Two disciplined choices matter:
-
In a leftmost derivation (\Rightarrow_{lm}) you always
rewrite the leftmost nonterminal of the current sentential form. Top-down parsers —
LL, recursive descent — trace a leftmost derivation.
-
In a rightmost derivation (\Rightarrow_{rm}) you always
rewrite the rightmost nonterminal. Bottom-up parsers — LR, shift-reduce — trace a rightmost
derivation in reverse (the reductions replay it backwards). Rightmost forms are also called
canonical.
Fixing the order removes the freedom in which nonterminal, but not the freedom in
which production. That remaining freedom is exactly where
ambiguity
lives — a topic for the next page.
Worked example: a leftmost derivation of \mathbf{id} + \mathbf{id} * \mathbf{id}
Using the expression grammar E \to E + T \mid T,
T \to T * F \mid F, F \to (\,E\,) \mid \mathbf{id},
here is a full leftmost derivation. At every line the underlined-in-thought leftmost nonterminal is the
one about to be replaced; the third column names the production used.
| # | Sentential form | Production applied (to leftmost nonterminal) |
|---|
| 0 | E | start |
| 1 | E + T | E \to E + T |
| 2 | T + T | E \to T |
| 3 | F + T | T \to F |
| 4 | \mathbf{id} + T | F \to \mathbf{id} |
| 5 | \mathbf{id} + T * F | T \to T * F |
| 6 | \mathbf{id} + F * F | T \to F |
| 7 | \mathbf{id} + \mathbf{id} * F | F \to \mathbf{id} |
| 8 | \mathbf{id} + \mathbf{id} * \mathbf{id} | F \to \mathbf{id} |
Eight steps, eight productions, and the last line is all terminals — a sentence. Now watch the same
derivation as a growing tree. Each production hangs its right-hand side as children under the nonterminal
it rewrites; the frontier fills in left to right:
Read the leaves left to right and you recover the input string — that reading is the tree's
yield (or frontier). The internal structure is what the parser will
later hand to type-checking and code generation.
The tree is the derivation with the order erased
Here is the pivotal fact. A parse tree records which production expanded which
nonterminal — parent to children — but says nothing about the order in which the expansions
happened. A leftmost derivation and a rightmost derivation of the same sentence, though they list their
steps in different sequences, build the identical tree. The tree is the derivation's
equivalence class under "reorder independent steps".
- Every parse tree corresponds to exactly one leftmost derivation and
exactly one rightmost derivation.
- Conversely, a leftmost derivation and a rightmost derivation determine, and are determined by, a
single parse tree.
- So for a given tree there is no ambiguity in the derivation orders; ambiguity means a
second tree, not a second order.
This is why "how many parse trees does this string have?" is the sharp question, and "how many
derivations?" is not: reordering independent rewrites spawns many derivations from one tree, but those
are all the same structure. The frontier read left-to-right is invariant across all of them — it is
always the input sentence.
Counting derivations for one tree, in code
To make "one tree, many derivations" concrete: given a parse tree, the number of distinct
derivations equals the number of ways to linearly order the productions so that each parent is expanded
before its children — a topological count. For a tree, that count multiplies nicely. The leftmost and
rightmost orders are just two specific choices out of that (often large) set.
// A parse-tree node: a symbol plus its children (terminals have none).
type Node = { sym: string; kids: Node[] };
const n = (sym: string, ...kids: Node[]): Node => ({ sym, kids });
// Tree for id + id * id.
const tree: Node =
n("E",
n("E", n("T", n("F", n("id")))),
n("+"),
n("T",
n("T", n("F", n("id"))),
n("*"),
n("F", n("id"))));
// A nonterminal is any node that has children.
const isInternal = (x: Node) => x.kids.length > 0;
// Number of distinct derivations = number of linear extensions of the
// "expand parent before child" order. For a forest this is the multinomial
// (sum of subtree expansion-counts)! / product(subtree counts!).
function fact(k: number): number { let r = 1; for (let i = 2; i <= k; i++) r *= i; return r; }
// (expansions, derivations) for the subtree rooted at `node`.
function count(node: Node): { exp: number; ways: number } {
if (!isInternal(node)) return { exp: 0, ways: 1 };
const kids = node.kids.map(count);
const total = kids.reduce((s, k) => s + k.exp, 0); // child expansions
let ways = fact(total); // interleavings
for (const k of kids) ways = ways / fact(k.exp) * k.ways;
return { exp: total + 1, ways }; // +1 for this node
}
const { exp, ways } = count(tree);
console.log(`productions applied: ${exp}`);
console.log(`distinct derivations of this ONE tree: ${ways}`);
console.log("leftmost and rightmost are just 2 of those orders");
The same tree admits many derivations, yet all describe the identical structure. The parser only ever
needs one canonical order — leftmost for top-down, rightmost-reversed for bottom-up.
Because a parser does not have the tree yet — it is building it, left to right, one input token
at a time, and it must commit to moves before it has seen the whole string. A top-down parser starts at
the root and predicts productions, growing the leftmost nonterminal to match the next input token: that
is a leftmost derivation, played forwards. A bottom-up parser starts at the leaves and reduces groups of
symbols up to their parent, discovering the rightmost derivation in reverse. The finished tree
is order-blind, but the process of discovering it must follow a consistent order to line up with
the left-to-right stream of tokens. The order is a property of the algorithm, not of the answer.
Students often panic on discovering that a sentence has dozens of derivations and conclude the grammar is
ambiguous. It is not — not on that evidence. Reordering independent rewrites (expand the left subtree's
nonterminals before the right's, or interleave them) yields many derivations that all fold up
into the same tree. That is harmless and universal. Ambiguity is a
strictly stronger condition: it means the string has two different parse trees — equivalently,
two different leftmost derivations (or two rightmost). Always compare at the level of trees, or
of leftmost derivations specifically, never at the level of derivations-in-general. Counting all
derivations tells you nothing about ambiguity.