Midterm 1 Solutions


  1. A virtual method is slower than a non-virtual method because the determination of the jump address for the method must be deferred until runtime rather than being determined at compile time. At runtime a jump table must be consulted, resulting in an indirect jump to the proper location rather than the direct jump that can be made for a non-virtual method.

  2. Java's package mechanism requires the programmer to write far less code in order to allow a group of related classes to share access to one another's methods and instance variables while denying access to outside classes. In Java a class shares access by using a package statement to declare the class's package and an import statement to import the other classes in the package. In contrast, in C++ a group of related classes must first deny access to all classes, then selectively use the friends declaration to enumerate all the other classes with which they wish to share access.
  3. class InvalidInput extends Exception {
        String token;
        public String getToken () { return token; }
        public InvalidInput(String badInput) {
          token = badInput;
        }
      }
    
      int quotient(Scanner input) throws InvalidInput {
        int divisor, dividend;
        
        if (input.hasNextInt()) 
          divisor = input.nextInt();
        else
          throw new InvalidInput(input.next());
    
        if (input.hasNextInt()) 
          dividend = input.nextInt();
        else
          throw new InvalidInput(input.next());
    
        return divisor / dividend;
      }
    
  4.     try {
          System.out.printf("quotient = %d\n", p.quotient(input));
        }
        catch (InvalidInput ie) { 
          System.out.printf("Invalid input: %s must be an integer\n", ie.getToken());
        }
        catch (ArithmeticException e) { System.out.println(e); }
    

  5. The grammmar is LL(1) because there is no left recursion and because each production has a unique First set.

  6. E -> - E EE -> - E E
    E -> - number EE -> number
    E -> - number + E EE -> E -> + E E
    E -> - number + - E E EE -> E -> - E E
    E -> - number + - number E E E -> number
    E -> - number + - number number EE -> number
    E -> - number + - number number numberE -> number

  7.                           -------E---------
    		          |      |        |
                              -      E    ----E-----------------
    			         |    |       |            |
                                  number  +   ----E-------     E
    			                  |   |      |     |
    			                  -   E      E   number
    					      |      |
    				           number number
         
  8.      Set 1: E' -> E.
         Set 2: E -> number.
         Set 3: E -> - .E E | .number | .- E E | .+ E E
         Set 4: E -> + .E E | .number | .- E E | .+ E E
         
  9. InputStackAction
    -(id)$$1shift - and move to state 4
    (id)$$1-4shift ( and move to state 3
    id)$$1-4(3shift id and move to state 5
    )$$1-4(3id5reduce by E->id, pop 1 pair, shift E, and move to state 8
    )$$1-4(3E8shift ) and move to state 12
    $$1-4(3E8)12reduce by E->(E), pop 3 pairs, shift E, and move to state 9
    $$1-4E9reduce by E->-E, pop 2 pairs, shift E, and move to state 1
    $$1E2accept the string