Parsing / Context-Free Grammar/Leftmost and Rightmost Derivations
A derivation of a string for a grammar is a sequence of production rule applications.
The process of getting the string through the derivation is the parsing process.
For example, with the following grammar:
S → S + S (1)
S → 1 (2)
S → a (3)
The string $1 + 1 + a$ can be derived from the start symbol $S$ using 2 types of derivations: leftmost derivation and rightmost derivation.
Leftmost Derivation
In the leftmost derivation, the nonterminals are applied from left to right. Initially, we can apply rule 1 on the initial $S$:
$$
\rightarrow \underline{S + S} \qquad \text{(applied rule 1)}
$$
Next, the leftmost $S$ can be applied with rule 2:
$$
\rightarrow \underline{1} + S \qquad \text{(applied rule 2)}
$$
The next nonterminal is the second $S$. If we apply any of rule 2 or 3, there are still underived characters in the input string, so we choose rule 1 instead:
$$
\rightarrow 1 + \underline{S + S} \qquad \text{(applied rule 1)}
$$
Now, with the remaining characters from the input, we can apply rule 2 on the first $S$:
$$
\rightarrow 1 + \underline{1} + S \qquad \text{(applied rule 2)}
$$
Finally, the last $S$ can be applied with rule 3:
$$
\rightarrow 1 + 1 + \underline{a} \qquad \text{(applied rule 3)}
$$
The above derivation can be represented as the following parse tree:
Rightmost Derivation
In the rightmost derivation, the nonterminals are applied from right to left.
Initially, we can apply rule 1 on the initial $S$:
$$
\rightarrow \underline{S + S} \qquad \text{(applied rule 1)}
$$
This time, we apply rule 1 on the rightmost $S$:
$$
\rightarrow S + \underline{S + S} \qquad \text{(applied rule 1)}
$$
We found that rule 3 can be applied to the rightmost $S$:
$$
\rightarrow S + S + \underline{a} \qquad \text{(applied rule 3)}
$$
Next, we can apply rule 2:
$$
\rightarrow S + \underline{1} + a \qquad \text{(applied rule 2)}
$$
And finally, rule 2 can be applied again:
$$
\rightarrow \underline{1} + 1 + a \qquad \text{(applied rule 2)}
$$
This derivation can be represented as the following parse tree:
