GATE CS 2019 Q.46 (CS Q.36): Syntax-Directed Translation

Consider the following grammar and the semantic actions to support the inherited type declaration attributes. Let $X_1, X_2, X_3, X_4, X_5,$ and $X_6$ be the placeholders for the non-terminals $D, T, L$ or $L_1$ in the following table:

Production rule	Semantic action
$D \to T \; L$	$X_1.\text{type} = X_2.\text{type}$
$T \to \text{int}$	$T.\text{type} = \text{int}$
$T \to \text{float}$	$T.\text{type} = \text{float}$
$L \to L_1 , \text{id}$	$X_3.\text{type} = X_4.\text{type}; \quad \text{addType}(\text{id.entry}, X_5.\text{type})$
$L \to \text{id}$	$\text{addType}(\text{id.entry}, X_6.\text{type})$

Which one of the following are the appropriate choices for $X_1, X_2, X_3$ and $X_4$ ?

$X_1 = L, \; X_2 = T, \; X_3 = L_1, \; X_4 = L$

$X_1 = T, \; X_2 = L, \; X_3 = L_1, \; X_4 = T$

$X_1 = L, \; X_2 = L, \; X_3 = L_1, \; X_4 = T$

$X_1 = T, \; X_2 = L, \; X_3 = T, \; X_4 = L_1$

Official answer and solution

Official answer: A
From: Official GATE 2019 answer key

Solution

Track how type information flows from production head to children in syntax-directed translation schemes.

In syntax-directed translation schemes for variable declarations:

For the declaration rule $D \to T \; L$ :
The non-terminal $T$ synthesizes a type attribute ( $T.\text{type} = \text{int}$ or $\text{float}$ ). This type must be inherited by the identifier list $L$ . Therefore, the semantic action is: $L.\text{type} = T.\text{type}$ Comparing with $X_1.\text{type} = X_2.\text{type}$ , we obtain $X_1 = L$ and $X_2 = T$ .

For the identifier list rule $L \to L_1 , \text{id}$ :
The list $L_1$ must inherit the exact same type attribute that was passed down to $L$ . Therefore, the semantic action is: $L_1.\text{type} = L.\text{type}$ Comparing with $X_3.\text{type} = X_4.\text{type}$ , we obtain $X_3 = L_1$ and $X_4 = L$ .

Thus, the appropriate choices are $X_1 = L, X_2 = T, X_3 = L_1, X_4 = L$ (Option A).

Final answer

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

Source

Paper: GATE 2019 Computer Science and Information Technology (CS)
Question: 46 of 65, printed as CS Q.36
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