The Gateway to Computer Science Excellence
+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. 

in Compiler Design by Veteran (59.3k points) | 27 views

1 Answer

0 votes
$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)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,382 answers
198,530 comments
105,323 users