** Derivations**

A * derivation* is the process of deriving a
sentence from the
start symbol * S * according to a grammar, * i.e.*, the replacement of
nonterminal symbols by the right-hand sides of productions.

We use the symbol * ⇒ * to denote a derivation step.
* E ⇒ -E ⇒ -(E) ⇒ -(id) *
shows the steps in deriving the expression * -(id) * using an expression
grammar.

* ⇒ ^{*} * is used to denote
derivation in zero or more steps, while

In a * leftmost derivation*, the
leftmost nonterminal is replaced in
each step. If * S ⇒ ^{*}_{lm} α *,
then

In a * rightmost*
(or * canonical*) derivation, the rightmost
nonterminal is replaced in each step. A shift-reduce parser (* e.g.* YACC)
traces a rightmost derivation ``backwards''.