Step 4: Semantic Routines (I) - Due Wednesday, Oct. 11th, 11:59pm


Note: the step for [expression,I/O] and [control structures] is split into two steps, step4 and step5. So, the webpage for step4 and step5 are almost the same. Basically, you can refer to IRDescription.pdf for instructions on both steps.

In the so-called parser-driven compilers, the compilers call code-generation routines every time a grammar rule is recognized by the parser. This step, as well as "step 5 and 6", deals with the code generation routines, also called semantic routines, for your language. This step assumes that you have fixed all the problems with the parser developed in "step 2" as well as the symbol table developed in "step 3". You may find useful to get familiar with the material listed in the "Readings" section of the project webpage. The diagram below shows the stage of the compiler construction after the completion of this step:

semantic routines

The Task: The compiler's semantic routines for expressions and I/O operations

Your goal in this step is to generate executable code for a simple program written using your language (a program that only has the main function, which calls no other functions). For simplicity reasons, the code that your compiler will generate is meant to be executed on the Tiny simulator.

In order to achieve this goal you have to add the semantic routines that will be executed by the parser every time a grammar rule is recognized. The rules you will have to deal with are the ones related to statements (assignment, read/write), expressions (please, refer to the "step 4" described in the course syllabus). The implementation strategy we suggest is:

(1) Generate an intermediate representation (IR):

The intermediate representation is the representation of the program in a language internal to the compiler. Many code optimization techniques operate on the intermediate code. However, for now, the IR will serve only as an intermediate step for the generation of the final tiny code. The intermediate representation is implemented as a linked-list that has every intermediate instruction as a node. For branch instructions the node also has a pointer to the target node. The intermediate instructions are machine independent. We suggest you to follow the IR description provided here.

For this step you can assume that all variables are defined globally. There will not be any additional variables defined in main().

(2) The tiny simulator

The tiny simulator is meant to work as a simplified version of a real machine. It works executing a stream of assembly instructions. A description of the tiny simulator is here. The source code for the tiny simulator is here. You can compile the source code using the following command:

g++ -o tiny tinyNew.C

(3) Code generation

You implementation of item 1 will generate an internal representation of the micro program and store that representation in memory using a linked-list. In the code generation process you have to implement a procedure that will traverse the linked-list and translate the IR instructions to tiny instructions. Note that your IR code consists in three operand instructions as opposed to the two operand instructions of the tiny simulator. Therefore, some instructions in the IR representation will be translated in more than one tiny instruction. Please read carefully the tiny manual to understand how the tiny instructions are defined.

For this step you don't need to care about register allocation or semantic records, therefore the symbols of the final tiny code can be the same ones used in the intermediate representation. You will use a version of the tiny simulator that allows your code to use up to 1000 registers. That would be enough to map all each temporary result to one different register and there will be still registers available for intermediate operations that may need extra registers.

Input/Output format requirements

Execution of the compiler would output BOTH the IRcode and tiny code and combine them together on the standard output. The output forms an executable file on the tiny simulator. It should start with the IRcode, with each line commented out by prepending a ';' to its front. Then the second half of the output should be the tiny code. Please take a look at the example outputs given below.

Grading: We will grade by running the outputed code (*.out) on the tiny simulator, and look at the computation results. You should also run your output on the simulator and verify that the computation results of the program are correct. Since the IR codes are commented out, they don't affect tiny machine execution. (Although we will look at them too.) We do not care about the specific instructions you generate, as long as the output (computation result) of your compiled program is correct.

(4) Testcases

Please note that these *.out files are only examples -- it is perfectly ok if your output is different from them. What really matters is the execution result of your code.

To know the execution results, you should run the output code on tiny simulator like this:

tiny step4_testcase3.out
tiny test_expr.out

and compare those execution results with the results obtained by running the output code generated by your step4 implementation for the provided testcases. Note that only the value of the result matters and not the number of instructions, cycles, and registers used.

(5) Questions about semantics

As you implement the semantic routines you may feel the need for clarification about particular subtleties in the semantics. You are encouraged to email the TA or the professor regarding this information. Also we will update this section from time to time to help answer the most common questions, so please check back often.

Submitting your project

First, make sure that your directory structure is correct and you are submitting only the required files. Then, follow the instructions about the turnin command and note that the step name for this step is step4 (use -p step4). Also, if you are working in a pair, submit from the same login (also called your group account) every time.