# 02.11.2022 - 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: