GATE CSE 2013 | Question: 40

Question

Consider the following two sets of $\textsf{LR(1)}$ items of an $\textsf{LR(1)}$ grammar.$ $\begin{array}{l|l}
X \rightarrow c.X, c∕d &X → c.X, \$\\
X \rightarrow .cX, c∕  d& X → .cX, \$\\
X \rightarrow .d, c∕ d & X → .d, \$
\end{array}$ $Which of the following statements related to merging of the two sets in the corresponding $\textsf{LALR}$ parser is/are FALSE?

1. Cannot be merged since look aheads are different.
2. Can be merged but will result in $\textsf{S-R}$ conflict.
3. Can be merged but will result in $\textsf{R-R}$ conflict.
4. Cannot be merged since $\textsf{goto}$ on $c$ will lead to two different sets.

• A. $1$ only      
• B. $2$ only      
• C. $1$ and $4$ only      
• D. $\text{1, 2, 3}$ and $4$

Comments

I think statement (2) should be FALSE irrespective of whether there is SR conflict in the current LR(1) items or not as the statement is trying to say that because of merging there will be SR conflict but this can never happen.

---

Tricks:

There is no final item., so 2,3 false. Same LR(0) items means can be merged, so 1,4 false.

---

Even if we had inplace of X --> .d ,c/d and X --> .d , $

X-->d. , c/d.       X -->d. , $

 

There would have been no problem in merging. Perfect merging no conflict.

---

We need atleast one reduced form in one of the sets to get conflict but there is no Reduced conflict so there is no Chance of getting SR and RR conflict . So option D make good choice .

Answer 1

The TRUE statements are about merging of two states for $\textsf{LALR(1)}$ parser from $\textsf{LR(1)}$ parser.

1. The given two states can be merged because kernel of these are same, look aheads don't matter in merging.
2. The two states do not contain shift reduce conflict, so after merging the merged states cannot contain any $\textsf{S-R}$ conflict.
3. There is no final item in both states, so no $\textsf{R-R}$ conflict.
4. Merging of states does not depend on further $\textsf{GOTO}$ part on any terminal.

Therefore,  all the given statements in question are FALSE.

Option (D) is correct.

Comments

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

---

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 .

---

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' "

Answer 2

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 

Comments

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?

Answer 3

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.

Answer 4

• Both sets have the exact same $\text{LR}(0)$ core items $\{X \rightarrow c.X, \; X \rightarrow .cX, \; X \rightarrow .d\}$, so they can be merged in an $\text{LALR}$ parser by taking the union of their lookaheads $\{c, d, \$\}$.

• Statement 1 is FALSE because different lookaheads do not prevent merging; merging specifically combines identical cores having different lookaheads.

• Statement 2 is FALSE because none of the items are completed reduce items (the dot is not at the end), so no Shift-Reduce (S-R) conflict can occur.

• Statement 3 is FALSE because without completed reduce items, a Reduce-Reduce (R-R) conflict is impossible.

• Statement 4 is FALSE because goto transitions on non-terminals or terminals with identical cores are also merged consistently into a single state.

Correct Option: D. 1, 2, 3 and 4

Answer 5

The two sets in LR(1) items can be merged if they only differ with look aheads symbols, so statement 1 is false.
In the given LR(1) items there is not any reduce move, so after merging it will not have SR conflict and hence statement 2 and statement 3 are false.
Statement 4 is also wrong, because goto is carried on Non-Terminals symbols, not on terminal symbols, and c is a terminal symbol.
Hence all statements are false.

Answer 6

 

final result :
X→c.X,c∕d​/$

X→.cX,c∕d​/$

X→.d,c∕d​/$

1. Cannot be merged since look aheads are different.....FALSE
   reason lookhead does affect the mergering
2. Can be merged but will result in S-RS-R conflict......FALSE
   reason The two states do not contain shift reduce conflict, so after merging the merged states cannot contain any S-RS-R conflict
3. Can be merged but will result in R-RR-R conflict....false
   reason: There is no final item in both states, so no R-RR-R conflict.
4. Cannot be merged since gotogoto on cc will lead to two different sets....FALSE
   reason : Merging of states does not depend on further GOTOGOTO part on any terminal.