GATE CS 2026 Set 1 Q.53: Syntax-Directed Translation

Consider the following two syntax-directed definitions SDD1 and SDD2 for type declarations.

SDD1 Grammar (G1)	SDD1 Semantic Rules	SDD2 Grammar (G2)	SDD2 Semantic Rules
$D \rightarrow T\,V$	$D.\text{type} = T.\text{type}$ ; $V.\text{type} = T.\text{type}$	$D \rightarrow D_1\,\text{id}$	$D.\text{type} = D_1.\text{type}$ ; $\text{put}(\text{id}.\text{entry}, D_1.\text{type})$
$T \rightarrow \text{int}$	$T.\text{type} = \text{int}$	$D \rightarrow T\,\text{id}$	$D.\text{type} = T.\text{type}$ ; $\text{put}(\text{id}.\text{entry}, T.\text{type})$
$T \rightarrow \text{float}$	$T.\text{type} = \text{float}$	$T \rightarrow \text{int}$	$T.\text{type} = \text{int}$
$V \rightarrow V_1\,\text{id}$	$V_1.\text{type} = V.\text{type}$ ; $\text{put}(\text{id}.\text{entry}, V.\text{type})$	$T \rightarrow \text{float}$	$T.\text{type} = \text{float}$
$V \rightarrow \text{id}$	$\text{put}(\text{id}.\text{entry}, V.\text{type})$

$D$ is the start symbol, and $\text{int}$ , $\text{float}$ and $\text{id}$ are the three terminals. The non-terminal $V_1$ is the same as $V$ and the non-terminal $D_1$ is the same as $D$ . Here, the subscript is used to differentiate the grammar symbols on the two sides of a production. The function $\text{put}$ updates the symbol table with the type information for an identifier.

Let $P$ and $Q$ be the languages specified by grammars G1 and G2, respectively.

Which of the following statements is/are true?

The languages $P$ and $Q$ are the same

SDD2 is S-attributed and contains only synthesized attributes

SDD1 is L-attributed and contains only inherited attributes

The specifications of SDD1 and SDD2 are such that the same entries get added to the symbol table

Official answer and solution

Official answer: A, B and D
From: Official GATE 2026 answer key

Solution

Check the languages generated by G1 and G2, classify the attributes in SDD1 and SDD2 as synthesized or inherited, and compare their symbol table updates.

Option (A) is true: Both G1 and G2 generate the regular language $(\text{int} \mid \text{float})\,\text{id}^+$ (a type keyword followed by one or more identifiers).
Option (B) is true: In SDD2, every attribute ( $T.\text{type}$ and $D.\text{type}$ ) is computed for the LHS non-terminal from attributes of its children on the RHS. Hence SDD2 contains only synthesized attributes and is S-attributed.
Option (C) is false: Although SDD1 is L-attributed, it does not contain only inherited attributes: $T.\text{type}$ and $D.\text{type}$ are synthesized attributes (while $V.\text{type}$ is an inherited attribute).
Option (D) is true: For any valid declaration string $t\,\text{id}_1\,\text{id}_2\dots \text{id}_k$ , both SDD1 and SDD2 invoke $\text{put}(\text{id}_i.\text{entry}, t)$ for every identifier $\text{id}_i$ , adding the exact same entries to the symbol table.

Final answer

Options (A), (B), (D)

Common trap

Selecting (C) without noticing that $T.\text{type}$ and $D.\text{type}$ in SDD1 are synthesized attributes.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2026 Computer Science and Information Technology - Session 1 (CS1)
Question: 53 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source