Scribd
Upload
18 views

Compiler Construction (CS4623) : Course Instructor: Ms. Tayyaba Zaheer

Uploaded by

Hammad Ullah
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
18 views

Compiler Construction (CS4623) : Course Instructor: Ms. Tayyaba Zaheer

Uploaded by

Hammad Ullah
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 16

Compiler Construction

(CS4623)
Course Instructor: Ms. Tayyaba Zaheer

Department of Computer Science,


Capital University of Science and Technology, Islamabad
Fall Semester, 2024
Compiler Construction
Lecture # 07 – Part 01
Topics
• Derivation – 2 types
• Leftmost Derivation
• Rightmost Derivation

• Ambiguous Grammar

3
Sentence Form
• A Production that does not contain any non-
terminal is in Sentence Form

• Example:

4
Sentential Form
• Combination of Terminals and Non-terminals

• If the Production contain one or more non-


terminal, it is called Sentential Form

• Example:

5
Derivation
• The action of obtaining something from a source
is called derivation
• Example:

Input String: abc


6
Derivation
Derivation

Leftmost Derivation Rightmost Derivation

Replace the leftmost non-terminal Replace the rightmost non-terminal


On each step On each step

7
Derivation
Leftmost Derivation Rightmost Derivation
Leftmost derivation is the Rightmost derivation is the
one in which you always one in which you always
expand the leftmost non- expand the rightmost non-
terminal terminal

8
Derivation - Examples

String: abbcd

9
Leftmost Derivation

String: abbcd

10
Parse Tree S

d
a B C

B b c

11
Rightmost Derivation

String: abbcd

12
Parse Tree S

d
a B C

B b c

13
Leftmost Derivation

String: x+y*z

14
Rightmost Derivation

String: x+y*z

15
Ambiguous Grammar
• Definition # 01
• If there exist two different leftmost derivation for a given
string, this type of grammar is said to be Ambiguous
Grammar.

• Definition # 02
• If there exist two different parse trees for a given string,
this type of grammar is called Ambiguous Grammar.

16

You might also like