Using dynamic programming to generate optimized code in a Graham-Glanville style code generator

Abstract

We have performed an investigation of using a dynamic programming to generate optimized code in a Graham-Glanville style code generator We use Earley's algorithm rather than an IR algorithm for parsing in the code generator Not only does the use of Earley's algorithm make the construction of the code generator very easy it allows the selection of optimal code by dynamic programming (using a modification of the technique developed by Lvon) We compare two implementations of this technique to conventional hand-coded code generators using a subset of BASIC as the source language Further we discuss the use of this technique in an experimental C compiler.