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 types of derivations in parsing.
In context-free grammars, there are two standard derivations:
-- Leftmost derivation: always expand the leftmost non-terminal first.
-- Rightmost derivation: always expand the rightmost non-terminal first.
Step 2: Understand how LR parsers work.
LR parsers are bottom-up parsers.
They construct the parse tree starting from the input symbols and work their way up to the start symbol.
Bottom-up parsing corresponds to reversing a derivation process.
Step 3: Relate LR parsing to derivation type.
An LR parser effectively constructs the rightmost derivation in reverse order.
This means it reduces handles in such a way that, if reversed, corresponds to a rightmost derivation.
Step 4: Analyze the options.
(A) Leftmost: Used by top-down parsers, not LR parsers. Incorrect.
(B) Leftmost in reverse: Not the characteristic derivation of LR parsing. Incorrect.
(C) Rightmost: LR parsers do not directly perform a rightmost derivation forward. Incorrect.
(D) Rightmost in reverse: Correct — this is exactly what LR parsers perform.
Step 5: Conclusion.
LR parsers use \[ \boxed{\text{Rightmost derivation in reverse}} \]