3.8k 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/dX → .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$4$only 4.$\text{1, 2, 3}$and$4\$
edited | 3.8k views

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 do not contain shift reduce conflict, so after merging , the merged states cannot contain any S-R conflict.
3. There is no final item in both states, 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.
edited
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' "

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

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?
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.

1
2