Topic: Compiler Design
For the same input string, which of the following options is true in the case of ambiguous grammar?
(i) two different parse trees
(ii) two leftmost derivations
(iii) two rightmost derivations
(iv) leftmost and rightmost derivations are different
Which one is correct?
- A. (i), (ii), (iii) are true; (iv) is false
- B. (i) is true; (ii), (iii), (iv) are false
- C. (i), (iv) are true; (ii), (iii) are false
- D. (i) is false; (ii), (iii), (iv) are true
Answer: A. (i), (ii), (iii) are true; (iv) is false
Explanation: An ambiguous grammar is defined as having more than one valid parse tree for the same input string. Having multiple parse trees automatically implies there are multiple leftmost derivations and multiple rightmost derivations for that string. However, statement (iv) 'leftmost and rightmost derivations are different' is naturally true for almost any string with multiple non-terminals even in unambiguous grammars, so it is not a defining characteristic of ambiguity (thus considered 'false' in distinguishing ambiguity).