CSE 428, Spring 99: Solutions of Midterm 1

Exercise 1

  1. The grammar is not ambiguous. In fact, all the productions are distinguished by the first token generated, except for the production of <Stat_list> (which, in principle, could cause an ambiguity problem with associativity) and for the 2nd and 3rd productions of <Statement (which, in principle, could cause a dangling-else ambiguity). However, the associativity problem is avoided by making "unguarded" recursion (i.e. derivation of <Stat_list>) only at the right of ";", and the dangling-else ambiguity is avoided by having an "end" at the end of the <Stat_list> in the 2nd production.
  2. ";" is enforced to be right-associative.

Exercise 2

  1. With the given semantic specification, nand is non-strict. In fact, whenever the first operand results false, the second is not evaluated.

Exercise 3

  1. In Pascal:
    function sum_list(l:list):integer;
       begin
       if isempty(l) 
          then sum_list := 0
          else sum_list := head(l) + sum_list(tail(l))
       end;
    
    In C:
    int sum_list(list l){
        if (isempty(l))
           return 0;
        else 
           return head(l) + sum_list(tail(l));       
    } 
    
  2. It is not tail recursive: in the else-branch, after the recursive call, we need to perform the sum.

Exercise 4

  1. 
    
    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 | 2 |   |           |
            |   |        -----   |           |
         CL |   ------------------           |
            |                                | 
            |          Q II                  |
            |   ------------------           |
            |___|_               |           |
                |                |           |
                ------------------           |
                |               _|___________| SL 
                |                |
                ------------------
                |        -----   |
                |      y | 2 |   |
                |        -----   |
                ------------------      
    
        CL = Control Link
        SL = Static  Link
    

Exercise 5

  1. Note: I run the above program on Unix, with the g++ compiler, and I obtained indeed as output first 5 and then 6 in both cases (a) and (b).

    Another way in which foo2 can change the value of *p is by using pointer arithmetic: foo2 might assign to a local pointer exactly the location pointed by p and then change its value.