Derivations, Parse Trees, and Ambiguity

Let $G = (N, \Sigma, P, S)$ be a context-free grammar with non-terminals $N$, terminals $\Sigma$, productions $P$, and start symbol $S$. A sentential form is any string over $N \cup \Sigma$ derivable from $S$. A derivation step rewrites one sentential form into another: $\alpha A \beta \Rightarrow \alpha \gamma \beta$ if $A \to \gamma \in P$, where $\alpha, \beta \in (N \cup \Sigma)^*$ and $A \in N$. A derivation is a chain $S = \alpha_0 \Rightarrow \alpha_1 \Rightarrow \cdots \Rightarrow \alpha_n = w$ where $w \in \Sigma^*$; we write $S \Rightarrow^* w$. The set of strings so derivable is $L(G)$. At each step, a sentential form may contain several non-terminals, and the definition of $\Rightarrow$ does not specify which one to rewrite. Two canonical policies remove this freedom. In a leftmost derivation (written $\Rightarrow_{lm}$), every step expands the leftmost non-terminal in the current sentential form. In a rightmost derivation (written $\Rightarrow_{rm}$, sometimes called a "canonical derivation"), every step expands the rightmost non-terminal. These are not different grammars or different languages — they are different strategies for exploring the same set of derivations, and they matter because Top-Down Parsing methods naturally construct leftmost derivations while Bottom-Up Parsing methods naturally construct rightmost derivations in reverse. A parse tree (or derivation tree) for $G$ is an ordered tree where: the root is labeled $S$; each internal node is labeled by some $A \in N$ and its children, read left to right, spell out the right-hand side $\gamma$ of some production $A \to \gamma \in P$ (a node labeled $A$ with a single child labeled $\varepsilon$ represents $A \to \varepsilon$); and each leaf is labeled by a terminal, or by $\varepsilon$. The yield of the tree is the concatenation of its leaf labels left to right, and a tree is a parse tree for string $w$ if its yield is $w$. Crucially, a parse tree records which production was applied at which node, but not the order in which the productions were applied relative to each other — that ordering information is exactly what a derivation adds and a parse tree discards. A grammar $G$ is ambiguous if some string $w \in L(G)$ has two or more distinct parse trees. Because of the equivalence proved below, this is the same as saying $w$ has two distinct leftmost derivations (or, equivalently, two distinct rightmost derivations). Ambiguity is a property of the grammar, not of the language: the same language can often be generated by both an ambiguous grammar and an unambiguous one, and part of grammar engineering is finding the unambiguous version.

Constructing a leftmost derivation. The mechanism is a simple leftmost-rewrite loop: scan the current sentential form for the first (leftmost) non-terminal, pick a production for it, substitute, and repeat until only terminals remain. ``` function LEFTMOST-DERIVE(G, S): form ← [S] # sequence of symbols, sentential form steps ← [] while form contains a non-terminal: i ← index of leftmost non-terminal A in form choose a production A → γ (this choice is the nondeterminism that a real parser must resolve) form ← form[0 .. i-1] · γ · form[i+1 .. end] append form to steps return steps # the derivation, ending in a terminal string ``` Building the corresponding parse tree alongside the derivation is just as mechanical: maintain a tree whose current frontier (leaves not yet expanded) mirrors the sentential form, and whenever a non-terminal $A$ is rewritten by $A \to \gamma$, attach children to $A$'s node spelling $\gamma$. ``` function BUILD-TREE-FROM-DERIVATION(steps): root ← new node(S) frontier ← [root] # left-to-right list of open leaves for each step (A → γ) applied at position i in steps: node ← frontier[i] # the leaf currently labeled A if γ = ε: attach child(node, ε) remove node from expansion set # ε-leaf is terminal-like else: for each symbol X in γ (left to right): attach child(node, X) replace frontier[i] with the new children, in order return root ``` The key correctness fact used by both real parsers and this construction is:

Theorem (Derivation–Tree Correspondence). For a context-free grammar $G$ and string $w \in \Sigma^*$, the following are equivalent: 1. $w$ has a parse tree with yield $w$ and root $S$. 2. $S \Rightarrow_{lm}^* w$ (a leftmost derivation exists). 3. $S \Rightarrow_{rm}^* w$ (a rightmost derivation exists). Moreover, distinct leftmost derivations correspond to distinct parse trees, and vice versa — so counting parse trees and counting leftmost derivations of $w$ give the same number. Proof sketch. (2) $\Rightarrow$ (1): induct on the number of derivation steps, using the tree-building procedure above; each leftmost expansion step corresponds to attaching one production's children to the current leftmost open leaf, and since expansion is always leftmost, the frontier ordering is unambiguous — there is exactly one "current leftmost open node" at every step, so the map from leftmost derivations to trees is well-defined. (1) $\Rightarrow$ (2): given a parse tree, perform a pre-order (left-to-right, depth-first) traversal, and at each internal node apply its production; this canonical traversal is a leftmost derivation, because pre-order always visits the leftmost unvisited subtree before any sibling to its right. The rightmost case (3) is symmetric, using a traversal that expands the rightmost open non-terminal at each step (equivalently, a reverse rightmost derivation corresponds to bottom-up reduction, the basis of shift-reduce parsing). Injectivity in both directions follows because the tree-to-derivation and derivation-to-tree maps constructed above are mutual inverses on the set of (production choice, position) sequences that respect leftmost order. $\blacksquare$ This theorem is precisely what licenses parser designers to work with whichever of the three objects is most convenient: top-down predictive parsers build leftmost derivations directly; bottom-up LR parsers build rightmost derivations in reverse; but both are computing the same parse tree, and it's the tree — not the derivation order — that carries semantic structure (e.g., driving syntax-directed translation).

Time and space to build one parse tree from a given derivation. If a derivation has $n$ steps and each step's production has right-hand side of length at most $k$ (a grammar constant), building the tree takes $O(nk)$ time and $O(nk)$ space, since each step attaches at most $k$ new children and the frontier list is updated once per step with an array/list splice of bounded local cost (amortized $O(k)$ with a suitable representation, e.g., a doubly linked list of frontier nodes). A parse tree for a string of length $m$ has at most $O(m)$ leaves, but can have more internal nodes if the grammar contains long unit-production chains ($A \to B \to C \to \cdots$); in the worst case (a grammar with $|N|$ non-terminals and no bound on chain length) tree size is $O(m \cdot |N|)$, since no non-terminal is expanded twice in a row on the same frontier position without producing a distinct sentential form. In practice, grammars for Top-Down Parsing and Bottom-Up Parsing are designed (or transformed) to avoid such chains, keeping parse trees $\Theta(m)$ in size.

Recognizing ambiguity is undecidable in general. There is no algorithm that takes an arbitrary context-free grammar and always correctly reports whether it is ambiguous — this is a classical undecidability result (reducible from the Post Correspondence Problem). What compilers rely on instead is sufficient, checkable conditions for unambiguity: a grammar is unambiguous if it can be parsed by a deterministic method such as LL(1) or LR(1), because the construction of those parsing tables itself either succeeds (proving no conflict, hence a unique parse per accepted string) or fails with a detected conflict. This is why parser-generator tools report "shift/reduce conflict" or "reduce/reduce conflict" rather than attempting a general ambiguity test — they are certifying unambiguity relative to their parsing strategy, which is decidable, rather than solving the undecidable general problem.

Correctness of the leftmost/rightmost equivalence rests on the induction sketched above: the key invariant is that at every prefix of a leftmost derivation, the sentential form splits cleanly into "fully terminal prefix already emitted to the left of the current point" and "one open non-terminal plus everything to its right still to be expanded," which mirrors exactly the frontier of a partially-built tree read left to right. This is why leftmost derivations correspond to pre-order tree construction and rightmost to post-order-reversed (i.e., a rightmost derivation read backward is the order in which a bottom-up parser reduces).

The honest tradeoff. Ambiguity is not always bad for writing a grammar — ambiguous grammars are often shorter, more natural, and closer to a language's informal description (e.g., "an if-statement, optionally followed by else"). The cost is that the compiler writer must supply extra information — precedence and associativity declarations, or a "match the else with the nearest unmatched if" rule — outside the bare grammar to pin down one tree per string. Rewriting a grammar to be unambiguous internalizes that rule into the productions themselves at the price of a taller, more layered grammar (as in the precedence-stratified $E, T, F$ example above), which is why parser generators support both approaches.

Take $G$: $E \to E + E \mid E * E \mid \mathrm{id}$, and the string $w = \mathrm{id} + \mathrm{id} * \mathrm{id}$. We exhibit two distinct leftmost derivations, proving $G$ is ambiguous on $w$.

Leftmost derivation 1 (yields tree A: `(id + id) * id`):

Leftmost derivation 2 (yields tree B: `id + (id * id)`):

Both are valid leftmost derivations of the same string from the same grammar, but they differ at step 1 (which top-level production is chosen), and this single early choice cascades into two structurally different trees — shown in the figure above. By the theorem, two distinct leftmost derivations means two distinct parse trees, which is the definition of $G$ being ambiguous. Semantically this matters enormously: tree A computes $(1+1) \times 1 = 2$-style precedence (multiplication after addition), while tree B computes the conventional $1 + (1 \times 1)$ (multiplication first) — the same string would evaluate to different results depending on which tree a compiler happens to build.

The fix. Stratify the grammar by precedence level, forcing associativity and precedence into the productions:

Now trace $w$ again: any leftmost derivation of $\mathrm{id} + \mathrm{id} * \mathrm{id}$ must start $E \to E + T$ (since $E \to T$ alone cannot yield a `+`), forcing the top-level split to occur at `+`; inside the right operand, $T \to T * F$ is the only way to introduce ``. There is exactly one leftmost derivation, exactly one parse tree — tree A's shape, `(id) + (id id)` structurally at the $E$/$T$ boundary — and the grammar is unambiguous on this string (and, one can verify, on every string in the language).

Dangling-else, a second worked case. Consider

and the string `if b then if b then a else a`. One parse attaches `else a` to the inner `if` (the conventional reading); another attaches it to the outer `if`. Both are valid parse trees under this grammar — a genuine ambiguity that, unlike operator precedence, is usually not removed by grammar rewriting in production compilers (though it can be, via an auxiliary non-terminal distinguishing "matched" from "unmatched" statements). Instead, most parser generators apply a disambiguation rule — "match each else with the closest unmatched then" — encoded directly in the parsing algorithm (e.g., by declaring `else` as taking precedence in a shift/reduce conflict). This shows the two available strategies side by side: precedence ambiguity is fixed in the grammar; dangling-else ambiguity is more often fixed in the parser's conflict-resolution policy.

Every production compiler front end — for C, Java, Python, Rust, or any language with an `if`/`else` construct or arithmetic expressions — must resolve exactly the ambiguities discussed here: expression-precedence ambiguity is designed away by grammar stratification (the `E`/`T`/`F` layering pattern generalizes to full operator-precedence tables), while dangling-else-style ambiguity is resolved by explicit disambiguation rules baked into parser generators like Yacc/Bison and ANTLR. Compiler front ends built with Top-Down Parsing techniques (recursive descent, LL parsers) construct leftmost derivations directly as they read input left to right, using exactly the frontier-expansion process described above; Bottom-Up Parsing techniques (LR, LALR, as used in Yacc/Bison and most industrial-strength parsers) construct rightmost derivations in reverse, reading shift/reduce and reduce/reduce conflicts as automated, decidable proxies for the underlying, otherwise-undecidable question of grammar ambiguity. Beyond compilers, the same theory underlies natural-language parsing (where ambiguity is the norm rather than the exception, and multiple parse trees are ranked probabilistically rather than eliminated) and configuration/data-format grammars (JSON, YAML schemas) where an unambiguous grammar is what guarantees a document parses to one unique structure regardless of which library reads it.

Ask the tutor: Can you show me why an LR(1) parser building a rightmost derivation "in reverse" actually recovers the same parse tree as a leftmost derivation would?