Question 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
   

Question 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)
   

Question 3

1. 2
2. 3
3. 1

Question 4

1. The result of

       x > 0 implies (x = 1 or x > 1 or 1/x > 1)
   

   is always true, in fact, it is:
   1. true if x < 0 or x = 0, because ( x > 0 ) is false
   2. true if x > 0, because either x = 1 is true, or x > 1 is true, or 1/x > 1 is true
   Note in particular that, thanks to the strictness of "implies", the expressions never gives error.
2. 1. call by value cannot be used, because the semantics would be strict
   2. call by value-result cannot be used, because the parameter needs to be a variable.
   3. call by reference cannot be used, for the same reason. (In some languages it is allowed to pass generic expressions, but then the parameter is evaluated at the moment of the call, like in call by value.)
   4. call by name is the only one that can be used

         bool implies(bool name e1, bool name e2){
            if (!e1) 
               return true;
            else 
               return e2;
        }
      

Question 5

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

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
   

Question 6

• x, global variable of type pointer to int, allocated in the space for the globals, lifetime = entire program
• y, formal parameter of p() of type int, allocated on the stack (in the AR of p()), lifetime = execution of p()
• z, local variable of p() of type int, allocated on the stack (in the AR of p()), lifetime = execution of p()
• (anonymous) dynamic variable of type int, allocated on the heap, lifetime = between the execution of "x = new int;" and "delete x;"
  

  ---