The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes

Consider the following CFG:

$S\rightarrow Aa\mid ca$

$A\rightarrow c\mid d$

How many conflict occur in $CLR\left ( 1 \right )$ Parsing construction ?

I think $LR\left ( 0 \right )$ there is $1$ conflict, but in $SLR\left ( 1 \right )orCLR\left ( 1 \right )$ there won’t be any conflict. Someone verify it.

asked in Compiler Design by Veteran (111k points)
edited by | 53 views
There will be a SR conflict in both LR(0) and SLR(1)
S -> .ca and A -> .c    -------------->(on c)    S->c.a and A->c.
So, answer of this question will be 0

No, the grammar is neither LR(0), SLR(1) nor CLR(1).

Even incase of CLR(1) there will be a SR conflict b/w

S -> c.a , $
S -> c. , a
how CLR(1) has conflict ?

Is their look aheads same?
S -> c.a , $  ( it is shift in this case, so this will reside in a's column)

S -> c. , a ( it is reduce in this case, this goes in the same column as well)

we will compare lookaheads only for reduce not for shift.

yes, I got it now.

Actually lookaheads are not different.

It is same for the above two cases.

$S\rightarrow c.a,$$

$S\rightarrow c.,$$

by the way can u chk it too

pls check it again, lookaheads must be different.

S -> c.a , $
S -> c. , a

@balchandar reddy san

If different lookahead, then there won't be any SR conflict in CLR(1). Because, GOTO works only those rows, which have lookaheads

S -> c.a , $ ( this is shift conflict so, we have to take 'a'),

we have to take lookahead only in case of reduce conflict

1 Answer

0 votes

Grammer is not CLR(1) because it have Shift-Reduce conflict. 

S->c.a $   (Shift production)

A->c.   a  (Reduce production)

The shift reduce condition in CLR(1) is that Shifting symbol should not be appearing look ahead list of reducing production.

Here 'a' is shift in 1st production and  it also appear look ahead list of 2nd production.


And another alternative grammer is ambiguous it  have 2 parse tree for the string 'ca' if the grammer is ambigious it can not be CLR(1) 

answered by (395 points)

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
49,540 questions
54,099 answers
71,006 users