Code Generator for CPP

Implementing Programming Languages, Assignment 4
Aarne Ranta (aarne (at) chalmers.se)

Summary

The objective of this assignment is to write an code generator from a fragment of the C++ programming language to JVM, Java Virtual Machine. The code generator should produce Java class files, which can be run in the Java bytecode interpreter so that they correctly perform all their input and output actions.

Before the work can be submitted, the program has to pass some tests, which are given on the book web page via links later in this document.

The recommended implementation is via a BNF grammar processed by the BNF Converter (BNFC) tool. The syntax tree created by the parser is first type checked by using the type checker created in Assignment 2. The code generator should then make another pass of the type-checked code.

The type checker is moreover recommended to annotate the abstract syntax trees with types, needed in instruction selection.

The approximate size of the grammar is 50 rules, and the code generator should be 100-300 lines, depending on the programming language used.

All BNFC supported languages can be used, but guidance is guaranteed only for Haskell and Java.

The code generator is partially characterized by compilation schemes in Chapter 6 of the book. More instructions are given in Appendix B. These explanations follow Jasmin assembler; the code generator may emit Jasmin assembly code into text files, which are then processed further by Jasmin to create class files.

Method

The recommended procedure is two passes:

  1. build a symbol table that for every function gives its type in a form usable for JVM code genetion;
  2. compile the program by generating a class file containing every source code function as a method.

You can copy your CPP.cf grammar and the TypeChecker module from Assignment 2 to the same directory.

Language specification

The language is the same as in Assignment 2, and you can use the grammar file CPP.cf. Also its type system is the same.

There are six built-in functions:

    void   printInt(int x)        // print an integer and a newline in standard output
    void   printDouble(double x)  // print a double and a newline in standard output
    void   printString(string x)  // print a string and a newline in standard output
    int    readInt()              // read an integer from standard input
    double readDouble()           // read a double from standard input
    string readString()           // read a string from standard input

These functions can be defined in a separate runtime class, which can be obtained e.g. from Java source. The runtime class should also contain the function

    string plusString(string x, string y) // concatenate strings x and y

used for compiling string addition (x + y).

Class structure

Boilerplate code, see Chapter 6.

Functions

Methods in the class, main special, see Chapter 6.

Statements and expressions

The semantics is the same as in Assignment 3. In other words, running the generated classes in java produces the same behaviour as running the source code in the icpp interpreter.

Solution format

Input and output

The code generator must be a program called ccpp, which is executed by the command

    ccpp <SourceFile>

and produces a class file. It may do this by first generating Jasmin assembly code and then calling Jasmin on this code.

The output at failure is a code generator error, or a TYPE ERROR as in Assignment 2, or a SYNTAX ERROR as in Assignment 1.

The input can be read not only from user typing on the terminal, but also from standard input redirected from a file or by echo. For instance,

    ./java fibonacci.class <test-input
    echo 20 | ./cppi fibonacci.cc

Example of success

Source file

  // file good.cc
  
  int main () 
  {
    int i = readInt() ; //5
  
    printInt(i) ;   //5
    printInt(i++) ; //5
    printInt(i) ;   //6
    printInt(++i) ; //7
    printInt(i) ;   //7
  
  }

Running the compiler

    % ccpp good.cc
    # produces good.class
  
    % echo 3 | java good.class
    3
    3
    4
    5
    5  

Compiling the code generator

The interpreter is submitted as a source file package that can be compiled by typing make.

Test programs

Run the test suite of Assignment 3 before submitting the assignment.

Success criteria

Your program must pass the test suite The test suite contains only correct programs; the assumption is that the type checker has rejected rejected the incorrect programs.

The solution must be written in an easily readable and maintainable way.