The GATE Grind

GATE 2024 CS (CS2) – Question 65

Compiler Design · Parsing and Syntax Analysis · 2 marks · Numerical answer

Consider the augmented grammar parsed with an SLR parser, terminals $\{a,b,c,d,\#,@\}$: $S'\to S$; $S\to SS\mid Aa\mid bAc\mid Bc\mid bBa$; $A\to d\#$; $B\to @$. Let $I_0=CLOSURE(\{S'\to\bullet S\})$. The number of items in the set $GOTO(I_0,S)$ is ___________

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 9

Explanation

Augmented grammar: $S'\to S$; $S\to SS\mid Aa\mid bAc\mid Bc\mid bBa$; $A\to d\#$; $B\to @$.

$I_0$ contains $S'\to\bullet S$ and its closure. $GOTO(I_0,S)$ moves the dot over $S$ in every item of $I_0$ that has $\bullet S$:
- $S'\to S\bullet$
- $S\to S\bullet S$

Closure adds the items for the nonterminal $S$ now after the dot:
- $S\to\bullet SS$, $S\to\bullet Aa$, $S\to\bullet bAc$, $S\to\bullet Bc$, $S\to\bullet bBa$ (5 items)
- $A\to\bullet d\#$ and $B\to\bullet @$ (from $\bullet A$ and $\bullet B$)

Total $=2+5+2=\mathbf{9}$ items.

More Parsing and Syntax Analysis questions

All Parsing and Syntax Analysis questions →