Derivation Tree

Derivation

Derivation is a sequence of production rules. It is used to get the input string through these production rules. During parsing we have to take two decisions. These are as follows:

• We have to decide the non-terminal which is to be replaced.
• We have to decide the production rule by which the non-terminal will be replaced.

We have two options to decide which non-terminal to be replaced with production rule.

Left-most Derivation

In the left most derivation, the input is scanned and replaced with the production rule from left to right. So in left most derivatives we read the input string from left to right.

Example:

Production rules:

S = S + S  
S = S - S  
S = a | b |c 

Input:

a - b + c

The left-most derivation is:

S = S + S  
S = S - S + S  
S = a - S + S  
S = a - b + S  
S = a - b + c

Right-most Derivation

In the right most derivation, the input is scanned and replaced with the production rule from right to left. So in right most derivatives we read the input string from right to left.

Example:

S = S + S  

S = S - S  

S = a | b |c  

Input:

a - b + c

The right-most derivation is:

S = S - S  
S = S - S + S  
S = S - S + c  
S = S - b + c  
S = a - b + c