GATE CSE 1998 | Question: 23

Question

Let the attribute ‘$val$’ give the value of a binary number generated by $S$ in the following grammar:

• $S \rightarrow L.L \mid L$
• $L \rightarrow LB \mid B$
• $B \rightarrow 0 \mid 1$

For example, an input $101.101$ gives $S.val = 5.625$

Construct a syntax directed translation scheme using only synthesized attributes, to determine $S.val$.

Answer 1

$S\to L.L  \quad\{ S.val = L_1.val + L_2.val/2^{L_2.nb} \}$

$\quad \quad \mid \; L \quad  \{ S.val = L.val \}$

$L\to LB \quad  \{ L.val = 2 * L_1.val + B.val,$
$\qquad \qquad \quad L.nb = L_1.nb + B.nb \}$

$\quad \quad \mid \; B\quad   \{ L.val = B.val$
$\qquad\qquad \quad L.nb = B.nb \}$

$B \to 0  \quad  \{ B.val = 0$
$\qquad\qquad B.nb = 1 \}$

$\quad \quad \mid \; 1   \quad \{ B.val = 1$
$\quad \quad \quad \qquad  B.nb = 1 \}$

Here, $val =$ decimal value, $nb =$ number of bits.

Comments

$Let's\ understand\ a\ little\ with\ an\ Example:$

$.01=\dfrac{1}{2^2}=\dfrac{1}{4}=0.25$

$.11=\dfrac{3}{2^2}=\dfrac{3}{4}=0.75$

$11.01=3+\dfrac{1}{2^2}=3+\dfrac{1}{4}=3+0.25=3.25$

$101.101=5+\dfrac{5}{2^3}=5+\dfrac{5}{8}=5+0.625=5.625$

---

I think instead of this:

$S\to L.L \quad\{ S.val = L_1.val + L_2.val/2L_2.nb \}$

It should be this:

$S\to L.L \quad\{ S.val = L_1.val + \dfrac{L_2.val}{2^{L_2.nb}}\}$

---

Why we are multiplying it with 2? Because:

ex: $1010=10$. Eveyone knows

How to get this:

$\underbrace{1}010:1\times 2+0=2$. Take the first bit, $\times$ it with 2 and add the next bit i.e., $0$

$\underbrace{10}10:2\times 2+1=5$. Take the previous computed value, $\times$ it with 2 and add the next bit i.e., $1$

$\underbrace{101}0:5\times 2+0=10$. Take the previous computed value, $\times$ it with 2 and add the next bit i.e., $0$

---

$L.val= L_{1}.val\times 2+B.val$

$1010=101\times 2+0$

---

@KUSHAGRA गुप्ता

Thanks For the logic :)