Derivations
The parse tree shows the structure, but it does not tell us in exactly
what order the productions were applied. The following example
shows the expression grammar and one derivation of a + a * a.
(E stands for expression, T for term and F for
factor. The number above each arrow is the number of the production
applied.
A left derivation replaces the left-most nonterminal at each step
of the derivation, while a right derivation replaces the
right-most nonterminal at each step
Parsing reverses the derivation process: given an input string, the parser
has to "discover" a derivation (if any).
