Question

Which one of the following derivations does a top-down parser use while parsing an input string? The input is assumed to be scanned from left to right.

• A. Leftmost derivation
• B. Leftmost derivation traced out in reverse
• C. Rightmost derivation
• D. Rightmost derivation traced out in reverse

Hint:

Top-down parsing corresponds to leftmost derivation, while bottom-up parsing corresponds to rightmost derivation in reverse.

Answer 1

The Correct Option is A

A top-down parser builds the parse tree from the root downward, trying to match the input as it goes. Since the input is scanned left to right, the parser must always decide how to expand whichever non-terminal is furthest to the left in its current partial string, that's the part it needs to resolve next to keep matching.
Doing this repeatedly, step after step, produces exactly a leftmost derivation, in the same forward order the parser commits to its choices.
Bottom-up parsers are the ones associated with a rightmost derivation (built in reverse), not top-down parsers.
So the correct answer is leftmost derivation.

Answer 2

It helps to remember that parsing strategies pair up with derivation types in a fixed way, and to check top-down against each pairing:

1. Leftmost derivation: Top-down parsers (like recursive descent or LL parsers) are built to always expand the leftmost pending non-terminal, which is the standard pairing: top-down parsing produces a leftmost derivation, read forward.
2. Leftmost derivation, reverse order: No standard parsing strategy is described this way, the "in reverse" qualifier belongs to how bottom-up parsers relate to the rightmost derivation, not to top-down parsers and leftmost derivations.
3. Rightmost derivation: This is associated with bottom-up (LR-style) parsers, which don't decide on the parse tree structure top-down at all, so it's the wrong pairing for a top-down parser.
4. Rightmost derivation, reverse order: This is precisely how bottom-up (shift-reduce/LR) parsers are described, they build a rightmost derivation, but the order in which they discover it is the reverse of the derivation order.

Top-down parsing pairs with exactly one of these four descriptions.

Therefore, the correct answer is Leftmost derivation.