GATE 2024 CS1 Q.37: solution and answer

GATE 2024 · CS1Q.37 · 2 marks · MCQ

Consider the following syntax-directed definition (SDD).

S \to D H T U D \to "M" D_{1} D \to ε H \to "L" H_{1} H \to ε T \to "C" T_{1} T \to ε U \to "K" {S . val = D . val + H . val + T . val + U . val;} {D . val = 5 + D_{1} . val;} {D . val = - 5;} {H . val = 5 * 10 + H_{1} . val;} {H . val = - 10;} {T . val = 5 * 100 + T_{1} . val;} {T . val = - 5;} {U . val = 5;}

Given "MMLK" as the input, which one of the following options is the CORRECT value computed by the SDD (in the attribute $S . val$ )?

GATE 2024 CS1 question 37: A table of eight productions with semantic actions: S -> D H T U S.val = D.val + H.val + T.val + U.val;; — Figure from the GATE 2024 CS1 paper. It is part of the question.

(A)
45
(B)
50
(C)
55
(D)
65

Answer and solution

ANSWER

$S . val = 45$ , option (A).

Official answer: ASource: Official answer key, GATE 2024 CS1 (IISc Bengaluru)

Parse "MMLK" with $S \to D H T U$ : $D$ derives "MM", $H$ derives "L", $T$ derives $ε$ (there is no "C" in the input), and $U$ derives "K".
Every attribute is synthesised, so evaluate bottom-up: each parent takes its value from its children.
$D$ : the innermost $D \to ε$ gives $- 5$ . Then $D \to "M" D_{1}$ applies twice: $5 + (- 5) = 0$ , then $5 + 0 = 5$ . So $D . val = 5$ .
$H$ : $H \to ε$ gives $- 10$ . Then $H \to "L" H_{1}$ gives $5 \cdot 10 + (- 10) = 40$ . So $H . val = 40$ .
$T$ : $T \to ε$ gives $T . val = - 5$ .
$U$ : $U \to "K"$ gives $U . val = 5$ .
Root: $S . val = 5 + 40 + (- 5) + 5 = 45$ , which is option (A).

KEY IDEA

Each nonterminal's value is computed bottom-up from its parse subtree. An $ε$ production still contributes its own constant (here a negative base value), and that constant is added back into the parent's total.

WATCH OUT FOR

Forgetting that the $ε$ productions contribute $- 5$ , $- 10$ and $- 5$ . For example, treating the missing $T$ as $0$ instead of $- 5$ gives $50$ . Counting $D$ as $10$ , with no $- 5$ base, is another slip.

From the GATE 2024 CS1 paper. Every question of this paper · Download the full paper · All 7 Syntax-directed translation questions, with notes

GATE 2024 CS1 Q.37: solution and answer

Answer and solution

More Syntax-directed translation questions