Question 1

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

1. For each of the following strings, say whether it is derivable from the grammar or not
   1. (~ (~ 0))
   2. 2 ~ 1
   3. 21
   4. 2 + ~ 1
2. Prove that the grammar is ambiguous.
3. Give an equivalent unambiguous grammar for the same language, defined in such a way that + is left associative and ~ has precedence over +.

Question 2

   Exp ::=  Num | Ide | Exp Op Exp | let Ide = Num in Exp end | (Exp)
   Op  ::=  + | * | - | / 
   Num ::=  ... // sequence of digits representing a natural number
   Ide ::=  ... // sequence of letters

   int eval(tree* t, environment* r){
          node* n = t->get_root();
          string ty = n->get_type();
          switch (ty) {
            case "num": 
               return n->get_value();
            case "ide": 
               return r->lookup(n->get_ide());
            case "op" : {  
               int k1 = eval(t->get_left(), r); 
               int k2 = eval(t->get_right(), r); 
               switch (n->get_op()) {
                  case "+": 
                     return k1 + k2;
                  case "*": 
                     return k1 * k2;
                  case "-": 
                     return k1 - k2;
                  case "/": 
                     return k1 / k2;
               }
            } 
            case "dec": {  
               string x = n->get_ide();
               int k = t->get_left()->get_root()->get_value();
               r->add(x,k);
               int result = eval(t->get_right(), r);
               r->pop();
               return result;
            }    
          }
   }

   let x = 1
    in let y = 2
        in let x = x + y
            in x
           end
       end
   end

1. Show how the grammar should be modified so to cope with such an extension.
2. Show how the eval function should be modified so to cope with such an extension.

Question 3

   void p(int <parameter-passing method> x){
      int temp;
      temp = x;
      x = y + 1;
      y = temp + y + 2;
   }

      y = 0;
      p(y);

1. Call by value
2. Call by reference
3. Call by value-result

Question 4

   Exp ::= Exp implies Exp

   the result of e1 implies e2 is
   - true if e1 is false
   - true if e1 is true and e2 is true
   - false if e1 is true and e2 is false

1. For every possible value of x, say what is the result (true, false or error) of the following expression, where x is declared as an integer:

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

2. Define a function which implements the above "implies" operator, and discuss which of the following parameter-passing methods can/cannot be used:
   1. value
   2. value-result
   3. reference
   4. name
   Note: the function implementing "implies" should be defined in such a way that we can call it on arbitrary boolean expressions, like x>0, (x = 1 or x > 1 or 1/x > 1) etc.

Question 5

   procedure p; 
      var x,y: integer;                                (* variables x,y local to p *)
      procedure q(y: integer);                         (* procedure q local to p   *)
         begin if x = y then r(y) else write(y) end;   (* body of q                *)
      procedure r(x: integer);                         (* procedure r local to p   *)
         begin if x = y then write(y) else q(x+1) end; (* body of r                *)
      begin                                            (* begin body of p          *)
      x := 1;                                          (* assign 1 to x            *)
      y := 2;                                          (* assign 2 to y            *)       
      q(x)                                             (* call to q with actual x  *)
      end;                                             (* end body of p            *)

   p(1);

1. Describe the effect of such call under
   1. static scope
   2. dynamic scope
2. In the case of static scope, show the stack snapshot (i.e. the configuration of the activation records on the stack) at the moment in which the instruction write(y) is executed. In particular, show the static and the control links. Please use a drawing.

Question 6

   int* x;
   void p(int y){ int z = 2; *x = y+z; }
   void main(){
      x = new int;
      *x = 3;
      p(*x);
      cout << *x;
      delete x;
      ...
   }