POPL

We consider methods of describing the syntax of programming languages in ways that are more flexible and natural than conventional BNF descriptions. These methods involve the use of ambiguous context-free grammars together with rules to resolve ...

Recently strict deterministic grammars and languages have been introduced [9,10,11]. This family of languages is quite fundamental in the study of the mathematical properties of deterministic languages and in dealing with some classical families of ...

Precendece techniques have been widely used in the past in the construction of parsers. However, the restrictions imposed by them on the grammars were hard to meet. Thus, alteration of the rules of the grammar was necessary in order to make them ...

A substantial portion of any programmer's time is spent in debugging. One of the major services of any compiler ought to be to provide as much information as possible about compile-time errors in order to minimize the time required for debugging. A good ...

This paper proposes axioms to define a sequence of language-classes; the most general is that of "programming language", the most restricted has some simple and attractive properties. Here "language" is used in its traditional sense as referring to a ...

In order to define the semantics of PL/I in a form which is both precise and readable, a method of definition has been developed which employs an abstract machine operating on tree-structured data. The classes of trees involved are defined by formal ...

This paper analyzes the semantics of the programming language SNOBOL4, following the mathematical approach proposed by D. Scott and C. Strachey. The study aims at clarifying a rather unusual semantic structure, and at demonstrating that the mathematical ...

The title is not a statement of fact, of course, but an opinion about how language designers should think about types. There has been a natural tendency to look to mathematics for a consistent, precise notion of what types are. The point of view there ...

High level programming languages tend to free a programmer from concern about the underlying machine structure and permit him to talk about his problem domain in more direct terms. Thus, he may imagine that objects such as real numbers, character ...

The purpose of this paper is to advise an approach (and to support that advice by discussion of an example) towards achieving a goal first announced by John McCarthy: that compilers for higher-level programming languages should be made completely ...

The PLANNER project is continuing research in natural and effective means for embedding knowledge in procedures. In the course of this work we have succeeded in unifying the formalism around one fundamental concept: the ACTOR. Intuitively, an ACTOR is ...

This paper describes a theorem prover that embodies knowledge about programming constructs, such as numbers, arrays, lists, and expressions. The program can reason about these concepts and is used as part of a program verification system that uses the ...

This paper discusses the desirability of procedure linkage optimization and sketches a general theory of interpretive semantics which is motivated by technical problems in specifying and validating program transformations that optimize procedure ...

A technique is presented for global analysis of program structure in order to perform compile time optimization of object code generated for expressions. The global expression optimization presented includes constant propagation, common subexpression ...

There is an ordering of the nodes of a flow graph G which topologically sorts the dominance relation and can be found in 0(edges) steps. This ordering is the reverse of the order in which a node is last visited while growing any depth-first spanning ...

Arrays are among the best understood and most widely used data structures. Yet even now, there are no satisfactory techniques for handling algorithms involving extendible arrays (where, e.g., rows and/or columns can be added dynamically). In this paper, ...

We consider partially interpreted monadic schemas in which some functions are specified to commute, or some function is specified to be invertible. The decision problems considered are those of halting, divergence, equivalence, inclusion and ...