Spring 2000, CSE 428: Solution of test 1
Question 1
 For each of the following strings, say whether or not they can be derived
from the grammar
 ^^bool can be derived
 int^bool cannot be derived
 int^*bool cannot be derived
 int*^bool can be derived
 The grammar has two kinds of ambiguities. One is related to the associativity of
*: int * int * int can be generated with two different trees. The other is related to
the priority between * and ^: ^ int * int can be generated with two different trees.
 One possible unambiguous grammar for the same language is the following:
Type ::= Type * A  A
A ::= ^A  B
B ::= int  bool  (Type)
 The above grammar enforces leftassociativity for * and the precedence of ^ over *.
Question 2
The grammar should be enriched by adding a production Exp ::= ~Exp.
Hence:
Exp ::= Num  Ide  Exp Op Exp  ~Exp  let Ide = Num in Exp end  (Exp)
We can assume that an expression of the form ~e is represented by a tree which has operator ~ in the root and
e represented in the left subtree.
The interpreter eval for such language should then be changed as follows (the only modifications are in the "op" case)
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);
string op = n>get_op();
if (op=="~")
return k1;
else {
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);
}
}
}
Question 3
 Call by value: 3
 Call by reference: 6
 Call by valueresult: 3
Question 4
 The result of
x > 0 implies (x = 1 or x > 1 or 1/x > 1)
is always true, in fact, it is:
 true if x < 0 or x = 0, because ( x > 0 ) is false
 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.

 call by value cannot be used, because the semantics would be strict
 call by valueresult cannot be used, because the parameter needs to be a variable.
 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.)
 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

 Under static scope the procedure call prints 0 and then returns
 Under dynamic scope the procedure call prints 1 and then returns

caller block where
of p p is defined
p I
^  ^
CL ____  
  
 
 _______ SL
 

>  <
  x  1    
     
  y  0    
     
CL    
  
 q I  
   
____   
   
  
 _______ SL 
  
 
> < 
    
    
CL    
  
 r I  
   
____   
   
  
 _______ SL 
  
 
>   
  x  0   
    
CL   
 
 q II 
  
____  
  
 
 ____________ SL
 

 
 
 

CL = Control Link
SL = Static Link
Question 6

There is some memory leak: the locations allocated by makelist()
are never deallocated.
There is no dangling reference.

There is some memory leak, for the same reason as before
(the assignment l = NULL as no effect wrt deallocation).
There is no dangling reference.

There is no memory leak: the instruction delete(l)
activates the list destructor, which deallocates
all the elements of the list pointed by l.
There is no dangling reference after p returns (the pointer l is deallocated).

There is no memory leak: when p returns, l is deallocated and
this causes the activation of the list destructor. (Note that
this is different from the situation in which l is a pointer
to list).
There is no dangling reference.

There is no memory leak: the list starting from l is deallocated.
There is a dangling reference: the field next of the element
pointed by m is
now dangling.