GATE CS 2019 Q3 — Parsing (LL, LR)

An LR parser is a bottom-up parser that parses the input from Left-to-right and produces a Rightmost derivation in reverse.

Explanation:

• Bottom-up Parsing: Bottom-up parsers start with the input string and attempt to rewrite (reduce) it back to the start symbol of the grammar.
• Derivation Relation: The sequence of reductions performed by a bottom-up parser corresponds exactly to a rightmost derivation traced in reverse order.

For example, if a rightmost derivation is: $$S \Rightarrow \alpha_1 \Rightarrow \alpha_2 \Rightarrow \dots \Rightarrow \text{input string}$$ the LR parser will perform reductions in the exact reverse order: $$\text{input string} \rightarrow \dots \rightarrow \alpha_2 \rightarrow \alpha_1 \rightarrow S$$

Thus, LR parsers use Rightmost derivation in reverse.