2,199 papers · page 107 of 110
An LL(1)-based error-corrector which operates by insertion-only is studied. The corrector is able to correct and parse any input string. It is efficient (linear in space and time requirements) and chooses least-cost insertions (as defined by the user) in correcting syntax errors.…
We propose a new optimization technique applicable to set-oriented languages, which we shall call general common subexpression elimination. It involves the computation of the IAVAIL(n) function for all nodes n in a flow graph, where IAVAIL(n) is the set of expressions such that a…
This paper presents a systematic approach to the problem of generating good code with a compiler that is easy to construct. A compiler structure is proposed which relies on interprocedural data flow analysis, global optimization, and an intermediate language schema to simplify th…
Structuring can be defined independently of what is being structured, and can be applied profitably to more than one domain. Using one mechanism to structure both values and assignments, we obtain equivalents for a variety of data and control structures. Structuring assignments i…
This paper presents a mechanism for the arbitration of parallel requests to shared resources. This mechanism is the serialize, which may be described as a kind of protection mechanism, in that it prevents improper orders of access to a protected resource. The mechanism is a gener…
A standard approach to the analysis of program structure for the purpose of code optimization is to construct the "control flow graph" which models the possible execution paths through the program. Various graph algorithms can be applied to the control flow graph to produce data …
We use the concept of evaluation up to a given threshold of information to generalize the semantics of call by value and assignment to non-discrete domains, and to define a formal semantics for generic procedures. We then prove the correctness of McCarthy's transformation of iter…
In his thesis Paterson proved that equivalence is decidable for program schemata such that every instruction falls on at most one loop and only monadic function signs appear. Here we remove the restriction on function signs. The problem reduces to that of showing that the numeric…
In this paper we show that some prevailing ideas on the elimination of left recursion in a context-free grammar are not valid. An algorithm and a proof are given to show that every proper context-free grammar is covered by a non-left-recursive grammar.
We consider the problem of automating some of the duties of programmers. We take as our point of departure the claim that data management has been automated to the point where the programmer concerned only about the correctness (as opposed to the efficiency) of his program need n…
This paper is concerned with difficult global flow problems which require the symbolic evaluation of programs. We use, as is common in global flow analysis, a model in which the expressions computed are specified, but the flow of control is indicated only by a directed graph whos…
Control flow relations in a high level language program can be represented by a hierarchy of small graphs that combines nesting relations among statements in an ALGOL-like syntax with relevant perturbations caused by goto or leave statements. Applications of the new style of repr…
One of the most attractive techniques in optimizing LR parsers is to eliminate reductions by semantically insignificant productions of the form A → X (single productions), where X is a nonterminal or a terminal; such a modification can lead to substantial savings in both space an…
This paper describes a system which checks correctness of array accesses automatically without any inductive assertions or human interaction. For each array access in the program a condition that the subscript is greater than or equal to the lower bound and a condition that the s…
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 computational complexity of genera…
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 statements, which tend to obscu…
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 corresponding flowchart programs…
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 in SL5. Procedure invocation…
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 small. We attempt to justify…