Question

Consider the syntax-directed translation with non-terminals N, I, F, B and the rules:

\[ \begin{aligned} N &\to I\ \#\ F \qquad && N.val = I.val + F.val \\ I &\to I_1\ B \qquad && I.val = 2 \times I_1.val + B.val \\ I &\to B \qquad && I.val = B.val \\ F &\to B\ F_1 \qquad && F.val = \tfrac12 \big(B.val + F_1.val\big) \\ F &\to B \qquad && F.val = \tfrac12 B.val \\ B &\to 0 \qquad && B.val = 0 \\ B &\to 1 \qquad && B.val = 1 \end{aligned} \] Find the value computed for the input string 10#011 (rounded to three decimals).

Hint:

The integer rule $I \to I B$ with $I.val=2\,I_1.val+B.val$ accumulates binary digits left-to-right. The fractional rule $F \to B F$ with $F.val=\tfrac12(B.val+F_1.val)$ yields $\sum b_i/2^i$ for bits after ``\#''.

Answer 1

Step 1: Parse the integer part $I$ for ``10''.
Use $I \Rightarrow B$ for the first digit and $I \Rightarrow I_1 B$ to append the next digit.
First digit $1$: $I = B = 1 \Rightarrow I.val = 1$.
Append digit $0$: $I.val = 2 I_1.val + B.val = 2 1 + 0 = 2$.
Hence, $I.val = 2$.
Step 2: Parse the fractional part $F$ for ``011''.
Rule $F \to B F_1$ implements binary fractions: each step weighs the next bit by an extra $\tfrac12$.
Let the three bits be $0,1,1$ (left to right). Then
\[ F.val \;=\; \tfrac12 0 \;+\; \tfrac14 1 \;+\; \tfrac18 1 \;=\; 0 + 0.25 + 0.125 \;=\; 0.375. \]
Step 3: Combine via $N \to I\ \#\ F$.
\[ N.val \;=\; I.val + F.val \;=\; 2 + 0.375 \;=\; 2.375. \]
\[ \boxed{2.375} \]