Lecture 2 Parse Tree

Parse Trees
--Sakshi Surve
Basics of Grammar :
A language is set of strings over a set of symbols
Language --- Finite set of sentences

Sentence --- Finite set of words
Words --- Finite set of Alphabets / Symbols
Grammar is essential to give syntactical structure to the

language
Grammar is the set of rules used to describe string of Language
The language may be Programming language or natural

language …Any type will require grammar
Alphabets
Words
Grammar
Sentences
Example :
If we want English statement “Dog Runs” ….We may use following rules :
<Sentence>  <Noun> <Verb>
<Noun>  Dog
< Verb >  Runs

 Dog Runs
These rules indicate how the sentence of the form ‘Noun’ followed by
‘Verb’ can be generated.
There are many such rules of the language and they are collectively called
the Grammar for the language
Constituents of Grammar :
Two Symbols :
Terminals
Non Terminals
Terminals are part of the generated sentence

E.g. In the above example, ‘Dog’ and ‘Runs’ are terminal
symbols as they collectively formulate the statement and
are part of the statement
Non Terminals take part in the formation of the
statement , but are not part of the generated sentence.
No statement that is generated using grammar will contain

Non Terminals in it.
 E.g. In above example , ‘Sentence’ , ‘Noun’ , ‘Verb’ are Non-
terminals…which are not in the generated statement but
took part on the formation of the statement
 Dog Runs
Thus, Non-terminals are essential while declaring the rules

These rules are called as ‘Productions’ or ‘Production
Rules’
Formal Definition :
Like a natural language has Constituents like Nouns, Verbs,
Adjectives etc….
Two Constituents :
Terminals
Non terminals
This grammar that is based on Constituent structure is

called Constituent Structure Grammar Or Phrase
Structure Grammar
The idea is …Basing a grammar on Constituent

structure blocks
Summary :
If we want English statement “Dog Runs” ….We may use
following rules :
<Noun>  Dog
< Verb >  Runs
We have to begin with rule ….<Sentence>  <Noun> <Verb>

Start Symbol ……………..Sentence
Non Terminals…..Sentence, Noun, Verb
Terminals…….Dog ,Runs
Rules……indicating how the sentence can be generated.
Grammar :
A Grammar G is a four tuple collection G = (V, T, P, S)
….Where
 V is the (finite) set of variables or Non terminals ….They

take part in the derivation , but are not part of the derived
sentence
T is a finite set of Terminals, i.e., the symbols that form the

strings of the language being defined
P is a finite set of Production Rules
S is the Start Symbol (One of the Non terminals )

In the example before :
S = Sentence
V = { Noun , Verb}
T = {Dog , Runs }
P
<Sentence>  <Noun> <Verb>
<Noun>  Dog
< Verb >  Runs
Example :
G = { S, V, P, T }
T = { Man, Book, Reads, The }

V = { N, V ,A}
S = S
P
S  ANVN
A  A | An | The
N  Man | Book
V  Reads
Derive string “ The Man Reads Book”
Derivation …. S  ANVN
A  A | An | The
S ANVN N  Man | Book
The NVN V  Reads
 The Man VN
The Man Reads Book
 The Man Reads N
 The Man Reads Book
Leftmost Derivation
Derivation …. S  ANVN
A  A | An | The
S ANVN
N  Man | Book
 ANV Book V  Reads
 AN Reads Book
 A Man Reads Book The Man Reads Book
 The Man Reads Book
Rightmost Derivation
∑ = { a , b }
L = { w € L | w begins with a }
L = { a , aa, ab, aab, aba, aaa, ………}
S -> aA
A -> aA | bA | €
For ‘a’
Derivation of ‘a’
S aA
S a
a A
€
S -> aA
A -> aA | bA | €
For generating ‘aa’
 S
a A
Derivation of ‘aa’
S aA
a A aaA
aa
€
S -> aA Derivation of ‘aba’
A -> aA | bA | € S aA
abA
For generating ‘aba’ abaA
aba
 S
a A
b A
In this grammar, the tuples are :
a A V = {S, A}
T = { a,b }
€ P
S= S
Parser :
Parser is a component of a Compiler or Interpreter that
breaks data into smaller elements
Parser takes the input in the form of a sequence of tokens

and builds a data structure in the form of a tree called
Parse tree
Deriving a Syntactic tree like structure from the stream of

tokens is called Parsing
Parsing is a process of determining if a string of tokens can

be generated by a grammar
Parse Tree :
The process of deriving a string using grammar rules is
called as derivation.
The geometrical representation of a derivation is

called as a parse tree or derivation tree.
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 1 :
Consider the following example :
S → aB / bA
A → aS / bAA / a
B → bS / aBB / b
Let us consider a string

w = aaabbabbba
Now, let us derive the string w using leftmost derivation.

S → aB / bA
A → aS / bAA / a
Leftmost Derivation - B → bS / aBB / b
S → aB
aaabbabbba
→ 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)
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 1 :
Consider the following grammar-
S → aB / bA
S → aS / bAA / a
B → bS / aBB / b
Let us consider a string w = aaabbabbba
Now, let us derive the string w using rightmost

derivation.
S → aB / bA
A → aS / bAA / a
Rightmost Derivation- B → bS / aBB / b
aaabbabbba
S → aB
→ ab (Using B → b)
This is NOT what we want …………….

S → aB / bA
A → aS / bAA / a
aaabbabbba
S → aB
→ a bS (Using B → bS)
→ abbA (Using S → bA)
→ abba (Using A → a)

S → aB / bA
A → aS / bAA / a
S → aB aaabbabbba
→ aaBbS (Using B → bS)
→ aaBbbA (Using S → bA)
→ aaBbba (Using A → a )
→ aaaBBbba (Using B → aBB)
→ aaaBbbba (Using B → b )
→ aaabSbbba (Using B → bS)
→ aaabbAbbba (Using S → bA)
→ aaabbaSbbba (Using A → aS)

S → aB / bA
A → aS / bAA / a

aaabbabbba
S → aB
→ 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)
Parse 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.
Example 2:

Consider the grammar-
S → bB / aA
A → b / bS / aAA
B → a / aS / bBB

For the string w = bbaababa, find-
1. Leftmost derivation
2. Rightmost derivation
3. Parse Tree
Solution :

1. Leftmost Derivation- 2. Rightmost Derivation-

S → bB S → bB
→ bbBB (Using B → bBB) → bbBB (Using B → bBB)
→ bbaB (Using B → a) → bbBaS (Using B → aS)
→ bbBabB (Using S → bB)
→ bbaaS (Using B → aS)
→ bbBabaS (Using B → aS)
→ bbaabB (Using S → bB) → bbBababB (Using S → bB)
→ bbaabaS (Using B → aS) → bbBababa (Using B → a)
→ bbaababB (Using S → bB) → bbaababa (Using B → a)
→ bbaababa (Using B → a)
Example 3 :
Consider the grammar-
S → A1B
A → 0A / ∈
B → 0B / 1B / ∈

For the string w = 00101, find-
Leftmost derivation
Rightmost derivation
Parse Tree

Solution-
1. Leftmost Derivation- 2. Rightmost Derivation-

S → A1B S → A1B
→ 0A1B (Using A → 0A) → A10B (Using B → 0B)
→ 00A1B (Using A → 0A) → A101B (Using B → 1B)
→ 001B (Using A → ∈) → A101 (Using B → ∈)
→ 0010B (Using B → 0B) → 0A101 (Using A → 0A)
→ 00101B (Using B → 1B) → 00A101 (Using A → 0A)
→ 00101 (Using B → ∈) → 00101 (Using A → ∈)

Parse Tree :
Example :
Let any set of production rules in a CFG be
X → X+X | X*X |X| a
over an alphabet {a}.
Show derivation for the string "a+a*a"

X → X+X
X X*X
XX
X a
The leftmost derivation for the string "a+a*a" may

be −
X → X+X
→ a+X
→ a + X*X
→ a+a*X
→ a+a*a
The stepwise derivation of the above string
is shown as below −
X → X+X
X X*X
XX
X a
The rightmost derivation for the above
string "a+a*a" may be −
X → X*X
→ X*a
→ X+X*a
→ X+a*a
→ a+a*a
The stepwise derivation of the above string is shown as below −

Lecture 2 Parse Tree

Uploaded by

Copyright:

Available Formats

Lecture 2 Parse Tree

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Lecture 2 Parse Tree

Uploaded by

Copyright:

Available Formats

Parse Trees

Language --- Finite set of sentences

Grammar is essential to give syntactical structure to the

Grammar is the set of rules used to describe string of Language

The language may be Programming language or natural

<Sentence>  <Noun> <Verb>

Terminals are part of the generated sentence

No statement that is generated using grammar will contain

Thus, Non-terminals are essential while declaring the rules

This grammar that is based on Constituent structure is

The idea is …Basing a grammar on Constituent

We have to begin with rule ….<Sentence>  <Noun> <Verb>

 V is the (finite) set of variables or Non terminals ….They

T is a finite set of Terminals, i.e., the symbols that form the

P is a finite set of Production Rules

S is the Start Symbol (One of the Non terminals )

T = { Man, Book, Reads, The }

Parser takes the input in the form of a sequence of tokens

Deriving a Syntactic tree like structure from the stream of

Parsing is a process of determining if a string of tokens can

The geometrical representation of a derivation is

The geometrical representation of leftmost derivation

Let us consider a string

Now, let us derive the string w using leftmost derivation.

The geometrical representation of rightmost

Now, let us derive the string w using rightmost

This is NOT what we want …………….

This is NOT what we want …………….

This is NOT what we want …………….

Show derivation for the string "a+a*a"

The leftmost derivation for the string "a+a*a" may

You might also like