GATE 2022 CS Q.29: solution and answer

GATE 2022 · CSQ.29 · 1 mark · NAT

Consider the augmented grammar with {+, *, (, ), id} as the set of terminals.

S' -> S
S  -> S + R | R
R  -> R * P | P
P  -> ( S ) | id

If $I_{0}$ is the set of two LR(0) items ${[S^{'} \to S \cdot], [S \to S \cdot + R]}$ , then $g o t o (c l os u r e (I_{0}), +)$ contains exactly ______ items.

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

$g o t o (c l os u r e (I_{0}), +)$ contains exactly 5 items.

Official answer: 5Source: Official answer key, GATE 2022 CS (IIT Kharagpur)

Only a non-terminal immediately after the dot makes the closure add items. In $S^{'} \to S \cdot$ the dot is at the end. In $S \to S \cdot + R$ the symbol after the dot is the terminal $+$ . So $c l os u r e (I_{0}) = I_{0}$ .
$g o t o (I_{0}, +)$ moves the dot over $+$ in every item that has $+$ right after the dot. Only $S \to S \cdot + R$ qualifies, so the kernel is the single item $S \to S + \cdot R$ .
Take the closure of the kernel. The dot is before $R$ , so add every $R$ -production with the dot at the start: $R \to \cdot R * P$ and $R \to \cdot P$ .
In $R \to \cdot P$ the dot is before $P$ , so add every $P$ -production with the dot at the start: $P \to \cdot (S)$ and $P \to \cdot i d$ .
In $R \to \cdot R * P$ the dot is before $R$ , and both $R$ -items are already present. In $P \to \cdot (S)$ and $P \to \cdot i d$ the next symbols are terminals, so nothing more is added and the closure is complete.
The resulting set is ${S \to S + \cdot R, R \to \cdot R * P, R \to \cdot P, P \to \cdot (S), P \to \cdot i d}$ . It has exactly 5 items.

KEY IDEA

$g o t o (I, X)$ moves the dot over $X$ in the items of $I$ that have $X$ after the dot. You then take the closure of that kernel, adding productions for each non-terminal that now follows a dot.

WATCH OUT FOR

Stopping at the kernel item $S \to S + \cdot R$ and forgetting the closure. Another slip is counting $S^{'} \to S \cdot$ in the result, although it has no $+$ after its dot and so does not carry over.

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

GATE 2022 CS Q.29: solution and answer

Answer and solution

More Parsing questions