GATE CS 2024 Set 1 Q27 — Syntax-directed Translation

To find the value of the attribute $S.val$ for the input string "MMLK", we first construct the parse tree based on the grammar rules and then compute the synthesized attributes bottom-up.

1. Parsing the Input "MMLK"

The start symbol is $S$, which derives $D H T U$. We match the input string "MMLK" to these non-terminals:

• $D$ matches "MM": $$D \rightarrow \text{"M"} D_1 \rightarrow \text{"M"} \text{"M"} D_2 \rightarrow \text{"M"} \text{"M"} \epsilon$$
• $H$ matches "L": $$H \rightarrow \text{"L"} H_1 \rightarrow \text{"L"} \epsilon$$
• $T$ matches $\epsilon$: $$T \rightarrow \epsilon$$
• $U$ matches "K": $$U \rightarrow \text{"K"}$$

2. Evaluating the Attributes

Now, we compute the synthesized attributes for each subtree:

Evaluating $D.val$:

• For $D_2 \rightarrow \epsilon$: $$D_2.val = -5$$
• For $D_1 \rightarrow \text{"M"} D_2$: $$D_1.val = 5 + D_2.val = 5 + (-5) = 0$$
• For $D \rightarrow \text{"M"} D_1$: $$D.val = 5 + D_1.val = 5 + 0 = 5$$

Evaluating $H.val$:

• For $H_1 \rightarrow \epsilon$: $$H_1.val = -10$$
• For $H \rightarrow \text{"L"} H_1$: $$H.val = 5 \times 10 + H_1.val = 50 + (-10) = 40$$

Evaluating $T.val$:

• For $T \rightarrow \epsilon$: $$T.val = -5$$

Evaluating $U.val$:

• For $U \rightarrow \text{"K"}$: $$U.val = 5$$

3. Computing $S.val$

Using the semantic rule for $S \rightarrow D H T U$:

Thus, the correct value computed by the SDD is 45.