GATE CSE 2021 Set 1 Q41: Fill the blank cells of an LL(1) parsing table

Compiler Design
2 marks
MCQ
−2/3 if wrong

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

$\begin{aligned} S &\to d\,a\,T \mid R\,f \\ T &\to a\,S \mid b\,a\,T \mid \epsilon \\ R &\to c\,a\,T\,R \mid \epsilon \end{aligned}$

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

Which one of the following choices represents the correct combination for the numbered cells in the parsing table ("blank" denotes that the corresponding cell is empty)?

	$a$	$b$	$c$	$d$	$f$	\$
S			(1)	$S \to d\,a\,T$	(2)
T	$T \to a\,S$	$T \to b\,a\,T$	(3)		$T \to \epsilon$	(4)
R			$R \to c\,a\,T\,R$		$R \to \epsilon$

Try it: multiple choice: exactly one correct option

Wrong answer costs 2/3 mark in GATE.

Show answer and explanation

Answer: A (official GATE 2021 final answer key)

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

First step: FIRST( $R\,f$ ) $= \{c, f\}$ . For $T \to \epsilon$ , compute FOLLOW( $T$ ) from $R \to c\,a\,T\,R$ and $S \to d\,a\,T$ .

Full step-by-step solution

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

Share this question

WhatsAppDownload image

Source: official GATE 2021 Set 1 CS question paper and final answer key, organised by IIT Bombay. Question paper · Answer key

PracticePractise Compiler Design questions →Full paperAll GATE CSE 2021 Set 1 questions →

GATE CSE 2021 Set 1 Q41: Fill the blank cells of an LL(1) parsing table

Question

Full step-by-step solution

More Compiler Design PYQs