GATE CS 2017 Set 2 Q.6 (CS Q.6): Parsing and Syntax Analysis (LL and LR)

Which of the following statements about parser is/are CORRECT?

I. Canonical LR is more powerful than SLR.
II. SLR is more powerful than LALR.
III. SLR is more powerful than Canonical LR.

I only

II only

III only

I and III only

Official answer and solution

Official answer: A
From: Official GATE 2017 answer key

Solution

Recall the relative expressive power of LR parsing algorithms.

The expressive power of bottom-up LR parsers follows the strict hierarchy:

\text{LR}(0) < \text{SLR}(1) < \text{LALR}(1) < \text{CLR}(1)

where CLR(1) denotes the Canonical LR(1) parser.

Evaluate the given statements:

Statement I: Canonical LR is more powerful than SLR. This is CORRECT because every SLR(1) grammar is a CLR(1) grammar, but CLR(1) can parse grammars with reduce/reduce or shift/reduce conflicts that SLR(1) cannot handle.
Statement II: SLR is more powerful than LALR. This is INCORRECT because LALR(1) is strictly more powerful than SLR(1).
Statement III: SLR is more powerful than Canonical LR. This is INCORRECT because Canonical LR is strictly more powerful than SLR.

Hence, Statement I only is correct, matching option A.

Final answer

Common trap

Confusing state count with grammar parsing power. While SLR and LALR have the same number of states, LALR has more specific lookaheads and is strictly more powerful than SLR.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2017 Computer Science and Information Technology (CS) Session 2
Question: 6 of 65, printed as CS Q.6
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.

Question

Solution

Source