The Gateway to Computer Science Excellence
+28 votes

A canonical set of items is given below

$S \to L .> R $

$Q \to R.$

On input symbol $<$ the set has

  1. a shift-reduce conflict and a reduce-reduce conflict.
  2. a shift-reduce conflict but not a reduce-reduce conflict.
  3. a reduce-reduce conflict but not a shift-reduce conflict.
  4. neither a shift-reduce nor a reduce-reduce conflict.
in Compiler Design by Veteran (105k points)
edited by | 4.8k views
Now, when we have the edited question,

This is a parsing error. as we do not have " < " in the canonical form.
What the answer would be if it is  '>'

The given state itself sufferes from SR conflict ? Right ?

Correct me if wrong .
@Arjun sir

Is it possible that these two items come in same cannonical item set??


S→L.>R comes from prev state on shift on L

Q→R. comes from prev state on shift on R

They should be in diff item set rt?
Yes different
yes sir .
it is not given that about which parser it is asking .

if i assume it as LR(0) ,and if it is asking about the set(state) on transition of <,then we come to a state which not exists .so ,there will be no conflict in that state.
(and also these two items can never be present on the same set in practice).
the set given in the question has s/r conflict acc. to lr(0) ,because reduce move goes to every terminal
and on transition by shift move of  '>' .

correct me please if i am wrong.
Yes, it itself a S-R conflict because on I/p '>' we are shifting in to another state, so in table it will come under action part

Isn't it a funny question?? What they wanted to check here , Concept or concentration?? My mistake was that I treated > as < .

3 Answers

+24 votes
Best answer

The question is asked with respect to the symbol  ' < '  which is not present in the given canonical set of items. Hence it is neither a shift-reduce conflict nor a reduce-reduce conflict on symbol '<'. Hence D is the correct option. But if the question would have asked with respect to the symbol  ' > '  then it would have been a shift-reduce conflict.

by Loyal (9.9k points)
selected by
S→L.>R // we can reach here by reading L in the previous state only.

Q→R.// we can reach here by reading R

how those both belong even to the same canonical state?

 We can't have any type of conflict here.
How would there be a conflict on '>'

If we consider the grammar to be LR(0) there would be S-R conflict in the given canonical form.

  > $
I0 R2/S1 R2

Suppose that the present state is I0 and on transition on > it goes to I1 state.

S->L.>R --production number :1 (on correction of existing question)

Q->R. ---production number:2

In LR(0) reduced move will be placed in entire row.(under terminal columns)

Here we cant determine SLR(1) paring table as the follow of Q is unknow so we dont know how to place the reduced move.


Suppose we go with the given question(on transition on <)



it wont go to any state so no S-R or R-R as that terminal (<) is not present in the canonical set of LR(0).




Case 1: If "<" is a valid terminal i.e < is in Grammar 

Considering given item as LR(0) item as no lookahead

State < > $
Given item state Q->R Q->R / Shift J Q->R
.. ... ... ...

In this case there will be reduce operation performed. So no conflict 

Case 2: If "<" is a Not valid terminal i.e < is nowhere Grammar 

State > $
Given item state Q->R / Shift J Q->R
.. ... ...

In this case there will be ERROR...But still no conflict 

Please correct me if i am wrong



Shift reduce conflict will be there if there would have been '>'.
+24 votes

Ans : The given input symbol no where in the given grammar so with given symbol we have neither a shift-reduce nor a reduce-reduce conflict. So, correct answer is (D.) ...

by Active (1k points)
edited by
its just an error and not a conflict rt?
Even if we consider that as an typing error or so, then even for '>' this symbol I don't see any option.

As Q-->R does not have a '.' So that we can tell if it is reduced or not.
Yes Arjun sir , in actuall question as Gate Keeda has mention below comment even for > symbol in actuall paper there is no any symbol that's why it is an error as there is no any entry in parse table so no any conflict but error..
@Gate-keeda I was not telling about typo. Error during parsing.
That's for sure will be an error.

But I'm saying that the question itself is wrong.
hmm q->r in not canonical form..."." is not there.....but if we ignore that nd take q->.r then option (d ) is correct
Are Canonical Set of items and LR(0) items same ?
Given state itself suffer from SR conflict , right ?
Correct me if wrong .
Yes SR conflict if Q->R.  is the second production and we have ">".
what is the meaning of this line "The given input symbol no where in the given grammar.." symbol no where?!?
yes on input > it has SR conflict for sure.
that cannot be confirmed till we know wheter the parser is lr (0) or slr (1 ) and if > is in follow of Q then it s confirmed to have SR conflict
Even if the question had ">", there won't be any conflict on its canonical collection. There will only be shift to $S\rightarrow L>.R$  and enumerations of R. The current state itself is in SR conflict, and that's a different matter.
Can someone send some resources for this topic?

may be printing mistake in the question?
but according to the question Option D is right

0 votes
d ans as <. is not in the grammer
by Active (4k points)
this question is just to trap students marking in a hurry!

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
50,737 questions
57,317 answers
105,096 users