Question

Which one of the following kinds of derivation is used by LR parsers?

• A. Leftmost
• B. Leftmost in reverse
• C. Rightmost
• D. Rightmost in reverse

Hint:

Easy mnemonic: {L}R parser $\Rightarrow$ {R}ightmost derivation (in reverse). Top-down parsers correspond to leftmost derivations.

Answer 1

The Correct Option is D

Step 1: Recall the basic derivation strategies. 
Context-free grammars support two common ways of generating strings:
A leftmost derivation, where the leftmost non-terminal is expanded at every step, and
A rightmost derivation, where the rightmost non-terminal is expanded first.

Step 2: Review the working principle of LR parsers.
LR parsers belong to the class of bottom-up parsers.
They begin with the input symbols and repeatedly reduce them until the start symbol of the grammar is reached.
This approach can be viewed as reversing a derivation process.

Step 3: Connect LR parsing with derivation order.
During parsing, an LR parser reduces handles in a sequence that corresponds to undoing a derivation.
When this sequence is viewed in reverse, it matches a rightmost derivation of the input string.
Thus, LR parsing can be described as constructing a rightmost derivation in reverse.

Step 4: Check each option.
(A) Leftmost: This is characteristic of top-down parsers, not LR parsers.
(B) Leftmost in reverse: This does not describe the behavior of LR parsing.
(C) Rightmost: LR parsers do not generate rightmost derivations directly in forward order.
(D) Rightmost in reverse: This correctly describes how LR parsers operate.

Step 5: Final conclusion.
LR parsers perform:

\[ \boxed{\text{Rightmost derivation in reverse}} \]