Aka. parse tree. Represents the hierarchical structure of a derivation.
- Root: start symbol
- Internal nodes: non-terminals
- Leaves: terminals
Reading the leaf nodes left-to-right gives the derived string.
Types of Derivations
Leftmost Derivation
Always replace the leftmost non-terminal.
Rightmost Derivation
Always replace the rightmost non-terminal.
Each derivation tree corresponds to one unique leftmost derivation and one unique rightmost derivation.