Ullman (Compiler Design) Edition 2 Exercise 5.4 Question 3 (Page No. 337)

Question

The following SDT computes the value of a string of $0's$ and $1's$ interpreted as a positive, binary integer.

• $B\rightarrow B_{1}0\:\{B.val=2\times B_{1}.val\}\mid B_{1}1\:\{B.val=2\times B_{1}.val+1\}\mid 1 \:\{B.val=1\}$

Rewrite this SDT so the underlying grammar is not left recursive, and yet the same value of $B.val$ is computed for the entire input string. 

Answer 1

$B -> 1 \{R.i = 1\} R \{B.val = R.s \}$

$R -> 0 \{R_{1}.i = 2 * R.i\} R_{1} \{R.s = R_{1}.s\}$

$R -> 1 \{R_{1}.i = 2 * R.i + 1\} R_{1} \{R.s = R_{1}.s\}$

$R -> \lambda \{R.s= R.i\}$