Compilerbau (Master Projekt)
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
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.
- Good knowledge of at least one programming language.
- An interest in compilers and related algorithms.
Please write an E-Mail to Stefan Kögel, stating that you are interested in this project. You will be informed about the date and place of the first meeting at the beginning of WiSe 2016/17.