THE AUTOMATIC GENERATION OF REALISTIC COMPILERS FROM HIGH-LEVEL SEMANTIC DESCRIPTIONS

Several recently developed semantics systems automatically generate compilers from denotational descriptions of programming languages. Unfortunately, the object programs produced by the generated compilers run several orders of magnitude slower than those produced by hand-written compilers. We believe that this is due in large part to fundamental problems with denotational semantics as a language for specifying compilers. These problems effectively preclude any possibility for efficient implementation, and furthermore lead to specifications that are unnecessarily hard to comprehend and debug.

In order to overcome these problems, we have developed a new style of semantic definition called high-level semantics. Unlike the traditional denotational approach, our high-level technique is suitable for both defining the functional meaning of programming languages as well as describing realistic complier implementations.

The feasibility of our ideas is demonstrated by a system called MESS which derives realistic compilers from high-level semantic descriptions. MESS has been used to generate a compiler for a language with recursive procedures, reference and value parameters, multidimensional flexible array parameters, and the usual Pascal-like control structures. The object programs produced by the compiler compare favorably with those produced by commercially available, hand-written compilers in both size and speed.