Complier Design Test 1.1

Question

Ques.  S --> Aa/bAc/dc

           A --> d

Which of them is correct. Please provide detailed information.

a) LALR(1) but not SLR(1)

b) Both SLR(1) and LALR(1)

c) Grammar is Ambiguous

d) Neither SLR(1) NOR LALR(1)

Answer 1

We have to construct LR parsing table,

For SLR(1) parsing table, we have to find all LR(0) items and make sure that no item should contain either SR/RR conflict, then grammar is SLR(1). 

Similarly for LALR(1), we need to find all LR(1) items.

For the above question ,

the LR(1) items are,

For LR(0) items, we will get SR conflict due to productions S->dc and A->d,

 hence grammar is LALR(1) but not SLR(1).

Correct me if i am wrong.

Comments

yes its correct, at state I4 there is SR conflict (in column c of SLR(1) parsing table), which is rectified by LALR(1). so option A is correct.

---

Although it doesn't matter, there is a mistake in GOTO column of state I₀ .

---

LR(0) :

So, in SLR(1) A -> d. Reduce Move R4 will go in FOLLOW(A) i.e., [0,c] and [0,a] cell

But S -> d.c Shift move will go in [0,d] cell. Therefore, where is the conflict?

Please do correct me where I am going wrong.

---

	$	a	b	c	d	S	A
4		R4		R4/S8

Follow(A) = {a,c}
At state I4, 4rth production that is A-> d is completed so, we write R4 under follow of a i.e {a,c}
and what will state I4 do, when he see c, it will move to state I8. i.e shift to state I8.
So you can see there is SR-conflict at [4,c].

Answer 2

there's nothing in that look,

while finding canonical form of LR(0) item that is SLR(1) we come up vit an SR conflict in I4 state but upon finding the follow we deduce that conflict. so its an SLR(1).

 And coming to the LALR(1)  there is an SR conflict again in I4 state but its easily eradicated because here there is an LOOKAHEAD sybl which doesn't not participate in conflict max number of blank spaces are seen soo here  the grammer satisfies LALR(1)..