cs152 Project Phase 3: Code Generation

All projects can be turned in up to 1 week late. Each day the project is late, 3% will be deducted per day for up to 21%. After a week, projects will not be accepted.

Overview

In the previous phases of the class project, you used the flex and bison tools to create a lexical analyzer and a parser for your custom programming language. In this phase of the class project, you will take a syntactically-correct program (a program that can be parsed without any syntax errors), verify that it has no semantic errors, and then generate its corresponding intermediate code. The generated code can then be executed (using a tool we will provide) to run the compiled MINI-L program.

[The example MINI-L source-code language is described in detail here (this is the same as for the prior project phases).]

You need to do code generation for the following statements:

• Function Related Statements
• Variable Declaration Statements
• Copy Statements
• Array Access Statements
• Input/Output Statements
• Arithmetic Operator Statements

You should perform one-pass code generation and directly output the generated code. There is no need to build/traverse a syntax tree. However, you will need to maintain a symbol table during code generation.

The intermediate code you will generate is called "MIL" code. We will provide you with an interpreter called mil_run that can be used to execute the MIL code.

[The MIL intermediate code representation is described in detail here.]
[Here are some slides describing the MIL intermediate code along with advice on code generation here.]
[Download the mil_run MIL interpreter here.]

The output of your code generator will be a file containing the generated MIL code. If any semantic errors are encountered by the code generator, then appropriate error messages should be emitted and no other output should be produced.

Here is a correct example implementation of Phase 3 based on the MINI-L example language: min_c.

[The required output format for your code generator is described here.]

The mil_run MIL interpreter

We are providing an interpreter for MIL intermediate code (mil_run), which can be used to execute the MIL code generated by your code generator. The mil_run interpreter requires an input file to be specified that contains the MIL code that should be executed. For example, if you have MIL code contained in a file called mil_code.mil, then you can execute the MIL code with the following command:

mil_run mil_code.mil

If the MIL code itself requires some input data, this input data can be written to a file and then redirected to the executing MIL code. For example, if the input values are written to a text file called input.txt, then it can be passed to the executing MIL program as follows:

mil_run mil_code.mil < input.txt

The mil_run interpreter will generate a file called milRun.stat that contains some statistics about the MIL code that was just executed. You may ignore this file.

mil_run makes the following assumptions.

1. Each line in the MIL file contains at most one MIL instruction
2. Each line is at most 254 characters long
3. All variables are defined before they are used

You must ensure that your generated MIL code meets the above three requirements.

mil_run is a linux executable and can be run on bolt.

Detailed Requirements

1. You will need to modify your bison specification file from the previous phase of the class project so that it no longer outputs the list of productions taken during parsing.
2. Implement the code generator. This will most likely require some enhancements to your bison specification file. You may also want to create additional implementation files. The requirements for your implementation are as follows.
   1. You do not need to do anything special to handle lexical or syntax errors in this phase of the class project. If any lexical or syntax errors are encountered, your compiler should emit appropriate error message(s) and terminate the same way as was done in previous phases.
   2. You need to check for semantic errors in the inputted program. During code generation, if any semantic errors are encountered, then appropriate error messages should be emitted and no other output should be produced (i.e., no code should be generated).
   3. If no semantic errors are encountered, then the appropriate MIL intermediate code should be generated and written to stdout.
   4. When generating the intermediate code, be careful that you do not accidentally create a temporary variable with the same name as one of the variables specified in the original program.
3. Compile everything together into a single executable. The particular commands needed to compile your code generator will depend on the implementation files you create.
4. Use the mil_run MIL interpreter to test your implementation. For each programming language example program, compile it down to MIL code using your implementation. Then invoke the MIL code using mil_run to verify that the compiled program behaves as expected.
   

A Note about Runtime Errors

There are some errors that cannot always be captured at compile-time and may only happen at run-time. These errors include those such as array index out-of-bounds errors, and division by zero. Your implementation need not handle these errors. You may assume that when we grade your programs, we will not use any example programs that would lead to run-time errors. Note also that the mil_run MIL interpreter we are providing may have unexpected behavior if you try to run it on a program that can lead to run-time problems (such as an out-of-bounds array access). Thus, when you are testing your implementation, try to make sure your example programs will not cause any run-time errors.

Example Code

Example Usage

Suppose your code generator is in the executable named my_compiler. Then for the MINI-L program basic.min (which is syntactically and semantically correct), your code generator should be invoked as follows:

cat basic.min | my_compiler

The file basic.mil should then be created and should contain the generated MIL code (it is okay if your generated code looks slightly different, but it should have the same behavior when executed). Next, you can test your generated code using the mil_run MIL interpreter to ensure that it behaves as expected. Suppose we want to run the compiled array program:

When the compiled array program is executed, then the following would be the output:

Here is the expected MIL output for add.min: add.mil

When the compiled add program is executed, then the following would be the output:

Here is the expected MIL output for math.min: math.mil

When the compiled math program is executed, then the following would be the output:

Here is the expected MIL output for array.min: array.mil

When the compiled array program is executed, then the following would be the output:

Here is the expected MIL output for function.min: function.mil

When the compiled function program is executed, then the following would be the output: