The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+22 votes
3.1k 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 (359k points)
edited by | 3.1k views

2 Answers

+32 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?
+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 Active (5.2k 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?
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

41,053 questions
47,651 answers
147,210 comments
62,380 users