Question 1

1. 1. yes
   2. yes
   3. no
   4. yes
2. One reason why the grammar is ambiguous is that there is no rule for associativity of +. Thus a string like a+b+c has two different derivation trees.

               E                   E
              /|\                 /|\
             / | \               / | \
            E  +  E             E  +  E
           /|\    |             |    /|\
          / | \   |             |   / | \
         E  +  E  A             A  E  +  E
         |     |  |             |  |     |
         |     |  |             |  |     |
         A     A  c             a  A     A
         |     |                   |     |
         |     |                   |     |
         a     b                   b     c
   

   There are also are causes of ambiguity: the associativity of the concatenation and the priority of the various operators.

3.      E ::= E+A | A
        A ::= AB | B
        B ::= B* | C
        C ::= a | b | c | (E)
   

Question 2

1. We need to add the productions

      Exp ::= max(Exp,Exp)
   

2. One way to cope with the proposed extension is to modify the class node by adding another type of node, say "ma"x, and to modify the interpreter by adding the following case in switch(ty):

              case "max" : {  
                  int k1 = eval(t->get_left(), r); 
                  int k2 = eval(t->get_right(), r); 
                  if (k1 > k2) 
                     return k1;
                  else
                     return k2;
                  }
               } 
   

   Another possibility would have been to represent max, in the parse trees, as another operator. In that case it would be sufficient to add the following case in switch(n->get_op()):

              case "max" : {  
                  if (k1 > k2) 
                     return k1;
                  else
                     return k2;
                  }
               } 
   

Question 3

1. 3
2. 4
3. 2

Question 4

1. • (a) the output is 1
   • (b) the output is 3

2. 
   
   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 | 3 |   |
               |        -----   |
               ------------------      
   
       CL = Control Link
       SL = Static  Link
   

Question 6

• y, global variable of type pointer to int, allocated in the space for the globals, lifetime = entire program
• w, global variable of type int, allocated in the space for the globals, lifetime = entire program
• x, formal parameter of foo() of type int, allocated on the stack (in the AR of foo()), lifetime = execution of foo()
• z, local variable of foo() of type pointer to int, allocated on the stack (in the AR of foo()), lifetime = execution of foo()
• (anonymous) dynamic variable of type int, allocated on the heap, lifetime = between the execution of "z = new int;" and "delete x;"
  

  ---