Homework: Statement and Recursion I

This homework is necessary preparation for the lab. You can hand-draw the abstract syntax trees, but make sure you type your code for countOfPrimitiveCalls and you bring the file to the lab so that you will not have to waste time entering your code during the lab.

1. Given the following BL statements, draw the corresponding abstract syntax trees as defined by the mathematical model of StatementKernel. See Slides 5-12 in Abstract Syntax Trees for some examples.

   1. IF next-is-empty THEN
          move
      ELSE
          IF next-is-wall THEN
              turnright
              turnright
              move
          END IF
      END IF

   2. WHILE true DO
          turnright
          IF next-is-enemy THEN
              TurnAround
          ELSE
              skip
          END IF
          turnleft
      END WHILE

   3. WHILE next-is-enemy DO
          infect
          TurnAround
          move
          turnright
      END WHILE

   4. IF next-is-friend THEN
          turnright
          turnright
          WHILE true DO
              infect
          END WHILE
      END IF

   5. IF next-is-not-empty THEN
          turnleft
          turnleft
      ELSE
          WHILE next-is-empty DO
              move
          END WHILE
          IF next-is-enemy THEN
              infect
          END IF
          skip
      END IF

2. Using recursion, complete the body of the following static method. Note the use of a Java switch statement. See Slides 44-49 in Statement for the syntax, purpose, and behavior of this construct.

       /**
        * Reports the number of calls to primitive instructions (move, turnleft,
        * turnright, infect, skip) in a given {@code Statement}.
        * 
        * @param s
        *            the {@code Statement}
        * @return the number of calls to primitive instructions in {@code s}
        * @ensures <pre>
        * countOfPrimitiveCalls =
        *  [number of calls to primitive instructions in s]
        * </pre>
        */
       public static int countOfPrimitiveCalls(Statement s) {
           int count = 0;
           switch (s.kind()) {
               case BLOCK: {
                   /*
                    * Add up the number of calls to primitive instructions
                    * in each nested statement in the BLOCK.
                    */
   
                   // TODO - fill in case
   
                   break;
               }
               case IF: {
                   /*
                    * Find the number of calls to primitive instructions in
                    * the body of the IF.
                    */
   
                   // TODO - fill in case
   
                   break;
               }
               case IF_ELSE: {
                   /*
                    * Add up the number of calls to primitive instructions in
                    * the "then" and "else" bodies of the IF_ELSE.
                    */
   
                   // TODO - fill in case
   
                   break;
               }
               case WHILE: {
                   /*
                    * Find the number of calls to primitive instructions in
                    * the body of the WHILE.
                    */
   
                   // TODO - fill in case
   
                   break;
               }
               case CALL: {
                   /*
                    * This is a leaf: the count can only be 1 or 0. Determine
                    * whether this is a call to a primitive instruction or not.
                    */
   
                   // TODO - fill in case
   
                   break;
               }
               default: {
                   // this will never happen...can you explain why?
                   break;
               }
           }
           return count;
       }