GateAI
Parsing

GATE CSE 2024 Set 1 · Q38

MCQ2 marksMedium

Time

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)‾S \rightarrow daT \mid \underline{\quad (1) \quad} T→aS∣bT∣(2)‾T \rightarrow aS \mid bT \mid \underline{\quad (2) \quad} R→(3)‾∣ϵR \rightarrow \underline{\quad (3) \quad} \mid \epsilon 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}, FIRST(T)={a,b,ϵ}, FIRST(R)={c,ϵ}\text{FIRST}(S) = \{c, d, f\}, \text{ FIRST}(T) = \{a, b, \epsilon\}, \text{ FIRST}(R) = \{c, \epsilon\} FOLLOW(S)=FOLLOW(T)={c,f,$}, FOLLOW(R)={f}\text{FOLLOW}(S) = \text{FOLLOW}(T) = \{c, f, \$\}, \text{ FOLLOW}(R) = \{f\} Which one of the following options CORRECTLY fills in the incomplete productions?

Select one answerSingle correct

Pick an option to check

Solution

Step-by-step verified solution

Official answer: A) (1) S → Rf (2) T → (3) R → cTR

Parsing

To determine the correct productions, we analyze the given FIRST and FOLLOW sets:

  1. Finding Production (2):

    • We are given FIRST(T)={a,b,ϵ}\text{FIRST}(T) = \{a, b, \epsilon\}.

    • The productions for TT are T→aS∣bT∣(2)T \rightarrow aS \mid bT \mid (2).

    • For ϵ∈FIRST(T)\epsilon \in \text{FIRST}(T), the production (2) must be T→ϵT \rightarrow \epsilon.

    • This eliminates options (C) and (D).

  2. Finding Production (1):

    • We are given FIRST(S)={c,d,f}\text{FIRST}(S) = \{c, d, f\}.

    • The productions for SS are S→daT∣(1)S \rightarrow daT \mid (1).

    • Here, FIRST(daT)={d}\text{FIRST}(daT) = \{d\}. Therefore, FIRST((1))\text{FIRST}((1)) must contain {c,f}\{c, f\}.

    • If (1)(1) is S→RfS \rightarrow Rf:

      FIRST(Rf)=(FIRST(R)∖{ϵ})∪{f}={c}∪{f}={c,f}\text{FIRST}(Rf) = (\text{FIRST}(R) \setminus \{\epsilon\}) \cup \{f\} = \{c\} \cup \{f\} = \{c, f\}

      This gives FIRST(S)={d}∪{c,f}={c,d,f}\text{FIRST}(S) = \{d\} \cup \{c, f\} = \{c, d, f\}, which matches the given set.

    • If (1)(1) were S→fRS \rightarrow fR, then FIRST(fR)={f}\text{FIRST}(fR) = \{f\}, yielding FIRST(S)={d,f}\text{FIRST}(S) = \{d, f\}, which is missing cc.

    • Thus, (1)(1) must be S→RfS \rightarrow Rf.

  3. Finding Production (3):

    • With (3)(3) being R→cTRR \rightarrow cTR, FIRST(R)={c,ϵ}\text{FIRST}(R) = \{c, \epsilon\} is satisfied.

Therefore, the correct choice is (A).

Try the question first, then check your work.

Think the official key or this write-up is wrong?

Report error or challenge

Examiner trap

The misconception this question tests

This Parsing previous year question is Q38 of the GATE CSE 2024 Set 1 paper. Find more GATE CSE PYQs on Parsing in Compiler Design, or browse all GATE CSE PYQs.

Free diagnostic

Where do you stand for GATE?

Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Parsing PYQs now with no account.

One GATE CSE PYQ every morning

An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.

Parsing in GATE CSE

Parsing has 23 GATE CSE PYQs across 16 papers from 2012 to 2026. 11 of them are 2-mark MCQs like this one, and GATE CSE 2024 Set 1 has 2.

How GATE tests Parsing

More from GATE CSE 2024 Set 1

Share this solution

A plain-text card for WhatsApp or Telegram study groups.

GateAI solution cardGATE CSE 2024 Set 1 · Q38 · MCQ

Consider the following grammar G, with S as the start symbol. The grammar G has three incomplete productions denoted by (1), (2), and (3). S → daT (1) T → aS bT (2) R → (3) The set of terminals is {a, b, c, d, f}. The FIRST and FOLLOW sets of the different non-terminals are as follows. FIRST(S) = {c, d, f}, FIRST(T) = {a, b, }, FIRST(R) = {c, } FOLLOW(S) = FOLLOW(T) = {c, f, \$}, FOLLOW(R) = {f} Which one of the following options CORRECTLY fills in the incomplete productions?

Topic-wise GATE CS PYQs with verified steps

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.