A portable compiler
Published 1 January 1978Open access
S. C. Johnson
Citations122
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
An overview of the compiler structure and algorithms is given, emphasizing those areas where theory was helpful, and discussing the approaches taken where theory is lacking.
Abstract
A compiler for the C language has recently been constructed which is now compiling C for about half a dozen machines. The compiler was influenced in various ways by recent theoretical developments. This paper gives an overview of the compiler structure and algorithms, emphasizing those areas where theory was helpful, and discussing the approaches taken where theory was lacking.
Keywords
Computer Science
Yacc : Yet Another Compiler Compiler
1,239 Citations1978S. C. Johnson, Murray Hill
Yacc provides a general tool for describing the input to a computer program, together with code to be invoked as each such structure is recognized, and turns such a specification into a subroutine that handles the input process.
Communications of the ACMThe UNIX time-sharing system
970 Citations1983Dennis M. Ritchie, Ken Thompson
Journal of the ACMThe Generation of Optimal Code for Arithmetic Expressions
295 Citations1970Ravi Sethi, Jeffrey D. Ullman
It is shown that the algorithms presented here also minimize the number of storage references in the evaluation, and they are shown to take the shortest possible number of instructions.
Journal of the ACMOptimal Code Generation for Expression Trees
242 Citations1976Alfred V. Aho, S. C. Johnson
A dynamic programming algorithm is presented which produces optimal code for any machine in this class of machines, which runs in time linearly proportional to the size of the input.
Communications of the ACMOn programming of arithmetic operations
132 Citations1958A. P. Ershov
The concepts used without explanation are taken from [1], and the text is intended to be user-friendly.
Journal of the ACMCode Generation for a One-Register Machine
95 Citations1976John Bruno, Ravi Sethi
The problem of generating minimal-length code for such machines is hard in a precise sense; specifically it is shown that the problem is NP-complete.
Code-generation for machines with multiregister operations
25 Citations1977Alfred V. Aho, S. C. Johnson +1 more
A linear-time optimal code generation algorithm is derived for a register-pair machine in which all registers are interchangeable, based on showing that for this model there is an optimal evaluation sequence with limited oscillation between the sub-trees dominated by the children of a given node.
Optimal code generation for expression trees
23 Citations1975Alfred V. Aho, S. C. Johnson
A dynamic programming algorithm is presented which produces optimal code for any machine in the class; this algorithm runs in time which is linearly proportional to the number of vertices in an expression tree.
The competence/performance dichotomy in programming preliminary report
15 Citations1977Vaughan Pratt
The claim that data management has been automated to the point where the programmer concerned only about the correctness of his program need not involve himself in any aspect of the storage allocation problem is taken as a point of departure.
DSpace@MIT (Massachusetts Institute of Technology)The Competence/Performance Dichotomy in Programming
14 Citations1977Vaughan Pratt
A Portable Compiler for the Language C
14 Citations1975Alan Snyder
This paper describes the implementation of a compiler for the language C, designed to be able to be capable of producing assembly-language code for most register-oriented machines with only minor recoding.
Journal of the ACMCode Generation for Expressions with Common Subexpressions
13 Citations1977Alfred V. Aho, S. C. Johnson +1 more
This paper shows the problem of generating optimal code for expressions containing common subexpressions is computationally difficult, even for simple expressions and simple machines.