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

An LALR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and only if

  1. The SLR(1) parser for G has S-R conflicts

  2. The LR(1) parser for G has S-R conflicts

  3. The LR(0) parser for G has S-R conflicts

  4. The LALR(1) parser for G has reduce-reduce conflicts

asked in Compiler Design by Veteran (59.7k points) | 2.8k views

3 Answers

+25 votes
Best answer

Both LALR(1) and LR(1) parser uses LR(1) set of items to form their parsing tables. And LALR(1) states can be find by merging LR(1) states of LR(1) parser that have the same set of first components of their items.

i.e. if LR(1) parser has $2$ states I and J with items $A \rightarrow a.bP$,$x$ and $A \rightarrow a.bP$,$y$ respectively, where $x$ and $y$ are look ahead symbols, then as these items are same with respect to their first component, they can be merged together and form one single state, let’s say $K$. Here we have to take union of look ahead symbols. After merging, State $K$ will have one single item as $A \rightarrow a.bP$,$x$,$y$ . This way LALR(1) states are formed ( i.e. after merging the states of LR(1) ).

Now, $S-R$ conflict in LR(1) items can be there whenever a state has items of the form :

A-> a.bB , p
C-> d. , b

i.e. it is getting both shift and reduce at symbol b, 
hence a conflict. 

Now, as LALR(1) have items similar to LR(1) in terms of their first component, shift-reduce form will only take place if it is already there in LR(1) states. If there is no S-R conflict in LR(1) state it will never be reflected in the LALR(1) state obtained by combining LR(1) states.

answered by Active (4.7k points)
edited by
0
Nicely Explained.
0
Same thing happens for RR conflict also.rt?

means

An LALR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and only if  The LR(1) parser for G has S-R conflicts
+2
for rr , its not if and only if , bcoz after merging might be there will rr conflict
0
@Madhab @ Bikram
A-> a.bB , p
C-> d. , b

how it is getting s-r conflict if LHS of both productions are different?

It will only be possible if A-> d. , b

0
what if the question is

SLR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and only if?
+1
@iarnav here conflict will create for a state ,unlike in LL(1) for non-terminal
0
can we merge the two states of LR(1) if state I has one more item,other than the common one,which is not present in another state J?
+13 votes
Answer is B.
answered by Boss (19.9k points)
+1
LALR(1) can have conflict even if LR(1) do not contain any conflict. Conflict may arise while merging.
0
why not (c), in LR(0) items S-R conflict??

edit:correction, LR(1) = CLR(1) so it makes sense , so option (b) is correct
+1 vote
Option B
answered by Active (2.9k 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,254 questions
49,750 answers
164,110 comments
65,848 users