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.