L.dv = 2 * L_{1}.dv + B.dv here why 2 is multiplied?

The Gateway to Computer Science Excellence

+15 votes

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

+26 votes

Best answer

$S\to L.L \quad\{ S.val = L_1.val + L_2.val/2L_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.

$\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.

+5

$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}}\}$

0

**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$

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.6k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,833 questions

57,733 answers

199,458 comments

107,893 users