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 placed with production rule.

1. Leftmost Derivation:

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

Example:

Production rules:

E = E + E  

E = E - E  

E = a | b  

Input

a - b + a  

The leftmost derivation is:

E = E + E  

E = E - E + E  

E = a - E + E  

E = a - b + E  

E = a - b + a  

2. Rightmost Derivation:

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

Example

Production rules:

E = E + E  

E = E - E  

E = a | b  

Input

a - b + a  

The rightmost derivation is:

E = E - E  

E = E - E + E  

E = E - E + a  

E = E - b + a  

E = a - b + a  

When we use the leftmost derivation or rightmost derivation, we may get the same string. This type of derivation does not affect on getting of a string.

Examples of Derivation:

Example 1:

Derive the string "abb" for leftmost derivation and rightmost derivation using a CFG given by,

S → AB | ε  

A → aB  

B → Sb  

Leftmost derivation:

Rightmost derivation:

Example 2:

Derive the string "aabbabba" for leftmost derivation and rightmost derivation using a CFG given by,

S → aB | bA  

 S → a | aS | bAA  

S → b | aS | aBB  

Solution:

Leftmost derivation:

S  

aB            S → aB      

aaBB          B → aBB  

aabB          B → b  

aabbS         B → bS  

aabbaB        S → aB  

aabbabS       B → bS  

aabbabbA      S → bA  

aabbabba      A → a  

Rightmost derivation:

S  

aB            S → aB      

aaBB          B → aBB  

aaBbS         B → bS  

aaBbbA        S → bA  

aaBbba        A → a  

aabSbba       B → bS  

aabbAbba      S → bA  

aabbabba      A → a  

Example 3:

Derive the string "00101" for leftmost derivation and rightmost derivation using a CFG given by,

S → A1B  

A → 0A | ε  

B → 0B | 1B | ε  

Solution:

Leftmost derivation:

S  

A1B  

0A1B  

00A1B  

001B  

0010B  

00101B  

00101  

Rightmost derivation:

S  

A1B  

A10B  

A101B  

A101  

0A101  

00A101  

00101