Skip to content
GATEiit

GATE CSE 2024 Session 1 Q38: Complete a grammar from its FIRST and FOLLOW sets

Question

Consider the following grammar GG, with SS as the start symbol. The grammar GG has three incomplete productions denoted by (1), (2), and (3).

S→daT∣(1)‾T→aS∣bT∣(2)‾R→(3)‾∣ϵ\begin{aligned} S &\to daT \mid \underline{\quad(1)\quad} \\ T &\to aS \mid bT \mid \underline{\quad(2)\quad} \\ R &\to \underline{\quad(3)\quad} \mid \epsilon \end{aligned}

The set of terminals is {a,b,c,d,f}\{a, b, c, d, f\}. The FIRST and FOLLOW sets of the different non-terminals are as follows.

FIRST(S)={c,d,f}\text{FIRST}(S) = \{c, d, f\}, FIRST(T)={a,b,ϵ}\text{FIRST}(T) = \{a, b, \epsilon\}, FIRST(R)={c,ϵ}\text{FIRST}(R) = \{c, \epsilon\}

FOLLOW(S)=FOLLOW(T)={c,f,$}\text{FOLLOW}(S) = \text{FOLLOW}(T) = \{c, f, \text{\textdollar}\}, FOLLOW(R)={f}\text{FOLLOW}(R) = \{f\}

Which one of the following options CORRECTLY fills in the incomplete productions?

Try it: multiple choice: exactly one correct option

Select one option
Wrong answer costs 2/3 mark in GATE.
Show answer and explanation

Answer: A (official GATE 2024 final answer key)

Concept used: FIRST and FOLLOW sets constrain which symbols can start or follow each non-terminal.

First step: ϵ∈FIRST(T)\epsilon \in \text{FIRST}(T) and c∉FIRST(T)c \notin \text{FIRST}(T) force (2) to be T→ϵT \to \epsilon; then use FOLLOW(R)={f}\text{FOLLOW}(R) = \{f\}.

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 2024 Session 1 CS question paper and final answer key, organised by IISc Bangalore. Question paper · Answer key

More Compiler Design PYQs

PracticePractise Compiler Design questions →Full paperAll GATE CSE 2024 Session 1 questions →