Leftmost and Rightmost Derivations

At any stage during a parse, when we have derived some sentential form (that is not yet a sentence) we will potentially have two choices to make:

1. which non-terminal in the sentential form to apply a production rule to
2. which production rule for that non-terminal to apply

Eg. in the above example, when we derived $E\; OP\; E$, we could then have applied a production rule to any of these three non-terminals, and would then have had to choose among all the production rules for either $E$ or $OP$.

The first decision here is relatively easy to solve: we will be reading the input string from left to right, so it is our own interest to derive the leftmost terminal of the resulting sentence as soon as possible. Thus, in a top-down parse we always choose the leftmost non-terminal in a sentential form to apply a production rule to - this is called a leftmost derivation.

If we were doing a bottom-up parse then the situation would be reversed, and we would want to do apply the production rules in reverse to the leftmost symbols; thus we are performing a rightmost derivation in reverse.

For example, a bottom-up rightmost derivation would look like:

$$\begin{array}{rcl\vert r} \hline \multicolumn{3}{c}{Rule\; Ap... ...E\; OP\; E \\ E & \rightarrow & E\; OP\; E & E \\ \end{array}$$

Note that this has no effect on the parse tree; we still get:
=1.00mm