GATE CS 2023 Q.60: Syntax-Directed Translation

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.\text{val}$ denotes the synthesized attribute (a numeric value) associated with a non-terminal $X$ . $I_1$ and $F_1$ denote occurrences of $I$ and $F$ on the right hand side of a production, respectively. For the tokens 0 and 1, $0.\text{val} = 0$ and $1.\text{val} = 1$ .

\begin{aligned} N &\rightarrow I \; \# \; F && N.\text{val} = I.\text{val} + F.\text{val} \\ I &\rightarrow I_1 \; B && I.\text{val} = (2 \cdot I_1.\text{val}) + B.\text{val} \\ I &\rightarrow B && I.\text{val} = B.\text{val} \\ F &\rightarrow B \; F_1 && F.\text{val} = \frac{1}{2} (B.\text{val} + F_1.\text{val}) \\ F &\rightarrow B && F.\text{val} = \frac{1}{2} B.\text{val} \\ B &\rightarrow 0 && B.\text{val} = 0.\text{val} \\ B &\rightarrow 1 && B.\text{val} = 1.\text{val} \end{aligned}

The value computed by the translation scheme for the input string

10\#011

is _______. (Rounded off to three decimal places)

Your answer

Official answer and solution

Accepted answers: 2.374 to 2.376
From: Official GATE 2023 answer key

Solution

Evaluate the synthesized attributes according to the syntax directed translation rules.

For input string 10#011:

Integer part ( $I$ ) for 10:
- $I \rightarrow B \rightarrow 1 \implies I_1.\text{val} = 1$ .
- $I \rightarrow I_1 \; B$ with $B \rightarrow 0 (B.\text{val} = 0) \implies I.\text{val} = 2(1) + 0 = 2$ .
Fractional part ( $F$ ) for 011 (evaluated right-to-left due to right recursion $F \rightarrow B F_1$ ):
- Third bit (1): $F \rightarrow B \rightarrow 1 \implies F_2.\text{val} = \frac{1}{2}(1) = 0.5$ .
- Second bit (1): $F \rightarrow B \; F_2$ with $B \rightarrow 1 \implies F_1.\text{val} = \frac{1}{2}(1 + 0.5) = \frac{1.5}{2} = 0.75$ .
- First bit (0): $F \rightarrow B \; F_1$ with $B \rightarrow 0 \implies F.\text{val} = \frac{1}{2}(0 + 0.75) = \frac{0.75}{2} = 0.375$ .
Root rule $N \rightarrow I \; \# \; F$ :
$N.\text{val} = I.\text{val} + F.\text{val} = 2 + 0.375 = 2.375$

Final answer

2.375

Common trap

Evaluating the fractional part left-to-right rather than following the right-recursive grammar derivation tree.

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

Source

Paper: GATE 2023 Computer Science and Information Technology (CS)
Question: 60 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.

Question

Solution

Source