An algebraic approach to language translation
John L. Knaack · 1995
This dissertation provides a solution to three major problems that characterize current compiler technology: the complexity of compiler construction, the lack of ability to parallelize the compilation process, and the lack of a specification language for the entire compiler. Our solution lies in a new paradigm of language translation called the algebraic compiler which utilizes a pattern-matching parser as the recognizer and a macro-expander as the code generator. This compiler implements a generalized homomorphism from the syntax algebra of the source language into the syntax algebra of the target language which is constructed such that the semantics of a source construct is preserved during the translation. The pattern-matching parser operates by using the specification rules as patterns to be matched against the source string in conjunction with both context and noncontext to determine the strings to be replaced. The recognizer is compositional in nature, hence a compositional code generator in the form of a macro-expander is paired with it. Thus, macro-operations serve as a specification language for the code generator and optimizer, while the BNF rules are the specification language for the recognizer. The incrementality of the specification leads to a simplification of construction of the compiler, and the compositional nature of the recognizer and code generator make them parallelizable. The first chapter explains how compiler construction is simplified with the algebraic compiler. A summary of past attempts at parallel recognition is provided in chapter 2. The theory behind the algebraic compiler and an associated algebraic scanner is presented in chapter 3. A description and performance analysis of two versions of the pattern-matching parser algorithm are shown in chapter 4. The proof of the correctness of the recognizer is provided and several schemes of parallelizing the two algorithms are discussed. In chapter 5, the specification languages of all parts of the compiler are presented and chapter 6 is dedicated to evaluation and further research.