The goal of this programming assignment is to implement the translation from php-- abstract syntax to intermediate representation in C-flat.

What you need to do

Read this assignment in its entirety.

Download the starter project, try compiling and running it. As it stands, a fair amount of the translator has been implemented for you: functions (definitions, calls, and returns), echo statements, string literals, identifier expressions, string concatenation, and comparison operators. For instance you should be able to compile the following code:

  <?php

  function doubleString(/*:string:*/ $s) /*:string:*/ {
    return $s . $s;
  }

  echo doubleString("compilers is twice as much fun");

  ?>

and it should produce the following C-flat intermediate code:

  #include "cflat_stdlib.c"

  int t2 = (int) "compilers is twice as much fun";
  int t3, t4;
  int fun_doubleString(int t0) {
  	int t1;
  	t1 = cflat_stdlib__strcat(t0, t0);
  	return t1;

  	return 0;
  }
  int main() {
  	t3 = fun_doubleString(t2);
  	t4 = cflat_stdlib__echo(t3);

  	return 0;
  }

You should be able to take the result of the output and compile it using a standard C compiler provided that the two supplied C files cflat_stdlib.c and cflat_stdlib.h are in the same folder. (The two C files are also included as part of the project stub.)

Don't worry. There is still plenty to do. (Append statements are also implemented for you, but you cannot test them until you make arrays work.)

Begin by looking over the supplied code, particularly the data structures defined in the ir package, the methods and environment structure defined (or at least sketched out) in the ast_to_ir package, and the printing methods in the cflat package. In particular, get familiar with the stub classes TranslateStatement and TranslateExpression and the helper routines in the TranslateUtil class.

Here is my recommendation for the order in which to proceed:

1. Implement translation of Boolean and integer literals, if statements and compound statements. You should be able to test it with code like:

     if (2 < 3) {
        echo "true";
     }
     else {
        echo "false";
     } 
   

2. Implement translation of arithmetic operations, short-circuit conjunction (&&) and disjunction (||), simple assignment and while statements. At this point you should be able to successfully compile the factorial example.

3. Implement translation of break and continue statements. Make sure to identify errors when either one of these control-flow statements is attempted outside the body of a loop. You can test for correctly working breaks and continues with the nested breaks example.

4. Implement everything else that does not have to do with arrays.

5. Implement translation of array expressions, the count operator, subscript expressions, and foreach loops. Make sure that assignments into arrays work properly and still generate valid C-flat code. At this point you should be able to successfully compile the selection-sort example.

Test your project thoroughly!

Notes

• Arrays are stored as triples - three consecutive words in memory. The first word is the address of where the elements of the array are stored; the second word is how much space has currently been allocated for the array; the third word is the current size of the array. (This indirect method of storing arrays will make their access slightly less efficient than in a more direct model and will make code generation a little more complicated but the reward is that the append operation can be significantly more streamlined.)

• Array elements are stored in a word-aligned fashion. You can get the word size from the environment and then multiply it by the source-level index to generate the proper intermediate (and machine-level) address.

• At this stage of the compilation process, where C-flat is used as the intermediate representation, strings are encoded as in C.

• Technically, we need type information around at this stage in order to distinguish between equality tests (== and !=) - that is, whether they refer to the scalar versions (on ints and bools) or the string version which requires a library call.

  For now, this feature is not implemented and, thus, you will observe a warning message:

    Warning: types ignored for equality check.
  

  every time your translator tries to compile an equality test.

  I was tempted to just remove built-in string equality from php--. After all, it's not a core feature of other programming languages (including C, C++, Java) and it would simplify things. However, there are many cases in compilers where type information _is_ needed at this stage; and it only requires a fairly simple change in the type-checking process: we can record an additional table mapping uids to types and have the type checker return that structure rather than void. Each ast expression will be adorned - automatically at the point of construction - with its own unique id. This allows us to create maps from arbitrary expressions. (But this additional expression-to-type table is not implemented at this time.)

Binaries

You will almost certainly find it useful to experiment with the binaries for the solution.

Submission