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

Step 1: Understanding top-down parsing.
Top-down parsers begin parsing from the start symbol and try to generate the input string by expanding non-terminals.
Step 2: Direction of derivation.
In top-down parsing, the leftmost non-terminal is always expanded first, while the input is scanned from left to right.
Step 3: Distinguishing from bottom-up parsing.
Bottom-up parsers construct a rightmost derivation in reverse, which is not the case here.
Step 4: Final conclusion.
Hence, a top-down parser uses a leftmost derivation.

Answer 2

A top-down parser starts at the grammar's start symbol and tries to expand it step by step until it matches the input string, scanning that input left to right. Let's check each option against how top-down expansion actually proceeds:

1. Leftmost derivation: At each step, a top-down parser expands the leftmost non-terminal in its current working string first, since it needs to match the input it has seen so far before deciding how to expand anything further to the right. This produces a leftmost derivation directly, in forward order.
2. Leftmost derivation traced out in reverse: "Reverse" would mean the derivation steps are discovered in the opposite order they were applied, which describes how a bottom-up parser reconstructs a derivation (by reducing), not how a top-down parser builds one, which expands forward, in the same order it commits to each step.
3. Rightmost derivation: This would mean the parser always expands the rightmost non-terminal first, but that would leave the leftmost part of the string (which needs to be matched against the already-scanned input) undetermined for longer, which doesn't fit how top-down parsing checks input as it goes.
4. Rightmost derivation traced out in reverse: This is the actual definition of what a bottom-up (shift-reduce) parser constructs, since it builds the parse tree from the leaves upward and only recognizes the full rightmost derivation once traced backward. It is not what a top-down parser does.

The direction of expansion (always leftmost non-terminal first, in forward order) matches only one option.

Therefore, the correct answer is Leftmost derivation.