Supervisor

Suitable for

Abstract

In the Compilers course, we selected instructions by a greedy pattern-matching algorithm that works on operator trees, and expressed the algorithm by means of a family of recursive functions. For CISC machines especially, this greedy algorithm is inadequate, and it becomes necessary to use an algorithm based on dynamic programming to find an optimal tiling of the operator tree with instructions.

Code generator generators exist that are capable of translating a machine grammar annotated with costs and instruction templates into efficient pattern matching code in C, in the form of a Bottom Up Rewriting System. The aim in this project is to implement a similar tool based on OCaml, so that the code generation phase of our compilers can be expressed directly as a tree grammar.