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

Context Free Grammar

Home

Parse Trees