The ASF+SDF Meta-Environment is an interactive language development environment whose main application areas are definition and implementation of domain-specific languages, generation of program analysis and transformation tools, and production of software renovation tools. It uses conditional rewrite rules to define the dynamic semantics and other tool-oriented aspects of languages, so the effectiveness of the generated tools is critically dependent on the quality of the rewrite rule implementation. The ASF+SDF rewrite rule compiler generates C code, thus taking advantage of C's portability and the sophisticated optimization capabilities of current C compilers as well as avoiding potential abstract machine interface bottlenecks. It can handle large (10,000+ rule) language definitions and uses an efficient run-time storage scheme capable of handling large (1,000,000+ node) terms. Term storage uses maximal subterm sharing (hash-consing), which turns out to be more effective in the case of ASF+SDF than in Lisp or SML. Extensive benchmarking has shown the time and space performance of the generated code to be as good as or better than that of the best current rewrite rule and functional language compilers.

PIM is an equational logic designed to function as a “transformational toolkit” for compilers and other programming tools that analyze and manipulate imperative languages. It has been applied to such problems as program slicing, symbolic evaluation, conditional constant propagation, and dependence analysis. PIM consists of the untyped lambda calculus extended with an algebraic data type that characterizes the behavior of lazy stores and generalized conditionals. A graph form of PIM terms is by design closely related to several intermediate representations commonly used in optimizing compilers. In this article, we show that PIM's core algebraic component, PIM t , possesses a complete equational axiomatization (under the assumption of certain reasonable restrictions on term formation). This has the practical consequence of guaranteeing that every semantics-preserving transformation on a program representable in PIM t can be derived by application of PIM t rules. We systematically derive the complete PIM t logic as the culmination of a sequence of increasingly powerful equational systems starting from a straightforward “interpreter” for closed PIM t terms. This work is an intermediate step in a larger program to develop a set of well-founded tools for manipulation of imperative programs by compilers and other systems that perform program analysis.

Current program generators usually operate in a greedy manner in the sense that a program must be generated in its entirety before it can be used. If generation time is scarce, or if the input to the generator is subject to modification, it may be better to be more cautious and to generate only those parts of the program that are indispensable for processing the particular data at hand. We call this lazy program generation . Another, closely related strategy is incremental program generation . When its input is modified, an incremental generator will try to make a corresponding modification in its output rather than generate a completely new program. It may be advantageous to use a combination of both strategies in program generators that have to operate in a highly dynamic and/or interactive environment.

It is common practice to specify textual patterns by means of a set of regular expressions and to transform this set into a finite automaton to be used for the scanning of input strings. In many applications, the cost of this preprocessing phase can be amortized over many uses of the constructed automaton. In this paper new techniques for lazy and incremental scanner generation are presented. The lazy technique postpones the construction of parts of the automaton until they are really needed during the scanning of input. The incremental technique allows modifications to the original set of regular expressions to be made and reuses major parts of the previous automaton. This is interesting in applications such as environments for the interactive development of language definitions in which modifications to the definition of lexical syntax and the uses of the generated scanners alternate frequently.

An axiomatic algebraic calculus of modules is given that is based on the operators combination/union, export, renaming, and taking the visible signature . Four different models of module algebra are discussed and compared.

An LR-based parser generator for arbitrary context-free grammars that generates parsers by need and handles modifications to its input grammar by updating the parser it has generated so far is described. The need for these techniques is discussed in the context of interactive language definition environments. All required algorithms are presented. Measurements are given comparing their performance with that of conventional techniques.>

An LR-based parser generator for arbitrary context-free grammars is described, which generates parsers by need and processes grammar modifications by updating already existing parsers. We motivate the need for these techniques in the context of interactive language definition environments, present all required algorithms, and give measurements comparing their performance with that of conventional techniques.

Most programming environments are much too complex. One way of simplifying them is to reduce the number of mode-dependent languages the user has to be familiar with. As a first step towards this end, the feasibility of unified command/programming/debugging languages, and the concepts on which such languages have to be based, are investigated. The unification process is accomplished in two phases. First, a unified command/programming framework is defined and, second, this framework is extended by adding an integrated debugging capability to it. Strict rules are laid down by which to judge language concepts presenting themselves as candidates for inclusion in the framework during each phase. On the basis of these rules many of the language design questions that have hitherto been resolved this way or that, depending on the taste of the designer, lose their vagueness and can be decided in an unambiguous manner.