4.2 Derivation, Parse Trees, and Ambiguity

A CFG defines a language by rewriting nonterminals. The sequence of rewrites is a derivation. The tree-shaped record of those rewrites is a parse tree. These are mathematical objects, but they also explain practical parser behavior: why a parser accepts a token stream, why a grammar may allow more than one meaning, and why compiler writers separate syntax trees from source text.

Let:

E -> E + T | T
T -> id

One derivation of id + id is:

E
=> E + T
=> T + T
=> id + T
=> id + id

The => relation means "derives in one production step." Its transitive closure is written =>*, meaning zero or more steps. We write:

E =>* id + id

to say that id + id belongs to the language generated by E.

Sentential Forms and Derivation Strategy

Every intermediate mixture of terminals and nonterminals is a sentential form. A derivation is not unique even when the final parse tree is the same. For the grammar above, after E => E + T, you may replace the left E first or the right T first.

A leftmost derivation always expands the leftmost nonterminal:

E
=> E + T
=> E + T + T
=> T + T + T
=> id + T + T
=> id + id + T
=> id + id + id

A rightmost derivation always expands the rightmost nonterminal:

E
=> E + T
=> E + id
=> E + T + id
=> E + id + id
=> T + id + id
=> id + id + id

Both generate the same sentence. The choice matters because parsing algorithms mirror these strategies in different ways. Top-down parsing is easiest to describe using leftmost derivations. Bottom-up LR parsing reconstructs a rightmost derivation in reverse. You do not need to memorize that slogan yet, but it explains why future chapters use the same grammar from different directions.

Parse Trees Preserve Hierarchy

A parse tree is a rooted, ordered tree:

• The root is the start symbol.

• Every internal node is a nonterminal.

• The children of an internal node are the symbols on the right-hand side of the production used at that node.

• The leaves, read from left to right, form the final terminal sentence.

For id + id * id, a parse tree records whether multiplication groups inside the right operand of addition, or whether addition groups inside the left operand of multiplication. That grouping is not cosmetic. It determines what program the compiler will eventually execute.

The parse tree also contains syntactic scaffolding that later compiler stages may not need: punctuation terminals, grammar-only nonterminals, and repeated list nodes. An abstract syntax tree (AST) usually removes that scaffolding. For example:

Concrete parse-tree idea:
Expr -> Expr + Term
Term -> Term * Factor
Factor -> id

Possible AST:
Add(Identifier("a"), Multiply(Identifier("b"), Identifier("c")))

The parse tree proves how the grammar was used. The AST captures the semantic structure that type checking and code generation care about. Chapter 7 will return to this distinction in implementation detail.

A Parse Tree Is Not an Evaluation Order

Do not confuse grouping with execution order. A parse tree normally determines syntactic association, such as a + (b * c). It does not by itself specify every runtime rule. Function-call argument order, short-circuit behavior, overflow, and side effects must be defined by the language semantics. A compiler can build a perfectly correct parse tree and still need semantic rules before it knows what behavior is allowed.

Ambiguity Means More Than One Parse Tree

A grammar is ambiguous if at least one terminal string has two distinct parse trees, equivalently two distinct leftmost derivations. The classic expression grammar:

E -> E + E | E * E | id

is ambiguous. The string:

id + id * id

can mean either:

id + (id * id)

or:

(id + id) * id

If the language specification does not choose between them, different parsers or parser-generator conflict resolutions can make different decisions. That is a language-design bug, not merely an implementation inconvenience.

One way to encode precedence is to use grammar levels:

Expr   -> Expr + Term | Term
Term   -> Term * Factor | Factor
Factor -> id | ( Expr )

Here * belongs lower in the tree, under Term, so it binds more tightly than +. Left-recursive productions also encode left associativity: a - b - c groups as (a - b) - c. For right-associative operators such as exponentiation in many languages, the grammar shape must be different.

Another famous ambiguous pattern is the dangling else:

Stmt -> if Expr then Stmt
      | if Expr then Stmt else Stmt
      | other

For nested conditionals, an else can attach to more than one if. Many languages resolve this by convention ("attach to the nearest unmatched if"), while some grammars split statements into matched and unmatched categories to remove the ambiguity structurally.

How to Diagnose a Grammar Before Coding a Parser

Before writing parser code, ask concrete questions:

1. Can one token sequence have more than one parse tree?

2. Does the grammar encode the intended precedence and associativity?

3. Do optional and repeated constructs have obvious boundaries?

4. Does the start symbol require the entire input, including EOF?

5. Is every syntactic distinction that later semantic analysis needs visible in the tree?

Testing grammars with small counterexamples is more valuable than staring at productions. Write strings such as a-a-a, a+b*c, nested if statements, empty argument lists, trailing commas, and unmatched delimiters. For each one, draw or enumerate the possible trees. A grammar that looks compact can still hide a serious ambiguity.

Make Ambiguity Visible With a Witness

a - b - c is a useful witness because its two groupings, (a-b)-c and a-(b-c), are easy to draw and may produce different answers. If a grammar permits both trees, it has described two programs. Precedence declarations and grammar levels therefore define source-language meaning; they do not merely silence a parser warning.

When a grammar looks suspicious, write a derivation and draw the smallest tree before changing code. A token sequence alone hides the hierarchy the grammar is responsible for defining.