Stress testing of compilers for modula-2

During standardization discussions on Modula-2 the question was raised whether the future standard should need a clause stating a set of minimal requirements for conforming implementations regarding the ‘structuredness’ of lexical, syntactical and run-time constructs in programs written in this language. It was decided to test a number of compilers to find their actual limits on the structuredness of some of these constructs. The test results do not only show these limits, but the inability of some compilers to handle large and complex inputs is shown as well.     

Converting interpreters into compilers

There is an effective and quite general method of manually deriving compilers from programming-language interpreters without dealing directly with machine language. The method is an implementation of the largely theoretical and under-appreciated concept of partial computation, but can be understood on its own terms. It involves the translation of a source program's intermediate form into the interpreter's implementation language. This paper shows how the method can be used to transform both a sample iterative interpreter and a sample recursive interpreter into compilers. The result can be a large gain in program execution speed. Other advantages of the method, including the ease and practicality of applying it, are discussed.     

An Optimizing Compiler for Parallel Chemistry Simulations

Well designed domain specific languages have three important benefits: (1) the easy expression of problems, (2) the application of domain specific optimizations (including parallelization), and (3) dramatic improvements in productivity for their users. In this paper we describe a compiler and parallel runtime system for modeling the complex kinetics of rubber vulcanization and olefin polymerization that achieves all of these goals. The compiler allows the development of a system of ordinary differential equations describing a complex vulcanization reaction or single-site olefin polymerization reaction—a task that used to require months—to be done in hours. A specialized common sub-expression elimination and other algebraic optimizations sufficiently simplify the complex machine generated code to allow it to be compiled—eliminating all but 8.0% of the operations in our largest program and enabling over 60 times faster execution on our largest benchmark codes. The parallel runtime and dynamic load balancing scheme enables fast simulations of the model.     

Converting a portable Pascal p-code interpreter to a code generator

This is a technical note that assumes reader familiarity with Pagan's paper on converting scaled down Pascal p-code programming language interpreters into simple compilers.¹ This note discusses the extension of Pagan's methods to a full-scale Pascal-to-C translator. In order to make procedure calls and typed function calls work properly for such a translator, it was found necessary to add type information to one of the p-code calling instructions (and alter the Pascal-to-p-code translator accordingly). A table of execution times for Pagan's ‘50 primes’ bench-mark program shows the improvements obtained as a result of successive refinements in the Pascal-to-C translator, until the present version that uses C ‘register variables’ for integer arithmetic.² Programs compiled using this system can also be linked into C programs as functions or procedures and can be debugged using standard C debuggers.     

A simple system for generating efficient lexical scans

A language for specifying lexical scans is described.The language uses the model of a finite state automation with a limited back-up facility.It is efficiently implementable and is machine independent except for one statement which depends on the machine's character set.     

Producing the left parse during bottom-up parsing

Schmeiser and Barnard described a method for producing the left parse at the end of the bottom-up parsing process. We improve their method in the sense that the left parse is actually produced during the bottom-up parsing process (i.e., with considerably less delay).     

Abstract execution: A technique for efficiently tracing programs

Many areas of computer performance analysis require detailed traces of events that occur during a program's execution. Collecting traces is expensive. The additional code required to record events greatly slows a program's execution. In addition, the resulting trace files can grow unmanageably large. This paper describes a technique called abstract execution that alleviates both problems. Abstract execution records a small set of events during the traced program's execution. These events serve as input to an abstract version of the program that generates a full trace by re-executing selected portions of the original program. This process greatly reduces both the cost of tracing the original program and the size of the trace files. The cost of regenerating a trace is insignificant in comparison to the cost of applications that use it. This paper also describes a system called AE that implements Abstract Execution. The paper contains measurements that demonstrate that AE can efficiently trace large programs.     

Even faster lr parsing

Conventional LR parser generators create tables which are used to drive a standard parser procedure. Much faster parsers can be obtained by compiling the table entries into code that is directly executed. A possible drawback with a directly executable parser is its large size. In this paper, we introduce optimization techniques that increase the parsing speed even further while simultaneously reducing the size of the parser.     

Incremental generation of LR parsers

Implementation of a new compiler usually requires making frequent adjustments to grammar definitions. An incremental technique for updating the parser tables after a monor change to the grammer could potentially save much computational effort. More importantly, debugging a grammar is made easier if the grammar is re-checked for correctness after each small change to the grammar. The basic design philosophy of an incremental parser generator, and incremental algorithms for LR(0), SLR(1) and LALR(1) parser generation are discussed in this paper. Some of these algorithms have been incorporated into an implementation of an incremental LALR(1) parser generator.