Consider the syntax directed translation given by the following grammar and… — GATE CS 2023 Q50

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

\#, \mathbf{0}

and

\mathbf{1}

are lexical tokens corresponding to input letters

\text{“\#", “0" and “1"},

respectively.

X.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

\mathbf{0}

and

\mathbf{1}, \mathbf{0} . v a l=0

and

\mathbf{1}.val =1

\begin{array}{ll} N \rightarrow I \# F & N.val =I . v a l+F . v a l \\ I\rightarrow I_{1} B & I.val =\left(2 I_{1} . v a l\right)+B.val \\ I \rightarrow B & I.val =\text{ B.val } \\ F \rightarrow B F_{1} & F.val =\frac{1}{2}\left(B . v a l+F_{1} . v a l\right) \\ F \rightarrow B & \text{ F.val }=\frac{1}{2} B.val \\ B \rightarrow \mathbf{0} & B . v a l=\mathbf{0} . v a l \\ B \rightarrow \mathbf{1} & B . v a l=\mathbf{1} . v a l \\ \end{array}

The value computed by the translation scheme for the input string

10\#011

is ____________. (Rounded off to three decimal places)

View worked solution

Answer: 2.375

The input string is $10\#011$ , which is split by the delimiter $\#$ into the integer part $I = 10$ and the fractional part $F = 011$ . We evaluate the synthesized attributes bottom-up.

1. Evaluation of the integer part $I$ for "10":

For the first character '1': $I_1 \rightarrow B \rightarrow \mathbf{1} \implies I_1.val = 1$
For the second character '0': $I \rightarrow I_1 B \rightarrow I_1 \mathbf{0} \implies I.val = 2 \times I_1.val + 0 = 2 \times 1 + 0 = 2$

2. Evaluation of the fractional part $F$ for "011":

The derivation tree for $F \Rightarrow 011$ is $F \rightarrow B_1 F_1 \rightarrow B_1 B_2 F_2 \rightarrow B_1 B_2 B_3$ , where $B_1.val = 0$ , $B_2.val = 1$ , and $B_3.val = 1$ .

$F_2 \rightarrow B_3 \implies F_2.val = \frac{1}{2} B_3.val = \frac{1}{2} \times 1 = 0.5$
$F_1 \rightarrow B_2 F_2 \implies F_1.val = \frac{1}{2} (B_2.val + F_2.val) = \frac{1}{2} (1 + 0.5) = 0.75$
$F \rightarrow B_1 F_1 \implies F.val = \frac{1}{2} (B_1.val + F_1.val) = \frac{1}{2} (0 + 0.75) = 0.375$

3. Evaluation of $N$ :

$N.val = I.val + F.val = 2 + 0.375 = 2.375$

Free practice · Your answers on this page are not saved.

GATE CS 2023 Q50 — Syntax-directed Translation

Related questions