1981 - 1984. BSc (hons) in Computer Science, University of Melbourne, Australia.
|Project:||Code Generator Generators|
|Skills:||Compiler construction, table driven code generation, optimisation|
I developed a code generator generator based on the Graham-Glanville techniques of table driven code generation. Table driven code generation is interesting because it is not only extremely fast, it also yields only provably correct interpretations of the intermediate language.
The code-generator generator worked by taking a modified LALR description of the intermediate language and generating a language parser similar to yacc to parse the language generated by the front end. As actions in the language description were executed, assembler was expected to be generated. Weights and conditions can be assigned to different rules to guide lowest cost code generation where multiple derivations occur. This also means that the parser can become stuck trying to reduce a ruleset when a condition is tested before the action is called. To handle this situation I implemented a part of Earley's algorithm to derive alternative derivations which could be used to return the parse state to a point where processing could continue.
The results of implementing a subset of the Perkin-Elmer 32/40 instruction set by parsing the output of the portable C compiler's front-end were promising. The code generation was extraordinarily fast compared to the somewhat ad-hoc pattern matching code generation techniques used by the PCC back-end: to the order of one hundred times faster. The small size of the implementation and the absense of many significant components in code generator, in particular a real register allocation scheme, makes this result less conclusive than it might be. The strict left-to-right translation of the intermediate language also meant that the code generation would routinely miss obvious optimisations.
Further work would have involved seeing whether Fraser's algorithms for peephole optimisation might have been able to clean up the inefficiencies introduced by the limitations of Graham-Glanville's techniques.
Higher School Certificate at The Geelong College in 1980.