Derivations, Sentential Forms, and What a Parse Tree Actually Records

A grammar is a finite set of rewrite rules, and a derivation is a record of applying them. The subtlety is that “applying a rule” is not a single event: a rule with several nonterminals on its left can fire at several places, in several orders, and the theory has to say which of those distinctions matter. Getting this right is what separates a grammar from a parser.

Rewriting is contextual substitution

A context-free grammar G = (V, Σ, R, S) has a finite set of nonterminals V, a disjoint finite set of terminals Σ, a start symbol S ∈ V, and a finite set of productions R, each of the form A → α with A ∈ V and α ∈ (V ∪ Σ)*. The word “context-free” states the restriction exactly: the left side is a single nonterminal, so the rule applies wherever that nonterminal appears, regardless of its neighbours. A context-sensitive rule such as aXb → aYb would be context-dependent, and its left side is not a single symbol.

The derivation relation ⇒ is defined on strings in (V ∪ Σ), called sentential forms. For u, v ∈ (V ∪ Σ), write u ⇒ v if u = xAβ and v = xαβ for some x ∈ (V ∪ Σ), β ∈ (V ∪ Σ), and rule A → α ∈ R. One step replaces one occurrence. The reflexive transitive closure ⇒* is derivability, and the language of G is

L(G) = { w ∈ Σ* : S ⇒* w }

so a string is in the language when it is derivable from the start symbol and consists only of terminals. A sentential form containing at least one nonterminal is a partial derivation: it is a claim about what the final string will look like, with holes still to be filled.

Note what the definition does not say. It does not say the derivation is unique, it does not say the rules are applied left to right, and it does not say the length of a sentential form is monotone. A rule A → ε shortens the form, and a rule A → ABC lengthens it. Derivations can loop, so a grammar may generate a string by infinitely many derivations even when each derivation is finite.

Leftmost, rightmost, and the irrelevance of order

At any step, the choice of which nonterminal to expand is independent of the choice of which rule to apply to it. Two derivations that differ only in the order of expansion are called permutations of each other, and they derive the same string with the same rules applied at the same positions. Because context-free rules never inspect neighbours, expansion order cannot affect the result.

This is a theorem, not an observation, and it justifies restricting attention to canonical orders. A leftmost derivation always expands the leftmost nonterminal of the sentential form; a rightmost derivation expands the rightmost. Every derivable string has a leftmost derivation and a rightmost derivation, and the leftmost derivation is unique exactly when the grammar is unambiguous.

For the grammar with productions S → S + S | S * S | (S) | a, the string a + a * a has a leftmost derivation

S ⇒ S + S ⇒ a + S ⇒ a + S * S ⇒ a + a * S ⇒ a + a * a

and another leftmost derivation that expands the second S first into a product whose left operand is the sum. Both are leftmost; they differ in which rule was applied to the first S. That is genuine ambiguity, not a permutation, and the distinction is the whole content of the next section.

The count of distinct derivations grows fast. In a grammar whose rules each add one nonterminal, the number of leftmost derivations of a string of length n is the number of binary tree shapes with n leaves, the Catalan number C_{n−1} = (1/n)·binomial(2n−2, n−1). For n = 10 that is 4862, and it grows roughly as 4ⁿ/n^{3/2}. Any parser that enumerates derivations is therefore exponential in the input length, which is why practical parsers record structure rather than steps.

Parse trees are derivations with the order quotiented out

A parse tree for a derivation is a rooted ordered tree. The root is labelled S. Each internal node is labelled by a nonterminal A and has children labelled by the symbols of α, in order, for some rule A → α used at that node. The yield is the string read left to right at the leaves. A tree is a parse tree for w when its yield is w and every leaf is labelled by a terminal or by ε.

The correspondence is exact:

• Every derivation determines a unique parse tree, obtained by recording each rule application as a node with its expansion as children.
• Every parse tree determines a unique leftmost derivation, obtained by walking the tree in preorder and expanding each node as it is reached.
• Two derivations determine the same tree exactly when they are permutations of one another.

So the map from derivations to trees is many-to-one, and the map from trees to leftmost derivations is a bijection. This is the reason “the grammar is unambiguous” is normally stated as “every string has at most one parse tree” rather than “at most one derivation”. Both statements are equivalent, but the tree formulation removes the expansion order, which was never semantically meaningful.

The tree also makes the distinction between a grammar and a language vivid. The set of parse trees of G is a syntactic object; the set of strings derived is the language L(G). Two different grammars can have the same language and different tree sets, and one can be ambiguous while the other is not. Ambiguity is a property of the grammar, and only derivatively of the language, when every grammar for that language is ambiguous.

Ambiguity is structural, and it has a local test

A grammar is ambiguous when some string in L(G) has two distinct parse trees. The classic witness is the expression grammar above, where a + a * a parses with the multiplication at the root or the addition at the root. The language is not ambiguous: a grammar with explicit precedence levels

E → E + T | T
T → T * F | F
F → (E) | a

generates the same set of strings with exactly one tree per string. The language {aⁱbʲcᵏ : i = j or j = k} is genuinely ambiguous, and every grammar for it is ambiguous, a result that follows from the structure of the language rather than from any particular rule set.

For context-free grammars, ambiguity is decidable in the narrow case of a single string: given G and w, build all parse trees for w by dynamic programming over substrings, and count them; the count is finite and computable. Deciding whether a grammar is ambiguous for some string is a different question, and it is undecidable, as Ambiguity, Equivalence, and Other Undecidable Grammar Questions sets out.

A grammar can also be defective in usefulness without being ambiguous: a nonterminal that derives no terminal string, or one unreachable from S, contributes rules that can never appear in a complete derivation. Eliminating such symbols is the first normalisation step, and it matters because a useless nonterminal can make a grammar look ambiguous or look infinite when it is neither.

Where the derivation view leaks into implementation

The gap between derivations and trees has a direct engineering consequence: a parser must choose a representation before it can be correct. Two common designs:

# A tiny recursive-descent recogniser: one function per nonterminal.
# This encodes the grammar's structure directly as call nesting.
def parse_E(tokens, i):
    i = parse_T(tokens, i)          # E -> T (E')
    while i < len(tokens) and tokens[i] == '+':
        i = parse_T(tokens, i + 1)  # E -> E + T, left-associative loop
    return i

def parse_T(tokens, i):
    i = parse_F(tokens, i)
    while i < len(tokens) and tokens[i] == '*':
        i = parse_F(tokens, i + 1)
    return i

def parse_F(tokens, i):
    if i < len(tokens) and tokens[i] == 'a':
        return i + 1
    if i < len(tokens) and tokens[i] == '(':
        j = parse_E(tokens, i + 1)
        if j < len(tokens) and tokens[j] == ')':
            return j + 1
    raise SyntaxError(f'expected atom at position {i}')

Recursive descent with a loop for left-associative operators commits to a tree shape at parse time. It cannot represent ambiguity because the call stack has exactly one interpretation at each point. A general algorithm such as CYK or Earley computes a table of all derivable substrings and can therefore enumerate every tree, which is why it handles ambiguous grammars but pays a cubic worst case, as described in Chomsky Normal Form and the CYK Table.

The same distinction appears in grammar transformation. Left recursion elimination rewrites A → Aα | β into A → βA′ and A′ → αA′ | ε, which preserves the language and the set of parse trees up to a re-association of nodes. It does not preserve the shape of the tree, and a tool that reports trees must know which grammar it is reporting on. Chomsky normal form, which splits long right sides into binary rules, preserves the language but multiplies tree depth, which is why a CYK table indexes by substring rather than by tree height.

A derivation is a proof that a string belongs to a language, and a parse tree is that proof with the order of steps erased. Everything else in the theory of context-free languages — normal forms, recognition algorithms, ambiguity tests — is a statement about which of the two objects is being preserved.