Homework: Program Code Generator

In this homework you will complete the code generation phase of the BL compiler by writing and testing the Program generatedCode secondary method.

The contracts for generatedCode and generateCodeForStatement are informal and vague. The details of the code to generate for each kind of statement are provided in the Code Generation slides (39-47, in particular). The code generated by your implementation must match the code-generation patterns described in the slides.

1. First, assume you are given an implementation for the following static method.

   /**
    * Converts {@code Condition} into corresponding conditional jump
    * instruction byte code.
    * 
    * @param c
    *            the {@code Condition} to be converted
    * @return the conditional jump instruction byte code corresponding to {@code c}
    * @ensures <pre>
    * conditionalJump =
    *  [conditional jump instruction byte code corresponding to c]
    * </pre>
    */
   private static Instruction conditionalJump(Condition c) {...}
   

   Using recursion and the conditionalJump method above, complete the body of the generateCodeForStatement static method below. Use the code for the case IF as a guide for the other cases.

   /**
    * Generates the sequence of virtual machine instructions ("byte codes")
    * corresponding to {@code s} and appends it at the end of {@code cp}.
    * 
    * @param s
    *            the {@code Statement} for which to generate code
    * @param context
    *            the {@code Context} in which to find user defined instructions
    * @param cp
    *            the {@code Sequence} containing the generated code
    * @updates cp
    * @ensures <pre>
    * if [all instructions called in s are either primitive or
    *     defined in context]  and
    *    [context does not include any calling cycles, i.e., recursion] then
    *  cp = #cp * [sequence of virtual machine "byte codes" corresponding to s]
    * else
    *  [reports an appropriate error message to the console and terminates client]
    * </pre>
    */
   private static void generateCodeForStatement(Statement s,
           Map<String, Statement> context, Sequence<Integer> cp) {
   
       final int dummy = 0;
   
       switch (s.kind()) {
           case BLOCK: {
   
               // TODO - fill in case
   
               break;
           }
           case IF: {
               Statement b = s.newInstance();
               Condition c = s.disassembleIf(b);
               cp.add(cp.length(), conditionalJump(c).byteCode());
               int jump = cp.length();
               cp.add(cp.length(), dummy);
               generateCodeForStatement(b, context, cp);
               cp.replaceEntry(jump, cp.length());
               s.assembleIf(c, b);
               break;
           }
           case IF_ELSE: {
   
               // TODO - fill in case
   
               break;
           }
           case WHILE: {
   
               // TODO - fill in case
   
               break;
           }
           case CALL: {
   
               // TODO - fill in case
   
               break;
           }
           default: {
               // nothing to do here: this will never happen...
               break;
           }
       }
   }
   

   Here are a couple of things to keep in mind:

   • The code generator is responsible for catching the two possible remaining syntax errors, which are not checked by the parser, namely, undefined instructions and direct and/or indirect use of recursion. To check for these errors use the Reporter.assertElseFatalError(boolean, String) utility method you are using in the parser project.
   • When making a (recursive) call to generateCodeForStatement, be careful to follow best practice with aliases. In particular, if the reference for a Statement block is an alias provided by a Map context, perhaps by use of a call to context's value method, then it would be wrong to pass both block and context to the same method. You can avoid doing so by obtaining block using context's remove method instead. Of course, context's value will need to be restored by later adding this name-statement pair back to it. You should then ponder the happy accident that being thus careful about aliases has made it easier for you to catch the syntax errors discussed in the immediately preceding item.

2. Now complete the body of the generatedCode instance method for the Program component. To generate code for a given Program (this) you need to generate code for the body of the program and append a HALT instruction at the end of that. this must be restored.

   /**
    * Generates and returns the sequence of virtual machine instructions
    * ("byte codes") corresponding to {@code this}.
    * 
    * @return the compiled program
    * @ensures <pre>
    * if [all instructions called in this are either primitive or
    *     defined in this.context]  and
    *    [this does not include any calling cycles, i.e., recursion] then
    *  generatedCode =
    *   [the sequence of virtual machine "byte codes" corresponding to this]
    * else
    *  [reports an appropriate error message to the console and terminates client]
    * </pre>
    */
   public Sequence<Integer> generatedCode();
   

Additional Activity (Recommended!)

Since testing the code generator is usually a lab activity, you can test your implementation of the code generator by following these steps.

1. To get started, in Eclipse, import the project ProgramCodeGenerator from the ProgramCodeGenerator.zip file available at this link.
2. Carefully look through the file Program1GeneratedCode1.java, which is an extension for Program1 that overrides the ProgramSecondary implementation of the generatedCode method, and make sure that you familiarize yourself with the methods provided. Note that it includes a main method that can be used to test your implementation and to display the code generated by generatedCode.
3. In Program1GeneratedCode1.java, complete the bodies of the generateCodeForStatement static method and the generatedCode instance method by pasting the code you wrote for the homework.
4. You can test your code generator implementation in a couple different ways. First use JUnit. Open the file Program1GeneratedCode1Test.java in the test folder and review the test cases provided to see how they are set up and how they attempt to test your implementation of the code generator. Run the JUnit test fixture and carefully review any test cases that fail. If that is not enough information to help you find the bug(s), you can also run the main program in Program1GeneratedCode1 and display the code generated by your implementation (but only for inputs that do not have any errors, including those that the code generator is supposed to catch). You can use the TestProgram1.bl file in the data folder in your project as test input. The main program generates two output files (both in the data folder): expected-output.txt that contains the correct output for the given input and actual-output.txt that is the output generated by your implementation. Use Eclipse's file compare feature you learned about in the previous labs to compare the two outputs. If your code does not work, you should create smaller test inputs that try to expose the bug(s) and make it easier to identify them. Fix all the bugs and make sure your code generator passes all the test cases.