Consider the following context-free grammar where the start symbol is S and the set of terminals is \a, b, c, d\. aligned S & AaAb BbBa \\ A & cS \\ B & dS aligned The following is a partially-filled LL(1) parsing table.

(1) S AaAb (2) S BbBa (3) A (4) B

(1) S BbBa (2) S AaAb (3) A (4) B

(1) S AaAb (2) S BbBa (3) blank (4) blank

(1) S BbBa (2) S AaAb (3) blank (4) blank

GATE CSE 2024 Session 2 Q40: Fill the missing cells of an LL(1) parsing table

Consider the following context-free grammar where the start symbol is $S$ and the set of terminals is $\{a, b, c, d\}$ .

$\begin{aligned} S &\to AaAb \mid BbBa \\ A &\to cS \mid \epsilon \\ B &\to dS \mid \epsilon \end{aligned}$

The following is a partially-filled LL(1) parsing table.

	$a$	$b$	$c$	$d$
$S$	$S \to AaAb$	$S \to BbBa$	(1)	(2)
$A$	$A \to \epsilon$	(3)	$A \to cS$
$B$	(4)	$B \to \epsilon$		$B \to dS$

Which one of the following options represents the CORRECT combination for the numbered cells in the parsing table?

Note: In the options, "blank" denotes that the corresponding cell is empty.

Try it: multiple choice: exactly one correct option

Wrong answer costs 2/3 mark in GATE.

Show answer and explanation

Answer: A (official GATE 2024 final answer key)

Concept used: LL(1) table: put $X \to \alpha$ under FIRST( $\alpha$ ), and under FOLLOW( $X$ ) when $\alpha$ can derive $\epsilon$ .

First step: Compute FIRST( $AaAb$ ), FIRST( $BbBa$ ), FOLLOW( $A$ ) and FOLLOW( $B$ ), then place each production in its cells.

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

Source: official GATE 2024 Session 2 CS question paper and final answer key, organised by IISc Bangalore. Question paper · Answer key