Question 1

   Type ::= int | bool | ^Type | Type * Type | (Type)

1. For each of the following strings, say whether or not they can be derived from the grammar
   1. ^^bool
   2. int^bool
   3. int^*bool
   4. int*^bool
2. Show that the grammar is ambiguous.
3. Give an unambiguous grammar generating the same language.
4. State what associativity and precedence rules your grammar enforces.

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();
               environment* r1 = r->add(x,k);
               return eval(t->get_right(), r1);                   
            }    
          }
   }

Note: Such extension is in a sense redundant, because the value of ~e can be expressed already by writing 0 - e. But anyway, the exercise is realistic because most programming languages allow the unary minus operator.

Question 3

   int f(int <parameter passing-method> x){
      x = x+1;
      y = y+2;
      return x + y;
   }

      y = 0;
      y = f(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(x:integer);
      var y:integer; /* declaration of a variable y local to p */
      procedure q; /* declaration of a procedure q local to p */
         procedure r; /* declaration of a procedure r local to q */ 
            var x:integer; /* declaration of a variable x local to r */
            begin     /* begin body of r */
            x := 0;      
            q
            end;     /* end body of r */
         begin     /* begin body of q */
         if x = y 
            then begin y := y - 1; r end
            else write(y)
         end;      /* end body of q */
      begin   /* begin body of p */
      y := x;
      q
      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

   class list{
      int info;
      list* next;
   public:
      list(){ info = 0; next = NULL; }
      list(int x, list* l){ info = x; next = l; }
      ~list(){ delete next; }
      int length(){ //returns the length of the list
          int n = 0;
          list* l = this;
          while(l->next!=NULL){ l = l->next; n++; }
          return n;
      }
   };

   list* makelist(){ //reads a sequence of integers and returns them in a list
      int x;
      list* l = new list();
      cin >> x;
      while(x!=0){ l = new list(x,l); cin >> x; }
      return l;
   }

1.    void p(){
         cout << makelist()->length();
      }
      

2.    void p(){
         list* l = makelist();
         cout << l->length();
         l = NULL;
      }
      

3.    void p(){
         list* l = makelist();
         cout << l->length();
         delete(l);
      }
      

4.    void p(){
         list l = list(42,makelist());
         cout << l.length();
      }
      

5.    void p(){
         list l = list(42,makelist());
         m = new list(53, &l); // m is a global variable of type list*
         cout << m->length();
      }