Which of the following derivations does a top-down parser use while parsing an input string? The input is scanned from left to right.
View worked solution
Answer: A
A top-down parser constructs the parse tree from the root (the start symbol) down to the leaves (the terminal symbols).
When the input is scanned from left to right:
- To match the input tokens sequentially, the parser must always expand the leftmost non-terminal in the current sentential form first.
- This process of always replacing the leftmost non-terminal at each step is called a Leftmost Derivation (LMD).
For comparison:
- Bottom-up parsers (such as LR parsers) scan the input from left to right and construct the parse tree from the leaves up to the root. This corresponds to a Rightmost Derivation traced out in reverse (RMD in reverse).
Therefore, a top-down parser uses a Leftmost derivation.
Free practice · Your answers on this page are not saved.