Question
Among simple LR (SLR), canonical LR, and look-ahead LR (LALR), which of the following pairs identify the method that is very easy to implement and the method that is the most powerful, in that order?
Official answer and solution
- Official answer
- C
- From
- Official GATE 2015 answer key
Solution
Compare the complexity of table construction and the parsing capability across the LR parsing family (SLR, LALR, and CLR).
The LR parsing methods compare as follows:
- Ease of implementation: SLR(1) uses LR(0) items and resolves reduce actions using simple
FOLLOWsets computed from the grammar. It requires the fewest resources and is the simplest and easiest to implement. - Parsing power: Canonical LR (CLR(1)) keeps distinct states for different lookahead sets, avoiding reduce-reduce and shift-reduce conflicts that occur when states with identical cores are merged. Hence, CLR(1) is the most powerful LR parsing technique.
LALR(1) merges states of CLR(1) that have identical cores. While having the same state count as SLR(1), it is strictly less powerful than CLR(1) and more complex to construct than SLR(1).
Thus, the method that is very easy to implement is SLR, and the method that is the most powerful is canonical LR. In that order: SLR, canonical LR (Option C).
C
Selecting LALR as the most powerful, whereas Canonical LR is strictly more powerful because merging cores in LALR can produce reduce-reduce conflicts.
The answer is the one in the official GATE answer key. The solution is this site's own explanation.
Source
- Paper
- GATE 2015 Computer Science and Information Technology (CS) Session 3
- Question
- 26 of 65, printed as CS Q.16
- 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.