Which of the following is FALSE ?
2016
Which of the following is FALSE ?
- A.
The grammar S → aS|aSbS|∈, where S is the only non-terminal symbol, and ∈ is the null string, is ambiguous.
- B.
An unambiguous grammar has same left most and right most derivation.
- C.
An ambiguous grammar can never be LR(k) for any k.
- D.
Recursive descent parser is a top-down parser.
Attempted by 80 students.
Show answer & explanation
Correct answer: B
Answer: The false statement is "An unambiguous grammar has same left most and right most derivation."
Explanation:
The grammar S → aS | aSbS | ε is ambiguous. Example: the string aab has two different leftmost derivations, showing ambiguity.
Leftmost derivation 1: S ⇒ aSbS ⇒ a aS b S ⇒ a a b
Leftmost derivation 2: S ⇒ aS ⇒ a aSbS ⇒ a a b
Why the highlighted statement is false: An unambiguous grammar means each string has exactly one parse tree, which yields exactly one leftmost derivation and exactly one rightmost derivation. However, those two derivations are not required to be identical sequences of sentential forms; they are different derivation orders that correspond to the same unique parse tree.
An ambiguous grammar can never be LR(k) for any k because LR(k) parsing is deterministic and produces a unique parse; any grammar that is LR(k) must therefore be unambiguous.
A recursive descent parser is a top-down parser: it starts from the start symbol and expands nonterminals using recursive procedures, predicting productions as it goes down the parse tree.