Spring 2001, CSE 428: Solution of test 1

Question 1

    1. yes
    2. yes
    3. no
    4. yes
  1. 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.
  2.      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. 
    
    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

The following variables are active during the execution of p():