GATE CS Mastery
Cheat sheets

GATE CS 2024 Set 1 · Compiler Design

Question 37

MCQ2 marksWrong answer: −2/3Easy (estimate)

Question

Consider the following syntax-directed definition (SDD).

S→DHTU{S.val=D.val+H.val+T.val+U.val;}D→"M"D1{D.val=5+D1.val;}D→ϵ{D.val=−5;}H→"L"H1{H.val=5∗10+H1.val;}H→ϵ{H.val=−10;}T→"C"T1{T.val=5∗100+T1.val;}T→ϵ{T.val=−5;}U→"K"{U.val=5;}\begin{aligned} S &\rightarrow DHTU && \{ S.val = D.val + H.val + T.val + U.val; \} \\ D &\rightarrow \text{"M"} D_1 && \{ D.val = 5 + D_1.val; \} \\ D &\rightarrow \epsilon && \{ D.val = -5; \} \\ H &\rightarrow \text{"L"} H_1 && \{ H.val = 5 * 10 + H_1.val; \} \\ H &\rightarrow \epsilon && \{ H.val = -10; \} \\ T &\rightarrow \text{"C"} T_1 && \{ T.val = 5 * 100 + T_1.val; \} \\ T &\rightarrow \epsilon && \{ T.val = -5; \} \\ U &\rightarrow \text{"K"} && \{ U.val = 5; \} \end{aligned}

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

Choose one option
Official answer and solution
Official answer
A
From
Official GATE 2024 answer key

Solution

Parse the input string "MMLK" according to S→DHTUS \rightarrow DHTU and evaluate the synthesized attribute .val.val bottom-up.

For the input string "MMLK", the unique derivation from S→DHTUS \rightarrow DHTU matches D to "MM", H to "L", T to ϵ\epsilon, and U to "K":

  1. D⇒∗"MM"D \Rightarrow^* \text{"MM"}:
    • D2→ϵ  ⟹  D2.val=−5D_2 \rightarrow \epsilon \implies D_2.val = -5
    • D1→"M"D2  ⟹  D1.val=5+(−5)=0D_1 \rightarrow \text{"M"} D_2 \implies D_1.val = 5 + (-5) = 0
    • D→"M"D1  ⟹  D.val=5+0=5D \rightarrow \text{"M"} D_1 \implies D.val = 5 + 0 = 5
  2. H⇒∗"L"H \Rightarrow^* \text{"L"}:
    • H1→ϵ  ⟹  H1.val=−10H_1 \rightarrow \epsilon \implies H_1.val = -10
    • H→"L"H1  ⟹  H.val=50+(−10)=40H \rightarrow \text{"L"} H_1 \implies H.val = 50 + (-10) = 40
  3. T⇒ϵT \Rightarrow \epsilon:
    • T→ϵ  ⟹  T.val=−5T \rightarrow \epsilon \implies T.val = -5
  4. U⇒"K"U \Rightarrow \text{"K"}:
    • U→"K"  ⟹  U.val=5U \rightarrow \text{"K"} \implies U.val = 5

Summing at the root:

S.val=D.val+H.val+T.val+U.val=5+40+(−5)+5=45S.val = D.val + H.val + T.val + U.val = 5 + 40 + (-5) + 5 = 45
Final answer

Option (A)

Common trap

Forgetting that TT still derives ϵ\epsilon with T.val=−5T.val = -5 even when 'C' does not appear in the input string (which would give 50).

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

Source

Paper
GATE 2024 Computer Science and Information Technology - Set 1 (CS1)
Question
37 of 65
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.