A top-down parser, during parsing, uses a leftmost derivation of the input string. The leftmost derivation is a derivation in which the leftmost non-terminal is replaced at each step.
Explanation:
-
Leftmost Derivation: In a leftmost derivation, at each step, the leftmost non-terminal in the current sentential form is chosen for expansion. This corresponds to scanning the input string from left to right.
-
Leftmost Derivation Traced Out in Reverse: Tracing out a leftmost derivation in reverse is not a common practice during parsing.
-
Rightmost Derivation: Rightmost derivation involves replacing the rightmost non-terminal at each step. This is commonly used in bottom-up parsing.
-
Rightmost Derivation Traced Out in Reverse: Tracing out a rightmost derivation in reverse is not a common practice during parsing.