GATE CS 2024 Set 1 — Question 37

To find the value of $S.val$ for the input string "MMLK", we first construct the parse tree based on the given grammar productions.1. Parsing the Input "MMLK":
The start symbol is $S$, and the production is S → DHTU.
We need to match the input string "MMLK" to the components $D, H, T, U$.

• Match $D$: The prefix "MM" matches the expansion of $D$.
• $D \to \text{"M"}D_1$
• $D_1 \to \text{"M"}D_2$
• $D_2 \to \epsilon$ (since the next character is 'L', which belongs to $H$)
• Match $H$: The next character "L" matches the expansion of $H$.
• $H \to \text{"L"}H_1$
• $H_1 \to \epsilon$ (since the next character is 'K', and $T$ must be skipped)
• Match $T$: There are no 'C' characters. The next character is 'K', which belongs to $U$. Thus, $T$ must derive $\epsilon$.
• $T \to \epsilon$
• Match $U$: The character "K" matches $U$.
• $U \to \text{"K"}$

2. Computing Attributes (Bottom-Up):
Now we compute the values using the semantic rules.

• For $D$:
• $D_2 \to \epsilon \implies D_2.val = -5$
• $D_1 \to \text{"M"}D_2 \implies D_1.val = 5 + D_2.val = 5 + (-5) = 0$
• $D \to \text{"M"}D_1 \implies D.val = 5 + D_1.val = 5 + 0 = 5$
• For $H$:
• $H_1 \to \epsilon \implies H_1.val = -10$
• $H \to \text{"L"}H_1 \implies H.val = 5 * 10 + H_1.val = 50 + (-10) = 40$
• For $T$:
• $T \to \epsilon \implies T.val = -5$
• For $U$:
• $U \to \text{"K"} \implies U.val = 5$
• For $S$:
• $S \to DHTU \implies S.val = D.val + H.val + T.val + U.val$
• $S.val = 5 + 40 + (-5) + 5$
• $S.val = 45$

Thus, the correct value is 45.