GateAI
Parsing

GATE CSE 2013 · Q40

MCQ2 marksMedium

Time

Consider the following two sets of LR(1) items of an LR(1) grammar. X→c.X, c/dX→c.X, $X→.cX, c/dX→.cX, $X→.d, c/dX→.d, $\begin{array}{ll} X \rightarrow c.X, \text{ } c/d & X \rightarrow c.X, \text{ } \$ \\ X \rightarrow .cX, \text{ } c/d & X \rightarrow .cX, \text{ } \$ \\ X \rightarrow .d, \text{ } c/d & X \rightarrow .d, \text{ } \$ \end{array} Which of the following statements related to merging of the two sets in the corresponding LALR parser is/are **FALSE**? 1. Cannot be merged since lookconjugates/lookaheads are different. 2. Can be merged but will result in S-R conflict. 3. Can be merged but will result in R-R conflict. 4. Cannot be merged since goto on cc will lead to two different sets.

Select one answerSingle correct

Pick an option to check

Solution

Step-by-step verified solution

Official answer: D) 1, 2, 3 and 4

Parsing

In an LALR(1) parser, two sets of LR(1) items are merged if and only if they have the same core (i.e., identical productions with the dot in the exact same positions), regardless of their lookaheads.

Let us analyze each statement:

  1. Statement 1 is FALSE: The two sets have identical cores (X→c.XX \rightarrow c.X, X→.cXX \rightarrow .cX, X→.dX \rightarrow .d). In LALR parser construction, states with the same core are merged by taking the union of their lookahead sets. Differences in lookaheads do not prevent merging.

  2. Statement 2 is FALSE: None of the items in these sets are complete items (A→α.A \rightarrow \alpha.), so there are no reduce actions at all. Therefore, no Shift-Reduce (S-R) conflict can occur.

  3. Statement 3 is FALSE: Since there are no reduce items in these sets, no Reduce-Reduce (R-R) conflict can arise.

  4. Statement 4 is FALSE: For any transition (such as goto on cc), the target states will also have identical cores and will correspondingly be merged into a single state in the LALR parser.

Since all statements 1, 2, 3, and 4 are false, the correct option is (D).

Try the question first, then check your work.

Think the official key or this write-up is wrong?

Report error or challenge

Examiner trap

The misconception this question tests

This Parsing previous year question is Q40 of the GATE CSE 2013 paper. Find more GATE CSE PYQs on Parsing in Compiler Design, or browse all GATE CSE PYQs.

Free diagnostic

Where do you stand for GATE?

Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Parsing PYQs now with no account.

One GATE CSE PYQ every morning

An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.

Parsing in GATE CSE

Parsing has 23 GATE CSE PYQs across 16 papers from 2012 to 2026. 11 of them are 2-mark MCQs like this one, and GATE CSE 2013 has 2.

How GATE tests Parsing

More from GATE CSE 2013

Share this solution

A plain-text card for WhatsApp or Telegram study groups.

GateAI solution cardGATE CSE 2013 · Q40 · MCQ

Consider the following two sets of LR(1) items of an LR(1) grammar. ll X → c.X, c/d & X → c.X, \ X → .cX, c/d & X → .cX, \ X → .d, c/d & X → .d, \$ Which of the following statements related to merging of the two sets in the corresponding LALR parser is/are FALSE? 1. Cannot be merged since lookconjugates/lookaheads are different. 2. Can be merged but will result in S-R conflict. 3. Can be merged but will result in R-R conflict. 4. Cannot be merged since goto on c will lead to two different sets.

Topic-wise GATE CS PYQs with verified steps

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.