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.
great thankyou :)
ReplyDelete