Leftmost Derivation and Rightmost Derivation

Leftmost Derivation and Rightmost Derivation

AU: May-13,16, Dec.-10,15,18, Marks 9

• The leftmost derivation is a derivation in which the leftmost non-terminal is replaced first from the sentential form.

• The rightmost derivation is a derivation in which rightmost non-terminal is replaced first from the sentential form.

• For example

S → XYX

S → aYX

S → abX

S → aba

S → XYX

S → XYa

S → Xba

S → aba

Leftmost derivation Rightmost derivation

Note that we have replaced first X from left to right in leftmost derivation and XYX the last X i.e. the rightmost symbol.

Examples for Understanding

Example 3.5.1 Let, G be the grammar

S → aB | bA

A → a | aS | bAA

B → b | bS | aBB

For the string baaabbabba. Find leftmost derivation, rightmost derivation and Parse tree. AU: Dec.-10, Marks 9

Solution :

PPPPPPPPPPPPPPPPPPPPPPPPPPP

Example 3.5.2 Consider the following productions

S → aB bA

A → a | aS | bAA

B → b | bS | aBB

For the string aaabbabbba, Find

1) Leftmost derivation

2) Rightmost derivation

3) Parse tree AU May-13, Marks 8

Solution: For leftmost derivation and parse tree refer answer of Q.10 from Two Marks Questions with Answers

Rightmost Derivation :

Pppppppppppppppppppppppp

 

Example 3.5.3 Given the grammar G = (V, Σ, R, E) where

V = {E, D, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, +, -, *, /, ()},

Σ = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0, +, -, *, /, ()}, and R contains the following rules:

E→D|(E)| E+ E |E + E| E* E |E| E / E

D → 0|1|2|3| ...9

find a parse tree for the string 1+2*3. AU: Dec. 15, Marks 6

Solution: The parse tree

pppppppppppppppppppppppppppppppp

Example 3.5.4 Show the derivation steps and construct derivation tree for the string 'ababbb' by using leftmost derivation with the grammar.

S → ABIɛ

A → aB

B → Sb. AU May-16, Marks 5

Solution :

Ppppppppppppppppppppppppppppppppp

Example 3.5.5 Consider the context free grammar (CFG) given below. Give the leftmost derivation for the string bbaa using the grammar.

S → bS | aT | ε

T → aT | bU | ε

U → aT | ɛ

AU Dec.-18, Marks 2

Solution :

pppppppppppppppppppppppppppp