ParseTrees ; Derivations &Ambiguity

Definition:
A parse Tree , derived by a grammar G=(V,Σ,R,S)  is a rooted,ordered tree in which

• Every leaf node is labeled with an element of Σ ⋃{𝛜},
• The root node labeled S
• Every other node is labeled with some element of V-Σ , and,
• If 'm' is a non leaf node labeled X and the children of m are labeled x1,x2,....,xm. then R contains the rule X→X₁,X₂,X₃....,Xn.

Definition : Parse tree is a grammatical structure of a string captured by a parse tree,Which records which rules were applied to which non terminals during the string's derivation.

Derivation:is one in which,at each step the leftmost/rightmost non-terminal in that working string is chosen for expansion of LMD &RMD respectively.

There are two useful families of derivation
A leftmost derivation: is one in which,at each step the leftmost non-terminal in that working string is chosen for expansion.

A rightmost derivation: is one in which,at each step the rightmost non-terminal in that working string is chosen for expansion.

 Ambiguity:
A grammar G is ambiguous iff there is at least one string in L(G) for which G produces more than one parse tree or more than one leftmost derivation or more than one rightmost derivation.

Example: Consider Balanced Parantheses grammar G:
S->(S)
   |SS
   |𝛜

If the grammar is ambiguous which can produce 2 parse trees for the string (( ))( ) .
 [ Note:These two parse trees are based on  left derivation]

                                         

Leftmost derivations(L.M.D):
Similarly we can produce  2 leftmost derivations which shows the grammar is ambiguous.
 [note:Every Step replace leftmost nonterminal by its correct R.H.S from rule that can yield the result]

1)   S⇒SS⇒(S)S⇒((S))S⇒(( ))(S)⇒(( ))( ) 
[note:Every Step replace leftmost nonterminal by its correct R.H.S that can yield the result]

2)  S⇒SS⇒SSS⇒SS⇒(S)S⇒((S))S⇒(( ))(S)⇒(( ))( )
Rightmost derivations(R.M.D):
Similarly we can produce  2 rightmost derivations which shows the grammar is ambiguous.
 [note:Every Step replace rightmost nonterminal by its correct R.H.S from rule  that can yield the result]
1)      S⇒SS⇒S(S)⇒ S()⇒(S)()⇒((S))()⇒(( ))( )

2)      S⇒SS⇒SSS⇒SS⇒S(S)⇒ S()⇒(S)()⇒((S))()⇒(( ))( )


Ex2:

Consider the grammar E→+EE|*EE|-EE|x|y
Find the L.M.D ,R.M.D and Parse Tree for input +*-xyxy.
L.M.D
E ⇒ +EE⇒+*EEE⇒+*-EEEE⇒+*-xEEE⇒+*-xyEE⇒+*-xyxE⇒+*-xyxy

Parse Tree (Based on L.M.D)



R.M.D   
E⇒+EE⇒+Ey⇒+*EEy⇒+*Exy⇒+*-EExy⇒+*-Eyxy⇒+*-xyxy


Parse Tree (Based on R.M.D)

 {Note: Both the parse trees are Same here)    

Ex3:Prove that it is ambiguous for input ibtibtaea for the grammar S→ iCtS | iCtSeS | a     C→b

1. LMD:  

                                                                       S⇒iCtS

⇒ibtS

⇒ibtiCtSeS

⇒ibtibtSeS

⇒ibtibtaeS

⇒ibtibtaea                               


2. LMD:

S⇒iCtSeS

⇒ibtSeS

⇒ibtiCtSeS

⇒ibtibtSeS⇒ibtibtaeS                       

⇒ibtibtaea

So we have two different parsetree & 2 diff LM.D for same input . Hence the Grammar is Ambiguous.

EX3:Eliminate the Ambiguity from the following expression grammar:

E->E+E
E->E*Eⁿ
E->(E)
E->id

The above grammar is unambiguous in 2 ways.
  1. It fails to specify associativity
       for eg: id+id+id can be parsed in (id+id)+id or id+(id+id) ways.
  2. It fails to define precedence hierarchy for the operators + &*. So for eg:
id+id*id can be parsed in (id+id)*id  or id+(id*id) ways.

So we have to rewrite the above rule as       E->E+T
                                                                      E->T
                                                                       T->T*F
                                                                       T->F
                                                                        F->(E)
                                                                         F->id.
Inherent Ambiguity:

There exist Context-Free languages for which no unambiguous grammar exists, We will call such languages inherently ambiguous.

Example1:

L={aⁿbⁿcm:n.m>=0} U{aⁿbⁿcm:n.m>=0}

Grammar rules for the language would be
S->S₁|S₂
S₁->S₁c|A
A->aAb|𝛜         /*generate all strings in {aⁿbⁿc^m:n.m>=0}*/
S₂->aS₂|B
B->bBc|𝛜         /*generate all strings in {aⁿb^mc^m:n.m>=0}*/

If we consider the strings   AⁿBⁿCⁿ ={aⁿbⁿcⁿ:n>=0} we have two distinct derivations one through S₁ & other through S₂ .
Hence the language is ambiguous.