Derivation Tree

Also known as parse tree. Represents the hierarchical structure of a derivation from a CFG.

Structure:

• Root
  Start symbol $S$.
• Internal nodes
  Non-terminals.
• Leaves
  Terminals or $\Lambda$.

Reading leaf nodes left-to-right gives the derived string (the yield of the tree).

Types of Derivations

Leftmost Derivation

Always replace the leftmost non-terminal first.

Rightmost Derivation

Always replace the rightmost non-terminal first.

Each derivation tree corresponds to exactly 1 leftmost derivation and exactly 1 rightmost derivation.

Example

Grammar:

• $S \to S + S \mid S * S \mid a$

Deriving $a + a * a$ leftmost:

The corresponding derivation tree has $S$ at the root, with children $S$, $+$, $S$. The right $S$ has children $S$, $*$, $S$.

Ambiguity

A grammar is ambiguous iff some string has 2 or more distinct derivation trees (equivalently, 2 distinct leftmost derivations).

For $a + a * a$ under the grammar above, a 2nd tree exists where the root $S$ splits as $S * S$ instead. Both trees are valid, so the grammar is ambiguous.