Spring 2000, CSE 428: Test 1

Question 1

Consider the following grammar, generating a subset of the language of types of a generic imperative language:
   Type ::= int | bool | ^Type | Type * Type | (Type)
where "int", "bool", "^", "*", "(" and ")" are terminal symbols.
  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

Consider the language of expressions seen in class
   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
and the interpreter eval for such language
   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);                   
Assume that we want to modify the language by adding negative expressions. More precisely, we want to add a unary operator "~", whose meaning is to change the sign of the value of the argument. For instance, if the value of x is 5, then the value of ~x should be -5. If the value of y is 2 and the value of z is 7, then the value of 5 * (~(~y + z)) should be -25. Show how the grammar and the eval function should be modified so to cope with such an extension.

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

Consider the following function declaration:
   int f(int <parameter passing-method> x){
      x = x+1;
      y = y+2;
      return x + y;
where y is a global variable of type integer. Say what is the final value of y after the following fragment of code:
      y = 0;
      y = f(y);
under each of the following assumptions:
  1. Call by value
  2. Call by reference
  3. Call by value-result

Question 4

Assume that we want to enrich the language of boolean expressions with the boolean operator "implies" (logical implication), by adding the production
   Exp ::= Exp implies Exp
and with a non-strict semantics of the following form:
   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

Consider the following procedure declaration in a Pascal-like language:
   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;      
            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;
      end;    /* end body of p */
Assume that at a certain point, the main program contains a call of the form
  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

Consider the following declarations in C++
   class list{
      int info;
      list* next;
      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;
For each of the following declarations of p, say whether a call to p leaves memory leaks and/or dangling references. (Note: "a call to p leaves ml/dr" means "after a call to p returns, we have ml/dr".)
  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();
  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();