Question

When LALR(1) is constructed form CLR(1) does not contain any shift reduce conflicts?

Comments

f we don't have a SR conflict in CLR(1) then we don't have in LALR(1) also, but considering this example

A->a. ,c  B->Ba.b ,a   and second state being A->a. ,a      B->Ba.b ,c
After merging these two we get A->a. ,(a,c)   B->Ba.b ,(a,c) which has SR conflict.  That indicates the statement is incorrect. Is it possible?

---

The merged stage contains { A -> a., (a,c) & B -> Ba.b, (a,c) }. Here, for the item A -> a., the reduce operation will be place in column a and c of row Ik. And for the item B -> Ba.b, the shift operation will be place in column b of row Ik, since b is after dot(.). When there is a terminal after dot, we simply shift based on that terminal, we don't see the lookahead symbols. Hence no SR conflict will be there.

 

I had same doubt, but after carefully thinking about how parse table is filled, it resolved.

Answer 1

When LALR1 is constructed from CLR1

1)LALR can have shift reduce conflicts only if   CLR has shift reduce conflict

2)LALR may have reduce reduce conflict even if CLR  dont have any conflict(conflict arises due to merging of states where lookaheads are same)

Comments

didn't get you mam

---

See these two line, as u shard example of @MiNiPanda

 

A→ B.aC, c/df/g  

C→ D.,e/h

how here r u telling SR conflict? Still they have different lookaheads during merging in LALR(1)?

 

---

i am saying, there is no SR conflict arises while Merging if CLR(1) states doesn't have it !

Answer 2

The reason is in canonical set of clr(1) shift entries depend on look ahead symbol but reduce entries not depends on look ahead symbol i.e. depends on follow set of left side of  ->.

Answer 3

When creating LALR from CLR :

1. Even if CLR doesn’t have RR conflict , LARL may have RR conflict.
2. CLR have RR conflict , LARL will also have RR conflict.
3. CLR has no SR conflict then LALR will also have no SR conflict
4. CLR has SR conflict then LALR will also have  SR conflict

LALR can’t generate SR conflicts by its own but can generate RR conlict by its own.

Answer 4

 

1. Even if CLR doesn’t have RR conflict , LARL may have RR conflict.
2. CLR have RR conflict , LARL will also have RR conflict.
3. CLR has no SR conflict then LALR will also have no SR conflict
4. CLR has SR conflict then LALR will also have  SR conflict

LALR can’t generate SR conflicts by its own but can generate RR conflict by its own.