POPL

The concept of grammar forms [4,5] provides evidence that there seems to be no way to base the definitions of many grammar types used in parsing and compiling solely on the concept of productions.

Strict interpretations, as introduced in [3,5], of ...

The close relationship between programming language syntax, context-free grammars (abbreviated cfgs), parsing, and compiling is well-known and is extensively discussed in [1]. Unfortunately, many of the problems about programming languages, one might ...

Easy as the task may seem, many compilers generate rather inefficient code. Some of the difficulty of generating good code may arise from the lack of realistic models for programming language and machine semantics. In this paper we show that the ...

The translation process may be divided into a syntactic phase and a semantic phase. Context-free grammars can be used to describe the set of syntactically correct source texts in a formal yet intuitively appealing way, and many techniques are now known ...

An automated business data processing system designer is described. Attention is centered on the I/O aspects of such systems and the development of optimizing design heuristics.

The design of data organization and data accessing procedures for data ...

We are all aware of the development of increasingly sophisticated, elaborate, and expensive computer programs, particularly in the fields of artificial intelligence, data base management, and intelligent systems. The need for techniques to deal with ...

This paper reports on a system, THESYS, that synthesizes LISP recursive programs from examples of what they do. There has been recent interest in this form of program specification[1,4,8]. The theory of such inductive systems has been investigated by ...

A new approach to the design of a programming language and its processor is proposed and some of the techniques necessary to realize the design are investigated. The language would have a precisely specified syntax and semantics, with both designed to ...

A different way to execute pure LISP programs is presented. It delays the evaluation of parameters and list structures without ever having to perform more evaluation steps than the usual method. Although the central idea can be found in earlier work ...

We explore the notion of an induction variable in the context of a set-theoretic programming langugage. An appropriate definition, we believe, involves both the necessity that changes in the variable around a loop be easily computable and that they be ...

Structured programming emphasizes programming language constructs such as while loops, until loops, and if then else statements. Properly used, these constructs make occurrences of loops and branching of control obvious. They are preferable to goto ...

A chain production is a production of the form A→M where A is a nonterminal and M is either a terminal or nonterminal. Pager in [Pag5] has presented an algorithm which removes all chain reductions from LR(1) parsers after they have been constructed.

In ...

The syntactical analysis of pictures derived by a context-free graph-grammar is a rather complicated algorithm. Analogously to the development for Chomsky-grammars ten years ago we define the precedence-graph-grammars as a subclass of the context-free ...

We treat a program as an object of manipulation, determine items of program constancy, and simplify the program based on the constancy. Some motivation for program manipulation is presented, along with two examples of “higher level optimization” written ...

Program development often proceeds by transforming simple, clear programs into complex, involuted, but more efficient ones. This paper examines ways this process can be rendered more systematic. We show how analysis of program performance, partial ...

We describe how to transform certain flowchart programs into equivalent explicit primitive recursive programs. The input/output correctness conditions for the transformed programs are more amenable to proof than the verification conditions for the ...

A Data Flow program [1,2] is a flow-chart like network of operators which compute concurrently, dependent only on the availability of the data which flow along the paths. Each operator has only a local effect, transforming input data to output data. ...

SL5 is a programming language developed for experimental work in generalized pattern matching and high-level data structuring and access mechanisms. This paper describes the procedure mechanism and the conventions for the interpretation of identifiers ...

SYNVER is an automatic programming system for the synthesis of solutions to problems of synchronization among concurrent processes from specifications written in a high level assertion language (SAL). The correctness of the solutions constructed by ...

Proofs of program correctness tend to be long and tedious whereas testing, though useful in detecting errors, usually does not guarantee correctness. This paper introduces a technique whereby test data can be used in proving program correctness. In ...