Compilerbau Projekt (Entwicklung konkreter Anwendungen nach ausgewählten Prinzipien des Software Engineering)

Overview

Results from last year

This video showcases the games from last year’s students during this project. Every student wrote the game in their own programming language and compiled it for the GameBoy platform. The video was recorded on an emulator, but the games were also playable on a real GameBoy.

Introduction

In this project you will define your own syntax for a simple programming language, develop a parser for it, implement several compiler optimisations, and a back-end for LLVM and Z80-(like)-Assembly.

The project consists of three phases:

Phase 1: Parsing

First you will define your own syntax and implement a parser with a parsing strategy and language of your choice. You can use Java and ANTLR, JavaScript and PEG.js, or Haskell and Parsec. You can also do this phase alone or in a group.

Your only constraint is that your parser has to produce a given textual intermediate representation (IR). This IR will be defined by us and we will provide an interpreter for it. Once your parser produces IR, you will be able to use the interpreter to interpret your programming language.

During Phase 1 you will have to add features to your programming language, for example, arrays, if-statements, loops, and function definitions. To prove that your parser works, you will implement unit tests using your parser and our interpreter. You will also have to give a presentation on your parsing strategy and your parser.

Phase 2: IR Optimisations

In this Phase, you will work in small groups or alone on optimisations for the IR. Since all Phase 1 parsers produce the same IR, you can keep using your own syntax while still profiting from the optimisations developed by other students. Your optimisation passes should read in the textual IR, apply a certain optimisation, and print out the new IR. That means, you can implement your optimisation pass in any programming language you like.

Some possible optimisations are: dead code elimination, inlining, loop unrolling, and constant folding.

During this phase you will also implement unit tests and benchmarks to show that your optimisations work. At the end of the phase you will have to present your optimisations and the results of your benchmarks.

Phase 3: Code Generation

Up to this point you will have used the interpreter to run your programs. In this Phase you will work on the back-end in groups. We plan to support two different back-ends: LLVM and Z80-(like)-Assembly (GameBoy Color or Sega Master System, using Emulicious). You will work on implementing register allocation and code selection for the back-ends.

At the end of this Phase every group will have to implement a small application, for example, Pong, PacMan, or Snake in their own programming language from Phase 1. To achieve this, you will have to adapt your parser and compiler from Phase 1 and 2 and add functionality to interoperate with the hardware. Furthermore, you will have to give a presentation about the part of the code generation that you implemented.

Prerequisites

  • Good knowledge of at least one programming language.
  • An interest in compilers and related algorithms.