GATE CSE 2019 | Question: 43

Question

Consider the augmented grammar given below:

• $S’ \rightarrow S$
• $S \rightarrow \langle L \rangle \mid id$
• $L \rightarrow L, S \mid S$

Let $I_0 = \text{CLOSURE} (\{[S’ \rightarrow \cdot S ]\}).$ The number of items in the set $\text{GOTO} (I_0, \langle \: )$ is______

Comments

It seems ambiguous, The number of items, Not mentioning LR(0) / LR(1) items

IF LR(0)  then 5 items  in GOTO (I0, < )

IF LR(1) then 7 items  in GOTO (I0, < )

---

Even if I consider LR(1) items, items shall remain 5 only. Please correct me if I am wrong.

---

@Umakant_Mukhiya it is not ambiguous cause we have already given augmented grammar without lookahead. So, it’s clearly Lr(0) or SLR(1).

Answer 1

Total $5$ items 

Comments

I have marked 2 since 5 will be entry for action-goto and go-to will be for L and S only

---

@Satbir

chk this..

 here Action+Goto taking 5 items, but asking for only GoTo state, right??Then why 5??

---

I do not know why there is so much confusion regarding this question

People who are saying only $GOTO$ is mentioned not the action part, think of one thing, what do we call GOTO?

From a state if we go to the next state using a NON-Terminal production then that is GOTO

But here in the question it is clearly mentioned that we need to find

The number of items in the set $GOTO(I_0,⟨)$

here $⟨$ is a terminal symbol right? So why so much fuss about non terminal GOTO part

They meant to ask the number  of items in the canonical collection set of $GOTO(I_0,⟨)$

Answer 2

A item  is a production rule with dot marker in a particular state.

 

https://cs.stackexchange.com/questions/25924/lr0-parsing-how-can-i-know-sets-of-items-corresponding-to-states

Comments

@Ram Swaroop

tell me one thing here Action+Goto taking 5 items, but asking for only GoTo state, right??Then why 5??

Answer 3

The canonical collection of items for the above grammar are:

 

GOTO($I_0,<$ ) = $I_2$ which is having 5 items. 

Comments

@Tuhin Dutta

tell me one thing here Action+Goto taking 5 items, but asking for only GoTo state, right??Then why 5??

---

I think they meant to ask no of items in the canonical collection set of the specified GOTO state and not the GOTO items.

Answer 4

It’s asking the number of items in the set GOTO(I0, <).

Means First evaluate I1 = GOTO(I0, <) and then count the number of items present in I1 state.

Answer is 5.