Derivations and Parse Trees

A context-free grammar $G = (V, \Sigma, R, S)$ consists of nonterminals $V$, terminals $\Sigma$, production rules $R$, and a start symbol $S$. A derivation step rewrites a single occurrence of a nonterminal $A$ appearing in some string $\alpha A \beta$ (where $\alpha, \beta$ are strings of terminals and nonterminals) into $\gamma$, provided $A \to \gamma$ is a rule in $R$. We write

to denote one derivation step. A derivation is a chain of such steps,

written compactly as $S \Rightarrow^{*} w$, showing that the string $w$ is generated by $G$. Crucially, at each intermediate string $\sigma_i$ there is usually more than one nonterminal present, and the grammar's rules say nothing about which one must be expanded next — that choice is a bookkeeping decision made by whoever performs the derivation, not a property of the grammar itself. This ambiguity of order (not to be confused with ambiguity of the grammar) motivates fixing a canonical strategy. In a leftmost derivation, every step expands the leftmost nonterminal symbol still present in the current string. In a rightmost derivation, every step expands the rightmost nonterminal. These are conventions for producing a unique, deterministic sequence of steps that generates a given string, out of all the equivalent unordered derivations that differ only in which nonterminal was chosen first. Top-down parsers (like recursive descent) naturally construct leftmost derivations; bottom-up parsers (like LR parsers) naturally construct the reverse of rightmost derivations. A parse tree (also called a derivation tree) for a grammar $G$ is a rooted, ordered tree satisfying three conditions: the root is labeled $S$; every internal node is labeled by some nonterminal $A$, and its children, read left to right, spell exactly the right-hand side of some rule $A \to X_1 X_2 \cdots X_k$ (with a single child labeled $\varepsilon$ if the rule is $A \to \varepsilon$); and every leaf is labeled by a terminal symbol or $\varepsilon$. The yield of the tree — its leaves read left to right — is the string generated. The tree captures only the hierarchical grouping of substitutions, discarding the temporal order in which they were performed. This is exactly why many different derivations, differing only in the interleaving of independent expansions, collapse onto the same single tree.

Building a parse tree from a grammar and a target string is the essence of parsing. Two dual algorithmic strategies correspond to leftmost and rightmost derivations respectively.

Top-down construction (leftmost derivation). Start with a single root node labeled $S$. Repeatedly find the leftmost nonterminal leaf in the tree built so far, choose a rule for it, and attach children spelling that rule's right-hand side. Continue until every leaf is a terminal (or $\varepsilon$) and the yield matches the target string.

Bottom-up construction (reverse rightmost derivation). Start with the target string as a forest of terminal leaves. Repeatedly find a substring matching some rule's right-hand side, replace it with a new internal node labeled by that rule's left-hand side, and continue until only the root $S$ remains. Read the sequence of reductions backward to recover the rightmost derivation. Below is pseudocode for generating a leftmost derivation and simultaneously constructing its parse tree, given a grammar and (via nondeterministic choice, as in a search procedure) a target string. This models what a nondeterministic top-down parser conceptually does; deterministic parsers add lookahead and restrictions to make the rule choice computable without backtracking. ``` function LEFTMOST-DERIVE(G, target):

# G = (V, Sigma, R, S). Returns a parse tree with yield == target,

# or FAIL if no leftmost derivation of target exists. root = new TreeNode(label = S, children = []) frontier = [root] # ordered list of tree leaves, left to right derivation = [] # sequence of (nonterminal, rule) pairs function YIELD(frontier): return concatenate(node.label for node in frontier if node.isTerminalOrEpsilon) function EXPAND(frontier, target):

# find leftmost nonterminal leaf i = index of first node in frontier where node.isNonterminal if i does not exist: return (YIELD(frontier) == target) ? SUCCESS : FAIL A = frontier[i].label for each rule (A -> X1 X2 ... Xk) in R: # nondeterministic choice newChildren = [TreeNode(Xj) for Xj in X1..Xk] # or single epsilon-node if k==0 attach newChildren as children of frontier[i] newFrontier = frontier[0:i] + newChildren + frontier[i+1:] partialYield = concatenate terminal labels in newFrontier up to next nonterminal if partialYield is not a prefix of target so far: undo attachment continue # prune: this choice cannot lead to target derivation.append((A, rule)) result = EXPAND(newFrontier, target) if result == SUCCESS: return SUCCESS derivation.pop() undo attachment # backtrack return FAIL if EXPAND(frontier, target) == SUCCESS: return (root, derivation) else: return FAIL ``` The rightmost analogue is identical except that `EXPAND` always selects the last nonterminal leaf in `frontier` rather than the first, and the resulting derivation, read in the order rules are applied, is the rightmost derivation of `target`. The figure below shows the parse tree for the arithmetic string `2+3*4` under a grammar with rules $E \to E + E \mid E * E \mid \text{num}$, alongside the two canonical derivations it corresponds to.

For this tree, the leftmost derivation always expands the leftmost `E`:

and the rightmost derivation always expands the rightmost `E`:

Both derivations produce the exact same tree shown above — they differ only in which order the two `E` children of the root were expanded, not in the final nesting structure.

Time and space for tree construction. For a fixed grammar $G$ with $|R|$ rules, each of bounded right-hand-side length, generating a leftmost derivation top-down with unbounded backtracking (as in the pseudocode above) is exponential in the worst case: at each of the $O(n)$ expansion steps for a target string of length $n$, up to $|R|$ rule choices must be tried, giving a search tree of size $O(|R|^n)$ in the naive case. This is why real parsers restrict attention to grammar subclasses (LL(1), LR(1), etc.) or use dynamic-programming parsers like CYK, which run in $O(n^3)$ time and $O(n^2)$ space for arbitrary context-free grammars by building parse trees bottom-up over all substrings, avoiding redundant recomputation. The CYK approach itself relies on rules being in Chomsky Normal Form, a normal form specifically designed to make this dynamic program clean — foreshadowing why that normal form exists at all. Independent of parsing strategy, once a specific derivation (leftmost or rightmost) of length $n$ steps is given, constructing its parse tree takes $O(n)$ time and $O(n)$ space: each step attaches $O(1)$ amortized new nodes (bounded by the maximum rule length), and the total number of nodes in the tree is linear in the number of derivation steps plus the string length.

Correctness argument — the leftmost/tree bijection. The central fact to justify is: > For any context-free grammar $G$ and string $w \in L(G)$, there is a bijection between parse trees for $w$ and leftmost derivations of $w$ (and, separately, a bijection between parse trees for $w$ and rightmost derivations of $w$). Tree → leftmost derivation. Given a parse tree $T$, produce a leftmost derivation by induction on tree size. If $T$ is a single terminal leaf, the derivation is empty (or the trivial one-step case $A \Rightarrow a$). Otherwise let the root be $A$ with rule $A \to X_1 \cdots X_k$ and subtrees $T_1, \ldots, T_k$ rooted at $X_1, \ldots, X_k$. Emit the step $A \Rightarrow X_1 X_2 \cdots X_k$, then recursively emit the leftmost derivation of $T_1$'s yield (this expands all nonterminals inside $T_1$ before touching $X_2, \ldots, X_k$, since $T_1$'s internal nonterminals are, by construction, always the leftmost pending nonterminal until $T_1$ is fully expanded), then of $T_2$'s yield, and so on. This produces one well-defined derivation and it is easily checked to always expand the current leftmost nonterminal, by induction on the recursive structure. Leftmost derivation → tree. Conversely, given a leftmost derivation, build the tree exactly as the top-down pseudocode does: each step $\alpha A \beta \Rightarrow \alpha \gamma \beta$ (with $A$ leftmost) attaches $\gamma$'s symbols as children of the tree node currently representing that occurrence of $A$. Because the derivation always targets the unique leftmost pending nonterminal, there is never an ambiguity about which tree node receives the new children — the construction is forced at every step, giving a well-defined tree. These two maps are mutually inverse. Running tree → derivation → tree recovers the original tree exactly, because the induction above visits subtrees in the same left-to-right order that the reconstruction consumes derivation steps; running derivation → tree → derivation recovers the original derivation exactly, because at every point the "leftmost pending nonterminal" in the partially built tree is uniquely determined by the tree's shape so far, matching the induction's recursive order. Formally this is proved by induction on the number of derivation steps, showing the invariant: after $i$ steps of a leftmost derivation, the frontier of the corresponding partially-built tree, read left to right, equals the current sentential form $\sigma_i$. This invariant holds trivially at $i = 0$ (frontier is just the root $S$), and is preserved at each step because expanding the leftmost nonterminal leaf in the tree corresponds exactly to rewriting the leftmost nonterminal occurrence in the string. The same argument, mirrored, gives the rightmost bijection.

Why unordered derivations do not give a bijection. A general (non-canonical) derivation need not expand nonterminals in any consistent left-to-right or right-to-left order — two independent nonterminals $A$ and $B$ present simultaneously in a sentential form can each be expanded first, giving two different derivations that nevertheless produce the identical tree (they only reorder when independent subtrees are grown, not how they nest). This is precisely why leftmost and rightmost derivations are singled out as canonical: they are the two derivation orders that break all remaining freedom by fixing a deterministic scan direction, collapsing the many equivalent unordered derivations of a tree down to exactly one representative each.

The honest tradeoff. Parse trees are the "right" object to reason about structure (operator precedence, scope nesting, semantic meaning), but they are more expensive to store and manipulate than a bare derivation string or a compressed abstract syntax tree. Compilers typically build a full parse tree (or an equivalent internal structure) only implicitly, collapsing it immediately into a leaner abstract syntax tree that omits redundant unit-production nodes, trading some traceability back to the exact grammar rules used for a smaller memory footprint and faster downstream traversal.

Take the classic (deliberately ambiguity-prone) grammar for simple arithmetic:

and derive the string `id + id × id`, tracing a leftmost derivation, its rightmost counterpart, and the resulting tree — using the derivation choice that groups `+` at the top (i.e., reading the string as `id + (id × id)`).

Both sequences are 5 steps long and use exactly the same multiset of rules — one application of $E \to E+E$, one of $E \to E \times E$, and three of $E \to \text{id}$ — but applied in reverse relative order, since leftmost sweeps outer-to-inner-left while rightmost sweeps outer-to-inner-right. Both correspond to the single tree: ``` E / | \ E + E | /|\ id E × E | | id id ``` Now check the bijection claim concretely. Reading the tree top-down, left to right, the induction described above emits: root rule $E \to E+E$ first (step 1 above); then recurse into the left child, which is a leaf `id`, contributing nothing further to the derivation steps beyond having already appeared; then recurse into the right child $E$, whose rule is $E \to E \times E$ (step 2's target, but note it appears as step 3 in the table because the leftmost `id` at position 1 must first be finalized) — this exactly reconstructs the leftmost derivation column. Running the same tree through the rightmost-recovery procedure (recursing right-to-left, applying the mirrored invariant) reconstructs the rightmost derivation column. Since both procedures are deterministic functions of the tree alone, this single tree provably yields exactly one leftmost and exactly one rightmost derivation — no other ordering of these same three rule applications is either leftmost or rightmost, even though several such orderings exist and all describe the same tree. Contrast this with genuine ambiguity: the same string `id + id × id` also has a second, different parse tree grouping as `(id + id) × id`: ``` E / | \ E × E / | \ | E + E id | | id id ``` This tree has a different shape (root rule is $E \to E \times E$, not $E \to E+E$), hence a genuinely different leftmost derivation: $E \Rightarrow E \times E \Rightarrow E{+}E \times E \Rightarrow \text{id}+E \times E \Rightarrow \text{id}+\text{id} \times E \Rightarrow \text{id}+\text{id}\times \text{id}$. Because two structurally distinct trees both yield the same final string under this grammar, the grammar is ambiguous for this input — the precise phenomenon that the concept of Ambiguity in Context-Free Grammars formalizes and studies.

The formal machinery of derivations and parse trees emerged from the mid-20th-century convergence of linguistics and computer science, as researchers sought precise mathematical models for how sentences — in natural language and later in programming languages — could be systematically generated and structurally analyzed.

Every modern compiler and interpreter — for C, Python, JavaScript, SQL, or any structured configuration language — relies on parsing a token stream into a parse tree (or a closely related abstract syntax tree) before any semantic analysis or code generation can proceed. Parser generators such as Yacc, Bison, ANTLR, and the Earley- or LR-based engines inside modern language toolchains all implement, at their core, the leftmost- or rightmost-derivation logic described here, differing mainly in how much lookahead and backtracking they permit before committing to a rule choice. Beyond programming languages, XML and JSON schema validators, natural language parsers used in computational linguistics, and even query optimizers for SQL that need to understand the structure of a query all build and manipulate parse-tree-like structures derived from an underlying context-free (or context-free-adjacent) grammar. The leftmost/rightmost canonical-derivation framework is also the conceptual foundation for understanding why certain grammars admit efficient, deterministic parsing (LL and LR grammars) while others require exponential search or restriction to normal forms — a distinction that directly determines which grammar classes are practical for building real-world language tools.

Ask the tutor: Can you show why an ambiguous grammar can sometimes be rewritten into an equivalent unambiguous grammar, and when that's impossible?