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

Comments

Post a Comment

Popular posts from this blog

What is the Difference between Scanning and Parsing

-
Image
  What is the Difference between Scanning and Parsing The main difference between scanning and parsing is that scanning is the process of reading the source code one character at a time in a methodical manner to convert them into tokens while parsing is the process of taking the tokens and generating a parse tree as the output. Generally, a compiler is a software program that is capable of converting the source code into machine code so that the computer can execute that machine code. The compiler goes through multiple phases to compile a program. Scanning and parsing are two activities that occur during this compilation process. Overall, scanning occurs at the lexical analysis phase, whereas parsing occurs at the syntax analysis phase. Furthermore, the lexical analyzer performs scanning while the parser performs parsing.
Read more

Syntax Tree

-
Image
Download pdf What is Syntax Tree? Tree in which each leaf node describes an operand & each interior node an operator. The syntax tree is shortened form of the Parse Tree. Example1  − Draw Syntax Tree for the string a + b ∗ c − d. Rules for constructing a syntax tree Each node in a syntax tree can be executed as data with multiple fields. In the node for an operator, one field recognizes the operator and the remaining field includes a pointer to the nodes for the operands. The operator is known as the label of the node. The following functions are used to create the nodes of the syntax tree for the expressions with binary operators. Each function returns a pointer to the recently generated node. ·         mknode (op, left, right)  − It generates an operator node with label op and two field including pointers to left and right. ·         mkleaf (id, entry)  − It generates an identifie...
Read more