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

Answer: Rightmost in reverse (bottom-up parsing).

Explanation: LR parsers perform bottom-up parsing by identifying handles in the input and reducing them. Each reduction corresponds to reversing a step of a rightmost derivation, so the parser constructs the rightmost derivation in reverse until it reaches the start symbol.

• Key idea: find a handle (the substring that matches the right-hand side of a production and is the rightmost such reducible substring) and replace it with the production's left-hand side.

• Result: the parser builds the rightmost derivation backwards (from the input toward the start symbol), which is why LR parsing is called bottom-up.

Short example:

• Grammar: S → a S b | c

• Rightmost derivation for string a c b: S ⇒ a S b ⇒ a c b

• Bottom-up (reverse) steps that an LR parser would take: a c b → reduce c to S → a S b → reduce a S b to S