+1 vote
27 views

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.

| 27 views

$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\}$
by Active (2.2k points)