6/6

Previous Contents Fulltext First Last

Exercises 5: Code generation

Programming Languages 2010

This exercise can be seen as a complete programming project: build a compiler from a fragment of C++ to JVM. Unlike the labs, it is not obligatory for the course. Like all other exercises, it generates extra points for the exam, which means 2 points if you do all questions.

In addition, you will get the satisfaction of being able to generate .class files with your own compiler and run them by using the JVM interpreter java.

The grammar you deal with is the same as in labs 2 and 3. But the compiler only needs to work for a subset of lab 3:

Most questions request you to write compilation schemes. The answer can be given in pseudocode or in actual Haskell or Java or some other code. To run the compiler, a main function very similar to lab 3 is needed. The compiler code itself is very similar to the interpreter.

1. Write compilation schemes for

Apply these schemes to compile the expression

    printInt((1 + 3*5)/2)

2. Design and implement an environment that supports

Show how the environment changes when compiling the code

    int i ;
    int j ;
    if (i < j) i++ ; else j++ ;

You don't need to show the code yet - this belongs to the later questions.

3. Write compilation schemes for expressions and statements with integer variables:

Be careful to distinguish between pre- and postincrement!

4. Write compilation schemes for

You don't need to think about optimizations.

5. Put everything together and show the code generated from the two programs below. The easiest way to produce the code is certainly by running your compiler!

Once you have a program, called ex5, you can use it to generate a class file by running the script jass on it. Then you can execute this file with

    java Main

You need all files from the jvm directory to run jass (a header, a footer, and a runtime support class).

Here are the two test files. If you haven't written a compiler, you can answer this question by hand-written code.

  // fibonacci.cc
  int main () 
  {
    int low,hi,mx ;
    low = 1 ;
    hi  = low ;
    mx  = 500000 ;
    printInt(low) ;
    while (hi < mx) {
      printInt(hi) ;
      hi  = low + hi ;
      low = hi - low ;
      }
  }

  // lazy.cc
  int main ()
  {
    int i = 1 ;
    bool b = (++i > 2) && (++i > 0) ;
    printInt(i) ; // 2
    printInt(++i) ; // 3
    printInt(i++) ; // 3
    printInt(i) ; // 4
    b = (i > 5) || (++i > 0) ;
    printInt(i) ; // 5
  }