The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+24 votes
3.3k views

Consider the following two sets of LR(1) items of an LR(1) grammar.

$X \rightarrow c.X, c/d$ $X → c.X, \$ $
$X \rightarrow .cX, c/d$ $X → .cX, \$ $
$X \rightarrow .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 look aheads 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.
  1. $1$ only      
  2. $2$ only      
  3. $1$ and $44 only      
  4. $\text{1, 2, 3}$ and $4$
asked in Compiler Design by Veteran (370k points)
edited by | 3.3k views

3 Answers

+35 votes
Best answer


The TRUE statements are about merging of two states for LALR(1) parser from RR(1) parser.i.e.

  1.  These can be merged because kernel of these are same, look ahead don't matter in merging
  2. Two states are not containing reduces item , so after merging , the merged states can not be contain any S-R conflict.
  3. There is no reduction possible so no R-R conflict
  4. Merging of states does not depend on further GOTO part on any terminal.

    Therefore , ALL given statement in question are FALSE , so option (D) is correct.
answered by Active (2.1k points)
edited by
0
Didnt get what is means by option D.
Does merging anyway depend on goto moves?  I know that if states have same LR0 items but different lookaheads in LR1 canonical collection, then we merge them to get LALR1 canonical collection. So what option D is talking about?
0
What does merging does depend on?
0
Why the grammar cant be reduced further?

My query is should we proceed to the answer from the given states only or we need to reduce the items and then encounter the answers?
0
  1. Cannot be merged since goto on c will lead to two different sets.

Merging is not depend on goto ..it need only 2 states with same productions with different lookaheads

But i am not getting meaning of " goto on c "..how can goto be defined on terminal ??

0

@jatin khachane 1 I don't think it will matter even if you say shift on c.

0
Yes but what "Goto on c " means actually ..we do shift on seeing terminal right ??
0

yes but that statement is just trying to imply some condition like if we see terminal/nonterminal and it goes to different state then we cannot merge it which is wrong and we know only condition is same LR(0) items .

0
Yes ..that option is incorrect because it inferring that merging is not possible if this option holds

But i am talking about general ..not particular to merging possible or not ..just "GOTO on 'c' "
+7 votes

after merging their are no final item so no posiblity of any type of conflict . bcz S-R,R-R conflicts r check over final item so option 2 and 3 are totaly wrong . and option 1 also wrong bcz merging can be possible bcz its does not  depend upon look ahead symbol.and option 4. so D is the option 

answered by Loyal (5.3k points)
0
Didnt get what is means by option D.
Does merging anyway depend on goto moves?  I know that if states have same LR0 items but different lookaheads in LR1 canonical collection, then we merge them to get LALR1 canonical collection. So what option D is talking about?
0 votes
Option A, B and D are clearly false, following are reasons
-Since merging don't depend on lookahead
-Due to the merging SR conflict never occurs
-And merging also don't depend on Goto part.
RR conflict may be occur after merging but in question no RR conflict even after merging.
So claerly option D is right choice.
answered by (313 points)
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,491 questions
49,940 answers
165,706 comments
65,911 users