Introduction

Your compiler should take two command line arguments, the first is the C-- code source file and the second is the name of the stack machine output file:

% ./mycc  foo.c--  foo.stk  

Once you successfully complete the basic C-- compiler, you can try adding additional features for extra credit points. Do not add additional features before your initial solution is complete and correct; an incomplete implementation of the required functionality plus an added feature will result in a lower grade than a complete implementation of the required functionality without any additional feature added.

Here are some additions you might want to consider (please talk to me about any additional ideas you have for extra features before attempting them):

• for loops
• floats
• strings
• function prototypes (allows two functions to call each other)
• pass by reference (passing int and char variables by reference) You must implement C style pass by reference, not C++ style. An example of C style pass by reference:

    int foo(int *x) {   // x declared as a pointer to int 
      *x = 6;           // dereference the pointer to modify the arg's value
      return (*x + 10); 
    }
    int main() {
      int x;
      write foo(&x);   // pass x by reference to foo
    }
  

• supporting assignment statements as expressions on the right-hand-side of statements. For example:

  	a = b = c = d;   // b, c, and d are both l-values and r-values
  
  	x = (y = 6) + 8;  // (y = 6) assigns 6 to l-value y, then use  
  			  // the r-value of y to add to 8
  

• Compile to MIPS assembly code and use the spim MIPS simular to run and test your MIPS assembly code. MIPS is Silcon Graphics processor architecture. It is a RISC processor (reduced instruction set) where instructions load, store, and get their operand values from machine registers. Information on how to use spim, is available in ~newhall/public/cs75/spim/ . In addition, a copy of the SPIM manual is in the overflow lab.

  If you choose this option, you should submit two versions of your solution, one that generates smach code, the other that generates MIPS assembly code (and don't attempt this until after you get your smach solution working).

• support for pointers and dynamic memory (requires changes to smach). If you choose this option, you should submit two versions of your solution, one that solves the basic solution, and one with your additional features including a copy of your modified smach (the source not the executable) with your solution.

Details/Getting Started

I recommend that you use some type of revision control software (CVS would be the best choice if you are working with a partner) to keep versions of your working compiler as you add functionality. Information about using CVS and RCS is available off the cs75 homepage.

You should create a test suite of C-- programs to test your compiler (when you write a new one, first try parsing it with your parser to make sure it is valid C--). Think carefully about programs you add to this suite to make sure they completely test all aspects of your code generator. As you add features to your compiler, re-test your compiler on your test suite to make sure you didn't break something that you previously had working.

How to add code generation

1. Define a codetable in global.h that can be used to store the stack machine code as you generate it. You do not want to write each instruction to the output file as you generate it because you will have some back patching to do. Instead, generate stack machine code to a codetable data structure and output the codetable to the target output file before your compiler exits.
2. Define a function called codegen, that writes lines of stack machine code to this table and use a variable to keep track of the current output line number.
3. Update main.c to open an output file, and after parsing and code generation, write the contents of the codetable to the output file.
4. Add fields to your symbol table data structure. Think about what type of attributes you need to keep for each type of symbol table entry.

   Now you are ready to actually generate some code.

   Basic Functionality: due as Part 3

5. Initially, ignore variables and function calls. Assume that all C-- code will simply be a main program that deals directly with numbers. So for now your first line of output code will always be: INC 0 3 and your last line will always be RTN 0 0.
6. In parser.c, add calls to codegen for all basic arithmetic operations and numbers. Test with programs such as:

   int main() {
     write 3+4*7; // should be 31
     writeln;
   }
   

7. Then add calls to codegen for all basic boolean operations. Remember to use the concept of back patching to implement || and && We need to branch to some line, but at the time we need to make the call to codegen we don't know which line. Save the current output line number, so that when you do know the branch target, you can go back and update it in the code table. Test with programs such as:

   int main() {
     write (4 == 5) || (5 < 6);  // should be 1 for true
     write (4 == 5) || (5 < 4);  // should be 0 for false
     write (4 == 5) && (5 < 6);  // should be 0 for false
     write (7 >= 7) && (8 <= 8); // should be 1 for true
     writeln;
   }
   

8. Once these are working correctly, add calls to codegen for if statements. Test with programs such as:

   int main() {
     if (!1)  // should output -1
       write 1;
     else
       write -1;
     writeln;
     if (1 == 1) // should output 1
       write 1;
     else
       write -1;
     writeln;
   }
   

9. Then add calls to codegen for while loops. Initially don't worry about break statements. Test with programs such as:

   int main() {
     while (1)  // this will create an infinite loop
       write 1;
   }
   int main() {
     write 1;
     writeln;
     while (0) { // this loop should never get executed
       write 2;
       writeln;
     }
     write 3;
     writeln;
   }
   

Part 4: Once this basic functionality is in place, then move on to the more complicated aspects of code generation.

• First, consider how you are going to deal with identifiers when they are encountered in the code. Currently the symbol table only keeps track of two things: the id's name (which is just a string) and the id's token value (e.g. ID). You need to add more information to the symbol table to distinguish between local variables vs global variables vs functions, and arrays vs non-arrays. For arrays, you may want to keep track of its size. For all types of ids you need to know where they are located. In the stack machine, the size of a char or an int variable is 1 (each require one unit of space on the stack).

  As your compiler finds parameters or local or temporary variable declarations inside a function or a block, it should add a new entry to the symbol table for these variables. When it finishes compiling a block or function, entries defined within the block or function should be removed. Your code must detect the error condition of duplicate definitions of a name within the same scope.

  You will likely need to add parameters to your parser functions to pass extra information necessary for code generation between the functions. In addition, you may discover that you need to re-write some of your grammar rules to better facilitate code generation.

  The stack machine's stack is implemented as an array. As you push a value on the stack, the top-of-stack value is a higher array index than the previous top-of-stack value. You will access most stack contents as offsets from BASEPTR. The locations of local variables will be a positive offset from the current stack frame baseptr. The location of parameters and the return value is at a negative offset from the current stack frame baseptr. The locations of global variables will be below main's stack frame. The locations of functions will be a line number in the code table. For example, if main calls function int blah() and blah calls int foo(int x, int y), then the stack will look like this after the call sequence instructions have executed:

                  -----------------------               PC: addr of a foo instr.
     frame 0      |    blah's PC value  | <---- TOP
                  |    blah's baseptr   |	  (foo's stack frame)
                  |    static link      | <---- BASEPTR 
                  -----------------------
     frame 1      |   param  y          |
                  |   param  x          |   (blah's stack frame)
                  |  foo's return value |
                  |   ...               |  
                  |   main's PC value   |
                  |   main's baseptr    |
                  |   static link       | <---- blah's baseptr value pts here
                  -----------------------
     frame 2      | blah's return value |
                  |   ...               |   (main's stack frame)
                  |    0                |
                  |    0                |
                  |    0                | <---- main's baseptr value pts here
                  =======================
      level -1    |    global vars      |
                  -----------------------         
  
  NOTE: when function foo returns, blah's frame becomes frame 0, and 
        main's frame is frame 1; frame 0 is always the top-most stack frame 
  

  To get and store the values of global variables do the following using absolute addressing:

  PSH -1 posoffset
  STO -1 posoffset
  

  And to get and store the values of local variables in the current stack frame do the following using relative addressing:

  PSH 0 posoffset
  STO 0 posoffset
  

• Dealing with arrays is actually fairly simple. Rather than using PSH and STO, you will use PSX and STX, which are indexed versions of push and store.

  Whenever you are uncertain of the effects of a stack operation, go to the smach.c code and find out what it does.

• In C, break statements are only allowed inside while loop, for loop, and switch statement blocks. Your compiler only should allow them inside while loop blocks.

• When we say "int x;" we want the compiler to reserve some static memory for x and save its location in the symbol table. When we say "x = 1;" we want the value 1 to be stored in the memory location associated with x. And when we use "x" in "z = x + y" we want the value of x to be added to the value of y.

  Your compiler needs to be able to determine when to use an lvalue (the storage location) as opposed to an rvalue (the actual value). Obviously, it depends on whether or not we have an assignment statement.

  One problem you need to solve is that in the LL(1) grammar, by the time you find the assignment token you have lost the information about the preceding identifier. One way to solve this problem is to pass to your expression parsing functions a value that will be updated by the part that parses an identifier and checked by the function that handles assignment statements. It is important that this information be stored locally, because the following kind of expression is allowed in C--:

  a = b = c = 0;
  

  This is very tricky to handle properly, because here, each variable is being used as BOTH and lvalue AND and rvalue. Don't worry if you aren't able to implement this kind of assignment expression for the final version. However, if you don't handle it, your compiler should flag it as an error.

  You should be able to detect invalid lvalues in assignment statements and correctly make a distinction between identifiers used as lvalues or rvalues. You must handle expressions like:

          x = x + z + 6;
  	array[i] = array[j] + foo(array, x, (y+7));
          6 + x = 10;   // your compiler should detect this error: invalid lvalue
  

  In addition, any time a name is used in an expression, you must ensure that it corresponds to a function or identifier that has been declared prior to its use.

• In order to make it easy to reserve static storage for global variables, use the "GLO" stack machine instruction which reserves space below main's stack frame for global data.

  Eventually the code you generate should begin as follows:

  1 GLO 0 num     ; where num is the amount of global memory needed at stack base
  2 BRU 0 line#   ; where line# is the line number of the start of main
  
  ...
  
  line# INC 0 3   ; the beginning of main
  ...
  

What to Hand in

1. Submit the following using cs75handin:
   A tar file containing:
   1. All the source header files and makefile I need to build and run your compiler.
   2. A README file with:
      1. Your name and your partner's name
      2. The number of late days you have used on this assignment
      3. The total number of late days you have used so far
   3. A sample of your parser's output on a good (and short) test C-- program that you devised. Annotate the output listing the parts (statement(s) of the C-- program) that are being parsed at different points in the output. Look at my unix help pages about using script to capture terminal I/O to a file.
   4. A copy of the test C-- program for which you submitted sample output.

2. In addition you should submit a project report (may be submitted on-line as part of your tar file or as a hardcopy in class). If you submit it on-line it must be in either postscript, pdf, or ascii (with line length of < 80 chars) format.

   In 1 to 2 pages give an overview of the design of your compiler based on the approach to compiler construction we've adopted in this course. You should describe any special features of your compiler. If there are any aspects that have not been fully implemented or are buggy, you should discuss them here. And, include a copy of your LL(1) grammar.

3. After submitting your solution, you and your partner will sign up for a 20 minute demo where you will run your compiler for me and show me all the cool things it can do. In preparing for your demo think about coming up with some good test programs that you can use to demonstrate your compiler's features. This is a good time to show off places where you are generating efficient code for C-- constructs, and to show off any extra credit features you implemented.