two derivations not only yield the same sentence but also use exactly the same
productions. The difference is entirely in the order in which the productions are
applied. To remove such irrelevant factors, we often require that the variables be
replaced in a specific order.
Definition 5.2
A derivation is said to be leftmost if in each step the leftmost variable in the
sentential form is replaced. If in each step the rightmost variable is replaced, we
call the derivation rightmost.
Example 5.5
Consider the grammar with productions
Then
is a leftmost derivation of the string abbbb. A rightmost derivation of the same
string is
Derivation Trees
A second way of showing derivations, independent of the order in which
productions are used, is by a derivation or parse tree. A derivation tree is an
ordered tree in which nodes are labeled with the left sides of productions and in
which the children of a node represent its corresponding right sides. For