Exercise 1

1. 1. yes
   2. no
   3. no
   4. yes
2. One reason why the grammar is ambiguous is taht there is no rule for associativity of +. Thus a string like 2+3+4 has two different derivation trees.

               Exp                   Exp
              / | \                 / | \
             /  |  \               /  |  \
           Exp  +  Exp           Exp  +  Exp
          / | \     |             |     / | \
         /  |  \    |             |    /  |  \
       Exp  +  Exp Num           Num Exp  +  Exp
        |       |   |             |   |       |
        |       |   |             |   |       |
       Num     Num  4             2  Num     Num
        |       |                     |       |
        |       |                     |       |
        2       3                     3       4
   

3.    Exp ::= Exp + A | A
        A ::= ~A  | B
        B ::= Num | (Exp)
      Num ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
   

Exercise 2

1. We need to change the production

      Exp ::= let Ide = Num in Exp end
   

   into

      Exp ::= let Ide = Exp in Exp end
   

2. We only need to change the following line in the "dec" case

      int k = t->get_left()->get_root()->get-value()
   

   into

      int k = eval(t->get_left(),r)
   

Exercise 3

1. 2
2. 2
3. 1

Exercise 4

1. • (a) the output is 1
   • (b) the output is 2

2. 
   
   caller of p        p I           A.R. where p is declared
           ^   ------------------      ^ 
        CL |___|_               |      | 
               |                |      |
               ------------------      |
               |               _|______| SL
               |                |
               ------------------
           |-->|        -----   |<-|---|----| 
           |   |      x | 1 |   |  |   |    |           
           |   |        -----   |  |   |    |
           |   |      y | 2 |   |  |   |    |
           |   |        -----   |  |   |    |
        CL |   ------------------  |   |    |
           |                       |   |    |
           |          q I          |   |    |
           |   ------------------  |   |    |
           |___|_               |  |   |    | 
               |                |  |   |    |
               ------------------  |   |    |
               |               _|__|SL |    |
               |                |      |    |
               ------------------      |    |
           |-->|        -----   |      |    |
           |   |      y | 1 |   |      |    |
           |   |        -----   |      |    |
        CL |   ------------------      |    |
           |                           |    |
           |          r I              |    |
           |   ------------------      |    | 
           |___|_               |      |    |
               |                |      |    |
               ------------------      |    | 
               |               _|______| SL |
               |                |           |
               ------------------           |
           |-->|        -----   |           |
           |   |      x | 1 |   |           |
           |   |        -----   |           |
        CL |   ------------------           |
           |                                | 
           |          Q II                  |
           |   ------------------           |
           |___|_               |           |
               |                |           |
               ------------------           |
               |               _|___________| SL 
               |                |
               ------------------
               |        -----   |
               |      y | 2 |   |
               |        -----   |
               ------------------      
   
       CL = Control Link
       SL = Static  Link
   

Exercise 5

1. ML yes, DR no
2. ML no, DR no
3. ML no, DR yes
4. ML no, DR no
5. ML yes, DR no