Which of the following is FALSE?

Concept

A context-free grammar is unambiguous when every generated string has exactly one parse tree. For a fixed parse tree there is exactly one leftmost derivation and exactly one rightmost derivation, but these derivations expand nonterminals in different orders.

Application

Test each statement using the defining parser or grammar property.

1. For S → aS | aSbS | ε, the string aab has two derivations: S ⇒ aS ⇒ aaSbS ⇒ aab and S ⇒ aSbS ⇒ aaSbS ⇒ aab. Their first productions differ, so the grammar is ambiguous.

2. For an unambiguous grammar, the leftmost derivation always expands the leftmost nonterminal, whereas the rightmost derivation always expands the rightmost nonterminal. They correspond to the same unique parse tree, but they are not the same derivation sequence.

3. An LR(k) grammar must give a conflict-free deterministic parsing action for each relevant state and k-symbol lookahead; an ambiguous grammar cannot meet that grammar property.

4. A recursive-descent parser begins at the start symbol and expands productions toward the input, so it is top-down.

Cross-check and contrast

• The grammar statement is supported by the two distinct derivations of aab.

• The unambiguous-grammar statement confuses a common parse tree with identical derivation order.

• The LR(k) statement follows from the requirement that the parsing table have no competing action.

• The recursive-descent statement follows from construction from the root toward leaves.

Therefore, the false statement is “An unambiguous grammar has same leftmost and rightmost derivation.”