What is a ambiguous grammar? The following grammar generates prefix expressions with operands x and y binary operators +, -, and *: E → +EEE |*EE|-EE|x|y. (i) Find leftmost and rightmost derivatives and a derivation tree for the string +*-xyxy; (ii) Prove that this grammar is unambiguous.


Ambiguous Grammar: Ambiguous grammar is a context free grammar G such that some word has two parse trees. Some word has more than one rightmost derivation in an ambiguous grammar.
OR
Ambiguous grammar: A grammar G is said to be ambiguous if it has more than one parse tree (Left or Right derivation) for at least one string.

(i) E→ +EE
E → *EE
E → -EE
E → x
E → y
String = +*-xyxy

Left-most Derivation 
E → +EE
→ +*EEE
→ +*-EEEE
→ +*-xEEE
→ +*-xyEE
→ +*-xyxE
→ +*-xyxy

Right-most Derivation 
E → +EE
→ +*EEE
→ +*-EEEE
→ +*-EEEy
→ +*-EExy
→ +*-Eyxy
→ +*-xyxy
The derivation tree for this string is given below:

(ii) Now we can say that the grammar E → +EEE |*EE|-EE|x|y has a derivation tree where each string of this grammar has at least one parse tree. So we can say that the grammar is unambiguous.

1 comment:

Dear Members, Thanks for Your Comments. We must be reply your comment answer as soon as possible. Please Stay with us.....

Theme images by ideabug. Powered by Blogger.