Question
Which one of the following kinds of derivation is used by LR parsers?
Official answer and solution
- Official answer
- D
- From
- Official GATE 2019 answer key
Solution
Recall the fundamental parsing strategy of LR parsers.
In compiler construction, "LR" stands for:
- L: Left-to-right scanning of the input string.
- R: Constructing a Rightmost derivation in reverse.
Bottom-up shift-reduce parsers trace the derivation backwards from the input tokens back to the start symbol, which corresponds to the reverse of a rightmost derivation.
Final answer
D
Common trap
Choosing rightmost derivation without specifying 'in reverse' (top-down parsers use leftmost derivation).
The answer is the one in the official GATE answer key. The solution is this site's own explanation.
Source
- Paper
- GATE 2019 Computer Science and Information Technology (CS)
- Question
- 13 of 65, printed as CS Q.3
- Section
- Computer Science and Information Technology
Report an error in this question
GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.