GATE CSE 1988 | Question: 10ia

Question

Consider the following grammar:

• $S \rightarrow S$
• $S \rightarrow SS \mid a \mid \epsilon$

Construct the collection of sets of $\text{LR (0)}$ items for this grammar and draw its goto graph.

Comments

Here  S→  ϵ will take as reduce/ shift action or not effect on LR(0) DFA??

---

So we cannot write LR(0) items if grammar is ambiguous?

---

afaik, LR(0) items can be constructed if the grammar is ambiguous.

Answer 1

The augmented production is $S^{'} \rightarrow S$.

$\textbf{GOTO Graph:}$

Here, each of $I_0$, $I_1$, $I_2$, $I_3$ is a set of $LR(0)$ items. And hence $I_0$, $I_1$, $I_2$, $I_3$ are the collection of sets of $LR(0)$ items.

Comments

@abir_banerjee

Yes. s -> ss. and s->. is also one.

---

@Arjun sir do we consider augmented productions in RR conflict? for example a state with

S’->S. and S->a.     

will these two be taken as rr conflict in LR(0) parser?

---

@Godlike

No, $S’→ S.$ is the acceptance state not the reduced state.

Answer 2

Augmented production S'-->S

 

Comments

Sir we can write LR(0) items..

But there will be conflicts in dfa (of canonical collection of LR(0) items).. so the grammar will not be LR(0)

---

Thats all is asked in the question rt?

---

Yes..

---

Yes this grammar is not LR(0)

And the question only asked to draw the DFA