Summary Classical strategies for matching identifier uses with declarations cannot handle the complexities of modern languages: arbitrarily qualified superclass names, cyclic dependence among lookup operations, and contextual access constraints. We have developed a language‐independent algorithm and supporting data structure that overcome these problems. A well‐defined interface allows introduction of arbitrary code to enforce language‐specific constraints within the basic lookup operations. This paper explains the limitations of the classical strategies, presents the concepts on which our approach is based, and showcases an implementation based on attribute grammars. We explore the major issues through a series of examples and show how one can deal with those issues in a general framework. Many of the issues are specific to a particular language, and in those cases, we explain the solutions that our general interface supports. Although attribute grammars simplify the task of incorporating the model into a compiler, the model itself is completely independent of attribute grammars. We validated our model by using an implementation to process programs in several representative languages. In particular, we mechanically compared the results produced by that implementation with those produced by the Java SE 8 compiler on complete Java programs that are in general use. Performance data obtained during this processing show that our implementation is efficient. Copyright © 2017 John Wiley & Sons, Ltd.

Abstract Type analysis can be characterized by a language‐independent collection of standard computational roles such as ‘typed identifier use’ (e.g. a variable name appearing in an expression) and ‘dyadic expression’ (e.g. addition of two values). A type analyzer for a specific language is then defined by stating which language construct(s) play each role. The computational roles provide a framework for understanding the general process and a vocabulary for applying that understanding to the solution of particular problems. We have captured this knowledge in attribute grammar modules that are carefully designed to be combinable and adaptable, exporting language‐independent roles that define the general type analysis problem. From this collection, the compiler designer instantiates the appropriate modules and identifies the relevant source‐language constructs; an attribute grammar processor then weaves the necessary computations into the compiler's semantic analyzer. Our attribute grammar modules provide a precise definition of the actions constituting the various roles and the dependences among them. They can therefore also be used to describe the type analysis process to students, or to specify a hand‐coded semantic analyzer. Copyright © 2009 John Wiley & Sons, Ltd.

Current literature states that the undergraduate curriculum can no longer afford the luxury of a traditional compiler construction course. Nevertheless, there is an increasing need for an understanding of how to design and implement domain-specific languages. This paper presents a modern course in compiler construction, designed to provide a student with the capability of quickly constructin robust processors for a variety of language-related applications.

The broadening of computer science education has called into question the roles of many traditional core courses. In order to remain viable, courses such as compiler construction must provide a coherent view of their subject matter that fits with the rest of the institution's curriculum. Three strategies have evolved for this course. As described in this paper, each strategy provides a model that a professor can use to design an appropriate course for their situation.

Last year we described the PL-Detective, a system for building exercises and demonstrations in a programming languages course. One of the main goals of the PL-Detective was to provide an experimental environment with which students could interact in order to discover the information that they needed to complete the exercise. In this paper we evaluate the PL-Detective with respect to this goal. We present data from a class of 29 groups of two or three students that used the PL-Detective for 11 exercises. Our data shows that students are both effective and efficient at getting information from the PL-Detective.

The educational literature recognizes that people go through a number of stages in their intellectual development. During the first stage, called received knowledge or dualism, people expect knowledge to be handed to them by authority figures (thus "received") and think in terms of black and white (thus "dualism"). Our experience indicates that many computer science students are at this first stage of learning. To help students move beyond this stage, we describe a system and strategy, the PL-detective, to be used in a "concepts of programming languages" course. Assignments using this system directly confront students with the notion that there are often multiple equally good answers and that discussion with students (rather than asking the instructor) is an effective way of learning how to reason.

Our industrial advisory boards tell us that our students are well prepared technically, but they lack important group work skills. Simply adding project courses and requiring that assignments be done in groups has not improved the situation. A careful study of student culture in Computer Science has uncovered barriers to collaboration, which can be overcome only by pervasive changes in the way we approach our curriculum.

The educational literature recognizes that people go through a number of stages in their intellectual development. During the first stage, called received knowledge or dualism , people expect knowledge to be handed to them by authority figures (thus “received”) and think in terms of black and white (thus “dualism”). Our experience indicates that many computer science students are at this first stage of learning. To help students move beyond this stage, we describe a system and strategy, the PL-Detective, to be used in a Concepts of Programming Languages course. Assignments using this system directly confront students with the notion that they can create knowledge via interactions with the PL-Detective and that discussion with students (rather than asking the instructor) is an effective way of learning how to reason. We present experimental results that show that the PL-Detective is effective in helping students move beyond the stage of received knowledge.

Concepts taught in large, lower-division computer science courses are carefully explained in standard textbooks. Thus we hypothesized that the classroom experience should not consist primarily of a restatement of those explanations by the professor. Instead, it should provide an opportunity for the students to learn through a process of conversation among themselves and with the professor. We were able to establish such a process in a sophomore-level course with an enrollment of 116 students. This change led to a doubling of the percentage of A and A- grades compared to historical values.

In industry, programmers work in groups to design and implement substantial pieces of software. In contrast, most programs that students write in classes are toy programs involving little or no group work. To address this discrepancy, we have developed a software infrastructure that aims to teach group work skills to students in computer science courses and also enables students to tackle larger and more significant projects. We are in the process of deploying this infrastructure in a three course sequence at the University of Colorado: Data Structures---Programming Languages---Compiler Construction.

A data format for context-free grammar representation called COMAR is proposed. It is intended to be used for integration and communication of various tools operating on CFGs, e.g. language-invariant grammar transformations, analysis of grammar properties, and parser generation. A compact ASCII file representation for COMAR is defined to be used as an interface language for such tools. Routines necessary for tool development based on COMAR are available: a front end producing COMAR representation from EBNF text, a set of I/O routines, and a set of functions constructing and accessing a Comar data structure in memory.

Abstract This paper examines a common design for a lexical analyser and its supporting modules. An implementation of the design was tuned to produce the best possible performance. In effect, many of the optimizations that one would expect of a production‐quality compiler were carried out by hand. After measuring the cost of tokenizing two large programs with this version, the code was ‘detuned’ to remove specific optimizations and the measurements were repeated. In all cases, the basic algorithm was unchanged, so that the difference in cost is an indication of the effectiveness of the optimization. Comparisons were also made with a tool‐generated lexical analyser for the same task. On the basis of the measurements, several specific design and optimization strategies are recommended. These recommendations are also valid for software other than lexical analysers.

Abstract Many Pascal compilers generate incorrect code for statements. The trap that catches many implementors, whereby overflow is generated incorrectly, is explained and means for avoiding it are discussed (with attention to cost). Most common languages have a similar construct in which iteration is ‘controlled’ by a sequence of values in that a variable takes on successive values of the sequence for the several executions of the ‘body’. Often, the size step is not restricted to plus‐or‐minus one (as in Pascal) and the correctness situation cannot be characterized in such black and white terms. Typically, there is a range of behaviours that are valid and the compiler writer is able to choose a compromise between time‐space overheads and avoidance of unnecessary overflow indications; we describe the latter behaviour as robust. We present techniques for implementation appropriate to several languages and direct comments at language designers warning against both ignoring and overestimating the cost of robustly implementing iteration statements with arbitrary step size. Lastly, we criticize the design of instructions available in some machines, ostensibly to support the implementation of such sequence controlled iteration statements.

Abstract How expensive is it for a compiler to process horizontal tab characters introduced arbitrarily into program text? The measurements discussed in this note show that if tabs are uniformly expanded by the source text input module of the compiler, the process of reading and tokenizing the source program is slowed by about 20 per cent. This overhead can be completely eliminated by using an ‘extra space count’ in the lexical analyser instead of a uniform expansion.

Abstract The ‘fact’ that compilers employing generated parsers suffer significant performance degradation dis‐a‐vis recursive descent compilers is entrenched in the folklore of computing. We give detailed measurements that support this belief when the entire compiler is written in Pascal. We then define a general interface for a parsing module that hides significantly more information than usual, simplifying the process of generation and integration. This interface makes an assembly‐coded parse table interpreter feasible without changing the language used for the remainder of the compiler. When the parse table interpreter is written in assembly language, the costs of the generated parser are essentially the same as those for recursive descent. (A minor space/time trade‐off is possible, with the recursive descent implementation being slightly bigger and slightly faster.)

Abstract Many Pascal compilers are based upon a model which has two unpleasant properties: a large working set of procedures and lack of flexibility in object code structure. In this paper we analyse the source of these faults and describe an alternative model which avoids them. We then present the details of the key interface in the alternative model, as realized by a particular compiler.

Abstract Janus is a symbolic language intended for use as an intermediate language in the transportation of software. Since its initial design four years ago, it has been used to implement a portable Pascal compiler, in the design of an Algol 68 compiler, and to realize a portable package of mathematical routines. These experiences, together with a critical re‐evaluation of the design criteria, have led to some modification of the specifications of Janus and an increased confidence in the viability of the approach. They have also indicated some problems yet to be solved. This paper reviews the significant lessons which we have learned, and quotes some results which support our confidence.

Abstract Would‐be implementors of portable software often encounter frustrating difficulties when attempting to enter the distributed text into their computers. This paper summarizes various problems which may arise, and indicates how the distributor can head them off. The conventions used by several successful distributors are given to illustrate possible solutions.

Abstract Janus is a symbolic language used to embody the information which is normally passed from the analysis phase of a compiler to the code generators. It is designed for transporting software: A program coded in a high level language can be translated to Janus on one computer, and the resulting output translated to assembly code on another. (The STAGE2 macro processor could be used for the second translation.) In this paper we present the principles upon which Janus is based, and show that it is suited to a wide range of source languages and target computers.

Abstract Periodic location counter sampling is a well‐known technique for conducting performance measurements on operating systems. It is also extremely useful for applications programs. This paper describes a set of interface conventions for such a monitor. SPY, a monitor obeying these conventions, has been implemented on three different computers.

Abstract This paper discusses the use of abstract machine modelling as a technique for producing portable software, i.e. software which can be moved readily from one computer to another. An overview of the principles involved is presented and a critical examination made of three existing abstract machines which were used respectively to implement a macro processor, a text editor and a BASIC compiler.

The techniques of abstract machine modelling and macro processing can be used to develop programs of great mobility. This paper describes the concepts and construction of a system which has been implemented on nine different computers. In no case was more than one man-week required, and most implementations went more rapidly than that.

The techniques of abstract machine modelling and macro processing can be used to construct software which is easily moved from one computer to another. This paper describes a system developed at the University of Colorado which has been implemented on 8 different machines, with efforts ranging from 1 man-day to 1 man-week. We feel that these techniques offer a possible solution to the "software crisis" which is plaguing the computer industry today.

One of the most important problems in computer development today is the difficult job of constructing programs and programming languages to handle a wide variety of tasks. There are two pure approaches to programming language design and an endless number of mixed approaches lying between them. One of the pure approaches, often taken by graduate students in universities, is to create a new programming language for each problem. The other approach, perhaps typified by certain supporters of PL/I, is to design a language which is intended hopefully to be all things to all programmers. Unfortunately, neither of these pure approaches is really practical. People have long recognized the common features of programming problems and most agree that certain techniques are applicable to almost all of them. However, with the burgeoning use of the machine it is not possible to assert with any degree of confidence that we have discovered all useful techniques. A reasonable way to proceed seems to be to design a programming language which contains most of the common features which people have discovered in various problems, but which allows the user to extend and mold the language to suit his particular application.

When a dynamic storage allocation scheme requires variable-length elements, an element of a given length may be requested when no free element large enough is available. This can happen even though the total free space is more than adequate to fulfil the request. In such a situation the program will fail unless some method is at hand for forming the available space into a single element large enough to satisfy the request. We present a procedure for compacting the store such that all of the free space forms a single element.

An iterative array is defined as an infinite set of identical blocks, interconnected in a regular manner. Each block has inputs and outputs, with internal connections from certain inputs to certain outputs. This paper is concerned with the problem of determining, for a given structure internal to each block, the existence of a given path. The path is specified by the relative positions in the array of its endpoints, and the algorithm presented decides whether such a path is possible in the given array. A special case of the general procedure, which tests for a closed path, has been successfully programmed.

This note presents a method for recognizing character strings of variable length, where the length is a priori unknown. The procedure has been used successfully in an assembly program for the English Electric KDF9, and can be applied to a wide range of other programming languages.

In a synchronous circuit an operation is complete when a given number of clock times have elapsed since it was begun. In an asynchronous network no such indication is available, and we must either rely on the network to inform us of completion, or wait for the worst-case delay. The second method is undesirable because normally the network will complete its operation long before the worst-case delay time has elasped. It will be shown here that, for a large class of iterative circuits, the network can be designed to inform us of completion. Moreover, this can be done without recourse to monitoring all lateral states (to see when none are changing).