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 &rArr to denote a derivation step. E &rArr -E &rArr -(E) &rArr -(id) shows the steps in deriving the expression -(id) using an expression grammar.
&rArr* is used to denote derivation in zero or more steps, while &rArr+ is used to denote derivation in one or more steps.
In a leftmost derivation, the leftmost nonterminal is replaced in each step. If S &rArr*lm &alpha , then &alpha is called a left-sentential form of the grammar G . A leftmost derivation is traced by a predictive, top-down parser.
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''.