Automatic generation of efficient compilers using abstract algebraic semantics.

Abstract

A compiler generator is described which produces compilers competitive with handwritten ones in compile and execution time. In both time measures its compilers are as fast as those produced by other semantics-directed systems and for most systems show one to three orders of magnitude improvement in at least one time measure. The generator described here differs from most in that it employs an algebraic semantic system rather than one based on the $\lambda$-calculus. Thus, it uses a formal semantic system which is easily comprehended and naturally applicable to language processing. A semantic algebra is presented which has very general applicability yet contains a small set of basic notions. Fundamental constructs of modern programming languages are analyzed and it is shown that apparently arbitrary choices in language syntax significantly affect the complexity of the semantic algebra for one-pass compilation. Previous compiler generators are inefficient partly because they are unable to translate source into object language directly. They construct an intermediate representation of semantic terms, thus separating parsing from code-generation. This work uses the semantic language to synthesize parsing and code-generation, as is done in a typical handwritten one-pass compiler, so that after construction of the compiler, no further reference is made to semantic terms. To accomplish this, a common problem of LR parsing is resolved: to identify positions in an LR grammar at which null nonterminals may be inserted such that the resulting grammar is still LR. This problem frequently arises in hand-writing a compiler and often was resolved by trial-and-error. A complete characterization and efficient algorithm for solving this problem are presented. Improved algorithms are given for related problems on networks and in the theory of ordered sets. The theory of the syntactic and semantic aspects of the compiler generator is presented and an implementation using these principles is described.