edited by
13,169 views
53 votes
53 votes

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.
  1. $1$ only      
  2. $2$ only      
  3. $1$ and $4$ only      
  4. $\text{1, 2, 3}$ and $4$
edited by

4 Answers

Best answer
64 votes
64 votes

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.

edited by
9 votes
9 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 

3 votes
3 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.
0 votes
0 votes
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:

Related questions

83 votes
83 votes
13 answers
1
Arjun asked Sep 23, 2014
32,856 views
What is the maximum number of reduce moves that can be taken by a bottom-up parser for a grammar with no epsilon and unit-production (i.e., of type $A \rightarrow \epsilo...