Answers to Self-Study Questions

Self-Study #1

---

Question 1

CFG Production				Translation Rule
B	$\longrightarrow$	0		B.trans = $0$
B	$\longrightarrow$	1		B.trans = $1$
B	$\longrightarrow$	B 0		B1.trans = B2.trans $\times$ $2$
B	$\longrightarrow$	B 1		B1.trans = B2.trans $\times$ $2$ $+$ $1$

---

Question 2

Input: 1001


        Annotated Parse Tree
        ====================
              (9) B 
                 / \
                /   \
           (4) B     1
              / \
             /   \
        (2) B     0
           / \
          /   \
     (1) B     0
         |
         1

      

---