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

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

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