Derivation & Derivation Tree in Compiler Design (Left Most Derivation & Right Most Derivation)

 Download pdf

Derivation

 

·         The process of deriving a string is called as derivation.

·         The geometrical representation of a derivation is called as a parse tree or derivation tree.

1. Leftmost Derivation-

 

·         The process of deriving a string by expanding the leftmost non-terminal at each step is called as leftmost derivation.

·         The geometrical representation of leftmost derivation is called as a leftmost derivation tree.

 

Example-

 

Consider the following grammar-

S → aB / bA

A → aS / bAA / a

B → bS / aBB / b

(Unambiguous Grammar)

 

Let us consider a string w = aaabbabbba

Now, let us derive the string w using leftmost derivation.

 

Leftmost Derivation-

 

S   → aB

→  aaBB                   (Using B → aBB)

→ aaaBBB                (Using B → aBB)

→ aaabBB                (Using B → b)

→ aaabbB                (Using B → b)

→ aaabbaBB            (Using B → aBB)

→ aaabbabB            (Using B → b)

→ aaabbabbS          (Using B → bS)

→ aaabbabbbA        (Using S → bA)

→ aaabbabbba         (Using A → a)

 

 

2. Rightmost Derivation-

 

·         The process of deriving a string by expanding the rightmost non-terminal at each step is called as rightmost derivation.

·         The geometrical representation of rightmost derivation is called as a rightmost derivation tree.

 

Example-

 

Consider the following grammar-

S → aB / bA

A → aS / bAA / a

B → bS / aBB / b

(Unambiguous Grammar)

 

Let us consider a string w = aaabbabbba

Now, let us derive the string w using rightmost derivation.

 

Rightmost Derivation-

 

S   → aB

→  aaBB                    (Using B → aBB)

→ aaBaBB                 (Using B → aBB)

→ aaBaBbS               (Using B → bS)

→ aaBaBbbA             (Using S → bA)

→ aaBaBbba              (Using A → a)

→ aaBabbba              (Using B → b)

→ aaaBBabbba          (Using B → aBB)

→ aaaBbabbba          (Using B → b)

→ aaabbabbba           (Using B → b)

 

 

NOTES ·         For unambiguous grammars, Leftmost derivation and Rightmost derivation represents the same parse tree. ·         For ambiguous grammars, Leftmost derivation and Rightmost derivation represents different parse trees.

 

Here,

·         The given grammar was unambiguous.

·         That is why, leftmost derivation and rightmost derivation represents the same parse tree.

 

Leftmost Derivation Tree = Rightmost Derivation Tree

 

 

Properties Of Parse Tree

 

·         Root node of a parse tree is the start symbol of the grammar.

·         Each leaf node of a parse tree represents a terminal symbol.

·         Each interior node of a parse tree represents a non-terminal symbol.

·         Parse tree is independent of the order in which the productions are used during derivations.

 

Yield Of Parse Tree-

 

·         Concatenating the leaves of a parse tree from the left produces a string of terminals.

·         This string of terminals is called as yield of a parse tree.

Download pdf