GATE 2026 CS (CS1) – Question 53
Consider the following two syntax-directed definitions SDD1 and SDD2 for type declarations:
**SDD1**:
- $D \to T \, V \quad \{ D.type = T.type; \; V.type = T.type; \}$
- $T \to int \quad \{ T.type = int; \}$
- $T \to float \quad \{ T.type = float; \}$
- $V \to V_1 \, id \quad \{ V_1.type = V.type; \; put(id.entry, V.type); \}$
- $V \to id \quad \{ put(id.entry, V.type); \}$
**SDD2**:
- $D \to D_1 \, id \quad \{ D.type = D_1.type; \; put(id.entry, D_1.type); \}$
- $D \to T \, id \quad \{ D.type = T.type; \; put(id.entry, T.type); \}$
- $T \to int \quad \{ T.type = int; \}$
- $T \to float \quad \{ T.type = float; \}$
Let P and Q be the languages specified by grammars G1 and G2, respectively. Which of the following statements is/are true?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (A) The languages P and Q are the same; (D) The specifications of SDD1 and SDD2 are such that the same entries get added to the symbol table
Explanation
- **Statement (A)**: Both grammars G1 and G2 generate the language of type declarations consisting of a type (`int` or `float`) followed by a non-empty sequence of identifiers `id` (e.g. `int a b c` or `float x y`). Hence, $L(G1) = L(G2)$, meaning languages P and Q are identical. Statement (A) is TRUE.
- **Statement (B)**: In SDD2, the semantic rules execute side effects via `put(id.entry, ...)` and define attributes. However, SDD2 is an S-attributed definition since all defined attributes are synthesized (computed from children), but statement (B) claims it contains *only* synthesized attributes while ignoring side effects. More importantly, in SDD1, attributes like $V.type$ are inherited from parent/sibling $T$. SDD1 contains both synthesized ($T.type$) and inherited ($V.type$) attributes, so statement (C) is FALSE ('contains only inherited attributes' is incorrect because $T.type$ is synthesized).
- **Statement (D)**: For any given valid input declaration string, both SDD1 and SDD2 associate each identifier in the declaration with the declared type and invoke `put` with the identical identifier entry and type. Statement (D) is TRUE.
Therefore, statements (A) and (D) are true.