ParseTrees ; Derivations &Ambiguity
Definition:
A parse Tree , derived by a grammar G=(V,Σ,R,S) is a rooted,ordered tree in which
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)
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.
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.
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.
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:
⇒ibtS
S⇒iCtSeS
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ⁿcm:n.m>=0}*/
S₂->aS₂|B
B->bBc|𝛜 /*generate all strings in {aⁿbmcm:n.m>=0}*/
If we consider the strings AⁿBⁿCn ={aⁿbⁿcn:n>=0} we have two distinct derivations one through S₁ & other through S₂ .
Hence the language is ambiguous.
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:
2. LMD:
⇒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ⁿcm:n.m>=0}*/
S₂->aS₂|B
B->bBc|𝛜 /*generate all strings in {aⁿbmcm:n.m>=0}*/
If we consider the strings AⁿBⁿCn ={aⁿbⁿcn:n>=0} we have two distinct derivations one through S₁ & other through S₂ .
Hence the language is ambiguous.
Comments
Post a Comment