GATE 2024 CS2 Q.65: solution and answer

GATE 2024 · CS2Q.65 · 2 marks · NAT

Consider the following augmented grammar, which is to be parsed with a SLR parser. The set of terminals is {a, b, c, d, #, @}

$S^{'} \to S$
$S \to S S ∣ A a ∣ b A c ∣ B c ∣ b B a$
$A \to d #$
$B \to @$

Let $I_{0} = CLOSURE ({S^{'} \to ∙ S})$ . The number of items in the set $GOTO (I_{0}, S)$ is ______

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

$GOTO (I_{0}, S)$ contains 9 items.

Official answer: 9Source: Official answer key, GATE 2024 CS2 (IISc Bengaluru)

$I_{0} = CLOSURE ({S^{'} \to ∙ S})$ contains $S^{'} \to ∙ S$ , then (dot before $S$ ) all $S$ -productions $S \to ∙ S S$ , $S \to ∙ A a$ , $S \to ∙ b A c$ , $S \to ∙ B c$ , $S \to ∙ b B a$ , and (dot before $A$ and $B$ ) $A \to ∙ d #$ , $B \to ∙ @$ .
$GOTO (I_{0}, S)$ is the closure of the set obtained by moving the dot over $S$ in every item of $I_{0}$ that has the dot immediately before $S$ . Only $S^{'} \to ∙ S$ and $S \to ∙ S S$ qualify.
Moving the dot gives the kernel: $S^{'} \to S ∙$ and $S \to S ∙ S$ .
In $S \to S ∙ S$ the dot is before the nonterminal $S$ , so add every $S$ -production with the dot at the start: $S \to ∙ S S$ , $S \to ∙ A a$ , $S \to ∙ b A c$ , $S \to ∙ B c$ , $S \to ∙ b B a$ (5 items).
The items $S \to ∙ A a$ and $S \to ∙ B c$ have the dot before $A$ and $B$ , so add $A \to ∙ d #$ and $B \to ∙ @$ (2 items).
The items $S \to ∙ b A c$ and $S \to ∙ b B a$ have the dot before the terminal $b$ , so they add nothing. No other nonterminal appears after a dot, so the closure is complete.
Count: $2 + 5 + 2 = 9$ . The set is ${S^{'} \to S ∙, S \to S ∙ S, S \to ∙ S S, S \to ∙ A a, S \to ∙ b A c, S \to ∙ B c, S \to ∙ b B a, A \to ∙ d #, B \to ∙ @}$ .

KEY IDEA

GOTO(I, X) moves the dot over X in every item that has the dot just before X, then takes the closure. Closure adds productions only for a nonterminal that sits immediately after a dot.

WATCH OUT FOR

Leaving out the kernel item $S^{'} \to S ∙$ , or adding items for $A$ and $B$ from $S \to ∙ b A c$ and $S \to ∙ b B a$ . There the dot is before the terminal $b$ , so they add nothing. Another slip is counting the old $I_{0}$ items instead of recomputing the closure.

From the GATE 2024 CS2 paper. Every question of this paper · Download the full paper · All 13 Parsing questions, with notes

GATE 2024 CS2 Q.65: solution and answer

Answer and solution

More Parsing questions