Test 2      

Abstract Syntax Tree
 
program = main_class class_decl*;
main_class = [classname]:id [arg]:id statement;
class_decl =
     id var_decl* method_decl* |
             {extends} [classname]:id
                             [extend]:id var_decl* method_decl*;
var_decl = type id;
method_decl = type id formal_list var_decl* statement* exp;
statement =
             {statementlist} statement* |
             {if} exp [true]:statement [false]:statement |
             {while} exp statement |
             {println} exp |
             {assign} id exp |
             {array_assign} id [index]:exp [r]:exp;
formal_list = type id formal_rest* | {empty};
formal_rest = type id;
 
type=   {int_array} |
            {boolean}   |
            {int}        |
            {id} id;
exp =    {and}   [l]:exp [r]:exp |
             {lt}    [l]:exp [r]:exp |
             {plus}  [l]:exp [r]:exp |
             {minus} [l]:exp [r]:exp |
             {times} [l]:exp [r]:exp |
             {length} exp                   |
             {arrayindex} [array]:exp [index]:exp |
             {methodcall} exp id exp_list |
             {integerliteral} integer_literal |
             {trueliteral} true |
             {falseliteral} false |
             {id} id |
             {this} this |
             {new} id |
             {newarray} exp |
             {not}     exp ;
exp_list = exp*;
  1. For the MiniJava abstract syntax above, what must be stored in the symbol table for each:
    1. variable    type id
    2. statement    nothing
    3. method_decl type id formal_list var_decl*
  2. For the MiniJava abstract syntax above, what methods need to be implemented for type checking the following?
    1. 4 * a    AIntegerliteralExp ATimesExp AIdExp
    2. while(a<b) a = a + 1; AIntegerliteralExp APlusExp AIdExp ALtExp AWhileStm AAssignStm
  3. Give the method for type-checking
    1. falseliteral
       
      public void caseAFalseliteralExp(AFalseliteralExp node) {
        setType(node, new ABooleanType());
      }
    2. lt
      public void caseALtExp(ALtExp node) {
        node.getL().apply(this);
        if (! ((Node)getType(node.getL()) instanceof AIntType) ) {
          System.out.println("Left side of < must be of type integer");
          System.exit(-1);
        }
        node.getR().apply(this);
        if (! ((Node)getType(node.getR()) instanceof AIntType) ) {
         System.out.println("Right side of < must be of type integer");
         System.exit(-1);
        }
        setType(node,new ABooleanType());
      }
  1. public class Q1 {
  2.     public static void main(String [] args) {
  3.        Q2 qa = new Q2();
  4.        Q2 qb = new Q2();
  5.        qa.f1( qb, 5);
  6.     }
  7. }
  1. class Q2 {
  2.    int a;
  3.    public void f1( Q2 q, int n ) {  
  4.        int i;
  5.        int j;
  6.        i = n;
  7.        j = i + 1;
  8.        n = q.f2();
  9.        this.a = n;
  10.    }
  11. }
  1.    public int f2( ) {  
  2.        int i;
  3.        i = 3;
  4.        return i;
  5.    }
  6. }

 
  1. (2) Diagram the stack (show TOS) for the method call:  qa.f1( qb, 5 );
qa.f1( qb, 5 )
0 qa
1  qb
2 TOS 5
  1. (6) Diagram the JVM frame contents (show both formal and actual parameters) for the two method calls starting with: qa.f1( qb, 5 );
    qa.f1( qb, 5 )
    0 this=qa
    1 q=qb
    2 n=5
    3 i
    4 j
    		q.f2()
    0 this=qb=q
    1 i

     
  2. (2) Diagram the stack (show TOS) for the method call:  q.f2(  );

    q.f2( )

    0 TOS q=qb

     

  3. Give the IR for the following:
    1. (2) 3 - 5 - 4
       
      BINOP(
       MINUS,
       BINOP(
        MINUS,
        CONST 3,
        CONST 5
       ),
       CONST 4
      )
    2. (3) a = 3-5, assume a is in frame at offset 7 and TEMP(fp) is the frame pointer value.
      MOVE(
        MEM(
         BINOP(
           PLUS,
           TEMP fp,
           CONST 7)),
        BINOP(MINUS,
          CONST 3,
          CONST 5))
    3. (3) a = b-3, assume a and b are in frame at offset 7 and 9 respectively and TEMP(fp) is the frame pointer value.
       
      MOVE(
        MEM(
          BINOP(
           PLUS,
           TEMP fp,
           CONST 7)),
         BINOP(
           MINUS,
           MEM(
              BINOP(
                PLUS,
                TEMP fp,
                CONST 9)),
           CONST 3))
    4. (4) 4 < a, assume a is in frame at offset 5 and TEMP(fp) is the frame pointer value.
       
      ESEQ(
        SEQ(
          SEQ(
            SEQ(
              MOVE(TEMP(t2),CONST(0)),
              CJUMP(
                Tree.CJUMP.LT,
                CONST(4),
                MEM(
                  BINOP(
                    BINOP.PLUS,
                    TEMP(fp),
                    CONST(5)
                  )
                ),
                T,
                F
              )
            ),
            SEQ(
              LABEL(T),
              MOVE(TEMP(t2),CONST(1))
            )
          ),
          LABEL(F)
        ),
        TEMP(t1)
      )
    5. (6) while ( 4<a )
           a = b-3
      SEQ(
            SEQ(
                  SEQ(
                        LABEL(test),
                        CJUMP(Tree.CJUMP.EQ,
                                  condition
                                  CONST(1),T,F)
                  ),
                  SEQ(
                        SEQ(
                            LABEL(T),
                            body
                         ),
                         Tree.JUMP( test )
                   )
            ),
            LABEL(F)
      )

      condition from d.

      body from c.
  1. (9) Give the linearization of each of the following:
    1. SEQ(MOVE(TEMP(t0),CONST(4)),SEQ(MOVE(TEMP(t0), CONST(3)),SEQ(MOVE(TEMP(t0), CONST(2)),MOVE(TEMP(t0),CONST(1))))) Þ
       
      MOVE(
       TEMP t0,
       CONST 4)
      MOVE(
       TEMP t0,
       CONST 3)
      MOVE(
       TEMP t0,
       CONST 2)
      MOVE(
       TEMP t0,
       CONST 1)
    2. SEQ(SEQ(SEQ(MOVE(TEMP(t0),CONST(4)),MOVE(TEMP(t0),CONST(3))),MOVE(TEMP(t0), CONST(2))),MOVE(TEMP(t0),CONST(1))) Þ
       
      MOVE(
       TEMP t0,
       CONST 4)
      MOVE(
       TEMP t0,
       CONST 3)
      MOVE(
       TEMP t0,
       CONST 2)
      MOVE(
       TEMP t0,
       CONST 1)
  2.  Give the linearization, basic blocks and trace of:
    1. MOVE(TEMP t0, ESEQ(MOVE(TEMP t0,CONST 4),CONST 1)) Þ
       
      ____Linearization_____
      MOVE(
       TEMP t0,
       CONST 4)
      MOVE(
       TEMP t0,
       CONST 1)
      ______Basic Blocks____
      LABEL L1
       MOVE(
        TEMP t0,
        CONST 4)
      MOVE(
        TEMP t0,
        CONST 1)
      JUMP(NAME L0)
      ______Trace_________
      LABEL L1
       MOVE(
        TEMP t0,
        CONST 4)
       MOVE(
        TEMP t0,
        CONST 1)
      JUMP(NAME L0)
      LABEL L0
    2. SEQ(SEQ(JUMP(b2),MOVE( TEMP(t0),BINOP(BINOP.PLUS, CONST(1), ESEQ( MOVE(TEMP(t2), CONST(2)), TEMP(t1))))),LABEL(b1)) Þ
      ____Linearization____
        JUMP(NAME b2)
        MOVE(
         TEMP t2,
         CONST 2)
        MOVE(
         TEMP t0,
         BINOP(PLUS,
            CONST 1,
           TEMP t1))
      LABEL b1
      ______Basic Blocks___
      LABEL L1
        JUMP(NAME b2)
      LABEL L2
        MOVE(
         TEMP t2,
         CONST 2)
        MOVE(
         TEMP t0,
         BINOP(PLUS,
           CONST 1,
           TEMP t1))
        JUMP(NAME b1)
      LABEL b1
        JUMP(NAME L0)
      ______Trace_________
      LABEL L1
        JUMP(NAME b2)
      LABEL L2
        MOVE(
          TEMP t2,
          CONST 2)
        MOVE(
          TEMP t0,
          BINOP(PLUS,
           CONST 1,
           TEMP t1))
      LABEL b1
        JUMP(NAME L0)
      LABEL L0


     

  3.  Give the right-hand side for the incomplete rewriting rules to eliminate ESEQ's.
    1. MOVE(TEMP t, ESEQ(s,e)) Þ SEQ(s, MOVE(TEMP t,e))
    2. MOVE(MEM(e1),ESEQ(S,e2)) Þ SEQ(MOVE(TEMP t, e1), SEQ( S, MOVE(MEM(TEMP t), e2)))
    3. EXP(ESEQ(s,e)) Þ SEQ(s, EXP(e))
    4.  EXP(CALL(e1, [e2, ESEQ(S,e3), e4])) Þ SEQ(MOVE(TEMP t, e2), SEQ(s, EXP( CALL( e1, [TEMP t, e3, e4] ))))