GATE 2023 CS Q.60: solution and answer

GATE 2023 · CSQ.60 · 2 marks · NAT

Consider the syntax directed translation given by the following grammar and semantic rules. Here N, I, F and B are non-terminals. N is the starting non-terminal, and #, 0 and 1 are lexical tokens corresponding to input letters "#", "0" and "1", respectively. X.val denotes the synthesized attribute (a numeric value) associated with a non-terminal X. I1 and F1 denote occurrences of I and F on the right hand side of a production, respectively. For the tokens 0 and 1, 0.val = 0 and 1.val = 1.

N → I # F N.val = I.val + F.val
I → I1 B I.val = (2 I1.val) + B.val
I → B I.val = B.val
F → B F1 F.val = (1/2)(B.val + F1.val)
F → B F.val = (1/2) B.val
B → 0 B.val = 0.val
B → 1 B.val = 1.val

The value computed by the translation scheme for the input string 10#011 is ______. (Rounded off to three decimal places)

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The value computed for the input 10#011 is 2.375.

Official answer: 2.374 to 2.376Source: Official answer key, GATE 2023 CS (IIT Kanpur)

Split the input $10#011$ as $I # F$ with $I \Rightarrow 10$ and $F \Rightarrow 011$ . All attributes are synthesized, so evaluate bottom-up.
Integer part: $I_{1} \Rightarrow 1$ uses $I \to B$ , so $I_{1} . val = B . val = 1$ . Then $I \to I_{1} B$ with $B \Rightarrow 0$ gives $I . val = 2 \cdot 1 + 0 = 2$ .
Fraction part, $F \Rightarrow 011$ . The last digit comes from $F \to B$ : $F . val = \frac{1}{2} \cdot 1 = 0.5$ .
The second digit $1$ uses $F \to B F_{1}$ with $F_{1} . val = 0.5$ : $F . val = \frac{1}{2} (1 + 0.5) = 0.75$ .
The first digit $0$ uses $F \to B F_{1}$ with $F_{1} . val = 0.75$ : $F . val = \frac{1}{2} (0 + 0.75) = 0.375$ . This agrees with the binary fraction $0.01 1_{2} = 0.375$ .
At the root, $N \to I # F$ : $N . val = I . val + F . val = 2 + 0.375 = 2.375$ .

KEY IDEA

The grammar reads the integer part as a binary number (each new digit doubles the value so far and adds itself), and the fraction part as a binary fraction built from the right: each digit adds to the value of the rest and halves it. So 10 gives 2, 011 gives 0.375, and the sum is 2.375.

WATCH OUT FOR

Evaluating the fraction from the left, or halving the digits in the wrong order. The rule $F \to B F_{1}$ puts the leftmost digit at weight 1/2, so the recursion must start from the last digit. Starting from the first digit gives a wrong value.

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

GATE 2023 CS Q.60: solution and answer

Answer and solution

More Syntax-directed translation questions