Derivations in Top Down Parsing

Derivation is a process of generating a sentence using grammar

Terminology used in derivations

• Every string of symbols in the derivation is a sentential form
• A sentence is a sentential form that has only terminal symbols
• A rightmost derivation is the rightmost non-terminal in which each sentential form is expanded
• A derivation may be neither leftmost nor rightmost

The starting symbol is this grammar is <program>

The symbol => is read as "derives”

Each Successive string is the sequence derived from the previous string by replacing one of the non-terminals with one of its definitions

Each string in the derivation is called a sentential form

Leftmost derivation is the derivation where the leftmost non-terminal is replaced in the previous string

Derivation continues until the sentential form does not have any non-terminal

Example:
Obtain the leftmost and right most derivation for the following grammar

S→aS

S→aSbS

S→ε

Leftmost Derivation		Rightmost Derivation
S	S→aS	S
aS	S→aS	aSbS	S→aSbS
aaS	S→aSbS	aSbaSbS	S→έ
aaaSbS	S→έ	aSbaSb	S→aS
aaabS	S→aSbS	aSbaaSb	S→έ
aaabaSbS	S→aS	aSbaab	S→aS
aaabaaSbS	S→έ	aaSbaab	S→aS
aaabaabS	S→έ	aaaSbaab	S→έ
aaabaab	is derived	aaabaab	is derived

Share on Google Plus

About Data Sciences by Venu

Hi, My name is Venugopala Chary and I'm Currently working as Associate Professor in Reputed Engineerng College, Hyderabad. I have B.Tech and M.tech in regular from JNTU Hyderabad. I have 11 Years of Teaching Experience for both B.Tech and M.Tech Courses.