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