Consider the following two syntax-directed definitions SDD1 and SDD2 for type… — GATE CS 2026 Set 1 Q43

GATE CSE 2026 | Set 1-43

Consider the following two syntax-directed definitions $\text{SDD1}$ and $\text{SDD2}$ for type declarations.
$\begin{array}{|l|l|} \hline {\textbf{SDD1}} \\ \hline { \begin{array}{c} \textbf{Grammar} \\ (G_1) \end{array}} & {\textbf{Semantic Rules}} \\ \hline \hline D \rightarrow TV & \begin{array}{l} D.type = T.type \\ V.type = T.type \end{array} \\ \hline T \rightarrow \text{int} & T.type = \text{int} \\ \hline T \rightarrow \text{float} & T.type = \text{float} \\ \hline V \rightarrow V_1\ \text{id} & \begin{array}{l} V_1.type = V.type \\ \text{put(id.entry, V.type)} \end{array} \\ \hline V \rightarrow \text{id} & \text{put(id.entry, V.type)} \\ \hline \end{array}$

$\begin{array}{|l|l|} \hline {\textbf{SDD2}} \\ \hline { \begin{array}{c} \textbf{Grammar} \\ (G_2) \end{array}} & {\textbf{Semantic Rules}} \\ \hline \hline D \rightarrow D_1\ \text{id} & \begin{array}{l} D.type = D_1.type \\ \text{put(id.entry, D\_1.type)} \end{array} \\ \hline D \rightarrow T\ \text{id} & \begin{array}{l} D.type = T.type \\ \text{put(id.entry, T.type)} \end{array} \\ \hline T \rightarrow \text{int} & T.type = \text{int} \\ \hline T \rightarrow \text{float} & T.type = \text{float} \\ \hline \end{array}$
$D$ is the start symbol, and int, float and 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 put updates the symbol table with the type information for an identifier.

Let $\text{P}$ and $\text{Q}$ be the languages specified by grammars $\text{G1}$ and $\text{G2}$ , respectively.
Which of the following statements is/are true?

View worked solution

Answer: A;B;D

Let us analyze each option step-by-step:

1. Language Equivalence (Option A):

Grammar $G_1$ : The productions are $D \rightarrow T V$ , $T \rightarrow \text{int} \mid \text{float}$ , and $V \rightarrow V \ \text{id} \mid \text{id}$ . This generates a type followed by one or more identifiers: $P = \{\text{int}\ \text{id}^n, \text{float}\ \text{id}^n \mid n \ge 1\}$ .
Grammar $G_2$ : The productions are $D \rightarrow D \ \text{id} \mid T \ \text{id}$ and $T \rightarrow \text{int} \mid \text{float}$ . This also generates a type followed by one or more identifiers: $Q = \{\text{int}\ \text{id}^n, \text{float}\ \text{id}^n \mid n \ge 1\}$ .

Since $P = Q$ , Option A is true.

2. Attributes of SDD2 (Option B):

The attributes defined in $\text{SDD2}$ are $T.type$ and $D.type$ .
$T.type$ is defined directly from terminals (synthesized).
$D.type$ is defined using the attributes of its children ( $T.type$ or $D_1.type$ ), which are also synthesized.
Since every attribute in $\text{SDD2}$ is synthesized, it is S-attributed and contains only synthesized attributes. Thus, Option B is true.

3. Attributes of SDD1 (Option C):

In $\text{SDD1}$ , $V.type$ is an inherited attribute because its value in $D \rightarrow T V$ is defined as $V.type = T.type$ (inherited from sibling $T$ ).
However, $T.type$ and $D.type$ are synthesized attributes. Since $\text{SDD1}$ contains both synthesized and inherited attributes, the claim that it contains only inherited attributes is false. Thus, Option C is false.

4. Symbol Table Entries (Option D):

For any declaration string like $\text{int}\ \text{id}_1\ \text{id}_2\ \dots\ \text{id}_n$ $int id_{1} id_{2} \dots id_{n}$ :
- In $\text{SDD1}$ , the type $\text{int}$ is inherited down the parse tree through $V.type$ , and $\text{put}(\text{id}_i.\text{entry}, \text{int})$ is called for every identifier.
- In $\text{SDD2}$ , the type $\text{int}$ is synthesized up the parse tree through $D.type$ , and $\text{put}(\text{id}_i.\text{entry}, \text{int})$ is called for every identifier.
In both cases, the exact same identifier-to-type mappings are added to the symbol table. Thus, Option D is true.

Free practice · Your answers on this page are not saved.

GATE CS 2026 Set 1 Q43 — Syntax-directed Translation

Related questions