Search

We describe a new language translation framework (partial translation) and the implementation of one of its instances: the C-$cation of Binary Prolog. Partial C-ification is a translation framework which compiles sequences of emulator instructions down to native code (on top of a C compiler). In the case of logic programming languages, their complex control structure, some large instructions, and the management of the symbol table are left to the emulator while the native code chunks will deal with relatively long sequences of simple instructions. The technique can be seen as an automatic specialization with respect to a given program of the traditional instruction folding techniques used to speed-up emulators. When the target language of the host compiler is the same as the implementation language of the emulator (say C), the emulator, the representation of the byte code as a C data structure, some other C-ified library routines and handwritten C-code can all be compiled and linked together to a form a stand-alone application. Communication between the run-time system (still under the control of the emulator) and the C-ified chunks is handled as follows. The emulated code representation of a given program (in particular the compiler itself) is mapped to a C data structure which allows exchange of symbol table information at link time. This is compiled together with the C-code of the emulator to a stand alone executable with performance in the range between pure emulators and native code implementations. We give full details and performance analysis of the Cification of a continuation passing Binary ProIog engine for which large write-mode sequences and the absence of a call-return mechanism make the framework particularly well suited. The method ensures a strong operational equivalence between emulated and translated code which share exactly the same observables in the run-time system. An important characteristic is easy debugging of t,he resulting compiler, coming from the full sharing of the run-time system between emulated and compiled code and the following property we ca.ll instruction-level compositionality: if every translated instruction has the same observable effect on a (small) subset of the program state (registers and a few data areas) in emulated and translated mode, then arbitrary sequences of emulated and translated instructions are operationally equivalent.

Aristotle provides program analysis information, and supports the development of software engineering tools. Aristotle's front end consists of parsers that gather control flow, local dataflow and symbol table information for procedural language programs. We implemented a parser for C by incorporating analysis routines into the GNU C parser; a C++ parser is being implemented using similar techniques. Aristotle tools use the data provided by the parsers to perform a variety of tasks, such as dataflow and control dependence analysis, dataflow testing, graph construction and graph viewing. Most of Aristotle's components function on single procedures and entire programs. Parsers and tools use database handler routines to store information in, and retrieve it from, a central database. A user interface provides interactive menu-driven access to tools, and users can view results textually or graphically. Many tools can also be invoked directly from applications programs, which facilitates the development of new tools. To assist with system development and maintenance, we are also creating support tools for managing bug and test suite databases.

A framework for specification-based testing is demonstrated on a symbol table case study, specified using the Z notation. Test derivation and structuring is discussed, as well as applications of the framework in deriving test oracles and aiding regressing testing during maintenance. Areas for further research and discussion are comparison of heuristics with regard to generated test suites and usability, formalising testing heuristics, and the discrepancy between functional testing and robustness testing.

In this paper we describe a collection of techniques for the design and implementation of concurrent compilers. We begin by describing a technique for dividing a source program into many streams so that each stream can be compiled concurrently. We discuss several compiler design issues unique to concurrent compilers including source program partitioning, symbol table management, compiler task scheduling and information flow constraints. The application of our techniques is illustrated by a complete design for a concurrent Modula-2+ compiler. After describing the structure of this compiler's performance that demonstrates that significant improvements in compilation time can be achieved through the use of concurrency.

An algorithm is given to translate a relatively low-level intermediate representation of a program into assembly code or machine code for a target computer. The algorithm is table driven. A construction algorithm is used to produce the table from a functional description of the target machine. The method produces high quality code for many commercially available computers. By replacing the table, it is possible to retarget a compiler for another kind of computer. In addition techniques are given to prove the correctness of the translator.

A defining characteristic of “functional” specifications is the absence of assignments: updates of tables and data structures are expressed by giving the relationship between the new and old values. An obvious implementation allocates separate space for new and old values and may consume a lot of storage. However, even when updates of attributes like symbol tables are expressed functionally, we would like to avoid making copies of the symbol table during attribute evaluation. In other words, if possible, the implementation should have a single global copy of the table that is updated using assignments. Since the value of the global copy changes during computation, the order of evaluation has to be chosen carefully. In this paper, we partition attributes into classes, the problem being to determine if there exists an evaluation order that allows each class to share a global storage area. The solution extends to handle symbol tables for block structured languages.More precisely, consider a directed acyclic graph D in which vertices represent attribute values to be computed. Associated with each vertex is a label indicating the storage area to be shared by the vertex. Storage used during the evaluation of D is studied by playing a pebble game on D with the following steps: (1) pebble (i.e. place a pebble) on a source; (2) pebble a vertex if all its successors have pebbles (a pebble may be moved to the vertex from one of its successors); (3) pick up a pebble. Each vertex must be pebbled exactly once. The use of global storage is formalized by defining single pebblings, in which at most one of the vertices with a given label has a pebble at any time. The results also apply to a form of pebbling, called chain pebbling, that allows symbol tables for block structured languages to be studied.

A compiler is traditionally partitioned into a (mostly) machine independent Front End which performs lexical, syntactic, and semantic analysis, and a machine dependent Back End which performs optimization and code generation. In the Ada compiler being implemented at Carnegie-Mellon University in the PQCC project, it is useful to identify a set of phases occurring at the start of the Back End - i.e., "Middle End" - after semantic analysis but before optimization. These phases, known collectively as "CWVM" (an abbreviation for "Compiler Writer's Virtual Machine") make basic representational choices and reflect these in an expanded program tree. This paper describes both TCOLAda - the intermediate language interface produced by the Front End - and the phases comprising CWVM. TCOLAda is a graph structured high level representation of the source program which includes both the symbol table and the program tree. The CWVM phases perform transformations of the TCOLAda graph which fall into three categories: language oriented (e.g., expansion of checking for constructs such as array indexing), virtual machine oriented (e.g., translation of up-level addressing into "display" vector accesses), and actual machine oriented (e.g., expansion of component selection into address arithmetic).

As various parts of the compiling process have become better understood, it has been possible to package this understanding in tools that can be used by nonspecialists. This talk describes tools for parser generation and lexical analyzer generation which are available under the UNIX% operating system. It will also touch on some less successful attempts to package understanding of symbol table management. In addition to specific tools, the UNIX system eases many of the ancillary tasks of the compiler writer: debugging, regression testing, and constructing new versions of the compiler, to name a few. The talk will draw from practical experience in the construction of a portable compiler for the language C, which has been moved to over a dozen different machines. Since the early history of compilers, researchers have attempted to systematize and automate the production of compilers. The most successful aspect of this attempt has been syntax analysis. It is now commonplace to use a table-driven syntax analyzer which is automatically constructed from a generalized context-free grammar specifying the syntax of the source language (see, for example, [1]). Such an analyzer is easily obtained or modified, provably correct, and modular. In order to automate the production of the code-generator module of a compiler, it is desirable to take a similar approach - namely, to find techniques to construct the code generator automatically from an easily specified description of the computer architecture. We would again have the advantages that the code-generator would be provably correct, modular, and easily modified to generate code for a new kind of machine. In the talk, a technique will be presented to provide an easily specified machine description to a program which computes a table of information from which another algorithm generates probably correct code. The results, described more fully in [4], [5], [6], are based in part on earlier work reported in [7] and [8]. Other current research on this topic, described in [2] and [3], will also be discussed. The PQCC (Production-Quality Compiler-Compiler) project is an effort aimed at the automatic construction of production quality, optimizing compilers. The goal, is, with no more than a few man-months effort, to produce a compiler that is competitive in every respect with the best hand-crafted compilers available today. Input to this automatic construction process is formal descriptions of the source language and target machine. PQCC differs from nearly all previous work in this area in that we are concentrating on the semantic and machine-dependent phases of compilation—as opposed to lexical and syntactic analysis. Each phase has been formalized in a manner that permits it to be expressed in table-driven form. Thus the automatic construction of the compiler consists of deriving these tables from the semantic definitions of the language and target machine. Table-driven prototypes have just been completed for most compiler phases, and work is now proceeding on improving and automating their generation. The talk will go into some detail on one of these phases, code generation, discussing the formalization of the (table-driven) algorithms and the automatic construction of the tables from a machine description.

This paper describes a compiler called ORACLE which allows a student to examine the actions performed by a simple compiler. Two features are provided to assist the student. The first called replacement mode, provides the necessary conditions to simulate the replacement of three compiler components: symbol table management, lexical analysis, and syntax analysis. Each replacement module is monitored by ORACLE in order to detect errors and to verify correct operation. The second, a trace option, permits source statements to initiate or terminate a selective monitoring of the actions of the compiler.

Newer programming languages such as Modula and Euclid provide more control than traditional Algol-like languages such as ALGOL-60 and Pascal over the inheritance, in inner scopes, of named entities available in outer scopes. They also provide mechanisms whereby chosen entities from inner scopes may be made available to outer scopes. In this paper we show how a hashed symbol table can be organized to implement these new scope rules in a time and space efficient way.

APL0 is a simple modern APL written entirely in APL2. It is smaller than APL2 (or even VSAPL) but is more powerful. APL0 is implemented as a shell that translates APL0 statements into standard APL2. Details such as symbol table and workspace management are all handled by native APL2. The result is a powerful and malleable APL system.

The object-oriented paradigm is applied to the interpreting of programming languages. An intermediate representation of a program is created as a collection of objects representing various entities in the conceptual world of the source language. These objects cover both the static and the dynamic aspects of a program. As a major advantage of this approach, issues that are traditionally handled by very different techniques (like symbol table management and the generation and execution of intermediate code) can be treated in a unified manner. The specification language of an interpreter generator based on these principles is described.

An incremental language processor is one that accepts as input a sequence of substrings of the source language and maps them independently onto fragments in some object code. The ordered sequence of these object code fragments are then either compiled, in which case we have an incremental compiler, or interpreted. In the first case the advantage resulting is that subsequent changes in the source program entail only reprocessing the source fragments affected and recompiling the updated collection of object code fragments. In an environment where small changes are made frequently to large programs, e.g. debugging, the curtailment of reprocessing is attractive. In the second case the object code fragments are the actual run-time program representation, and hence inter-fragment relations are transiently evaluated as needed in the process of execution, with no long-term preservation of these relationships beyond the scope of their immediate need in execution time. This permits the possibility of program recomposition in the midst of execution, one of the principal characteristics of conversational computing. Many conversational language processors execute a program representation functionally analogous to parse trees, i.e. the syntax analysis of a fragment, insofar as it is possible, is done at fragment load time. This representation choice is popular because many of the expensive aspects of interpretation, including character string scanning, symbol table lookup, and parsing, are performed once only and do not contribute to the execution overhead. This paper is devoted to examining the question of the construction of such a parser in a general manner for an arbitrary source language.

A set of four microcoded subprocessors have been designed for the Microdata 3200 to provide compact, efficient compilation and execution of LR(k) languages. The scanner subprocessor extracts tokens from an input string; the parser subprocessor executes a stack automation program which parses the source program; the semantics subprocessor provides operators for data handling in tables and stacks, symbol table searching, and object code generation; the execution subprocessor is a stack machine designed for ALGOL-like languages. The design and interaction of these subprocessors is discussed.

ASSIST - Assembler System for Student Instruction and Systems Teaching, is a self-modifiable IN-CORE Assembler F compatible System/360 assembler-interpreter. It allows students to replace portions of the assembler using a process which is economical and provides good diagnostics. It has the capability of assembling a subroutine written in assembler language, linking the routine to itself and then executing another program utilizing the newly linked subroutine. The replaceable subroutines perform many of the basic functions required in an assembler, e.g. symbol table management, general expression evaluator, etc. The new subroutine results are compared with standard results and thus explicit diagnostics are available. Performance figures are supplied.