Control flow aspects of semantics directed compiling (Summary)

ABSTRACT

We focus on the part of a compiler between syntax analysis and code generation. A language is specified by adding semantic rules in a functional notation to the syntax of the language. Starting with a small sublanguage of while statements, the semantics of the statement constructs of C is built up incrementally. Using a small ad hoc code generator, a compiler has automatically been constructed from the semantics. The semantic description is analogous to a syntax directed construction of a flow diagram for a program. In analogy with grammars and parser generators, minimal knowledge of the underlying theory is required. For the control flow aspects of languages, efficient compilers can quickly be generated.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	J. A. Goguen , J. W. Thatcher , E. G. Wagner , J. B. Wright, Initial Algebra Semantics and Continuous Algebras, Journal of the ACM (JACM), v.24 n.1, p.68-95, Jan. 1977 [doi>10.1145/321992.321997]
	2	James W. Thatcher , Eric G. Wagner , Jesse B. Wright, More on advice on structuring compilers and proving them correct, Semantics-Directed Compiler Generation, Proceedings of a Workshop, p.165-188, January 14-18, 1980
	3	A. V. Aho, "Translator writing systems: where do they now stand?," Computer13(8), pp. 9-14 (August 1980). This paper is a guest editor's introduction and overview of a special issue on Translator Writing Systems.
	4	Alfred V. Aho , Jeffrey D. Ullman, Principles of Compiler Design (Addison-Wesley series in computer science and information processing), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1977
	5	E. R. Anderson, F. C. Belz, and E. K. Blum, "SEMANOL (73): A metalanguage for programming the semantics of programming languages," Acta Informatica6, pp. 109-131 (1976).
	6	E. R. Anderson, F. C. Belz, and E. K. Blum, "Issues in the formal specification of programming languages," pp. 1-30 in Formal Description of Programming Concepts, ed. E. J. Neuhold, North-Holland, Amsterdam (1978).
	7	J. W. Backus et al., "The Fortran automatic coding system," Western Joint Computer Conference, pp. 188-198 (1957).
	8	Friedrich L. Bauer, Historical Remarks on Compiler Construction, Compiler Construction, An Advanced Course, 2nd ed., p.603-621, January 1976
	9	Compiler Construction, An Advanced Course, 2nd ed., January 1976
	10	D. Bjorner, "Programming languages: Formal development of interpreters and compilers," pp. 1-21 in International Computing Symposium 1977, ed. E. Morlet and D. Ribbens, North-Holland, Amsterdam (1977).
	11	The Vienna Development Method: The Meta-Language, January 1978
	12	R. G. Cattell, Automatic Derivation of Code Generators from Machine Descriptions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.2, p.173-190, April 1980 [doi>10.1145/357094.357097]
	13	H. Christiansen and N. D. Jones, "Control flow aspects of an algebraic approach to compiler generation," DAIMI IR-27, Computer Science Department, Aarhus University (July 1981).
	14	Jack W. Davidson , Christopher W. Fraser, The Design and Application of a Retargetable Peephole Optimizer, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.2, p.191-202, April 1980 [doi>10.1145/357094.357098]
	15	Jerome Feldman , David Gries, Translator writing systems, Communications of the ACM, v.11 n.2, p.77-113, Feb. 1968 [doi>10.1145/362896.362902]
	16	Harald Ganzinger, Transforming denotational semantics into practical attribute grammars, Semantics-Directed Compiler Generation, Proceedings of a Workshop, p.1-69, January 14-18, 1980
	17	Marie-Claude Gaudel, Specification of compilers as abstract data type representations, Semantics-Directed Compiler Generation, Proceedings of a Workshop, p.140-164, January 14-18, 1980
	18	Marie-Claude Gaudel, Compiler Generation from Formal Definition of Programming Languages: A Survey, Proceedings of the International Colloquium on Formalization of Programming Concepts, p.96-114, April 19-25, 1981
	19	R. Steven Glanville , Susan L. Graham, A new method for compiler code generation, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.231-254, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512785]
	20	H. H. Goldstine and J. von Neumann, "Planning and coding problems for an electronic computing instrument, Part II, Vol 1.," pp. 80-151 in John von Neumann: Collected Works, Vol. V, Macmillan, New York (1963). The report was prepared for the U.S. Army Ordnance Department in April 1947.
	21	David Gries, Compiler Construction for Digital Computers, John Wiley & Sons, Inc., New York, NY, 1971
	22	S. C. Johnson, "Yacc - yet another compiler compiler," CSTR 32, Bell Laboratories, Murray Hill NJ (July 1975). See the UNIX Programmer's Manual2 Section 19 (January 1979)
	23	S. C. Johnson, "A tour through the portable C compiler," UNIX Programmer's Manual2 (Section 34) (January 1979).
	24	Walter L. Johnson , James H. Porter , Stephanie I. Ackley , Douglas T. Ross, Automatic generation of efficient lexical processors using finite state techniques, Communications of the ACM, v.11 n.12, p.805-813, Dec. 1968 [doi>10.1145/364175.364185]
	25	Neil D. Jones, Semantics-Directed Compiler Generation: Proceedings, Springer-Verlag New York, Inc., Secaucus, NJ, 1980
	26	B. W. Kernighan , D. M. Ritchie, The C programming language, Prentice-Hall, Inc., Upper Saddle River, NJ, 1978
	27	D. E. Knuth, Invited papers: History of writing compilers, Proceedings of the 1962 ACM national conference on Digest of technical papers, p.43, September 01-01, 1962 [doi>10.1145/800198.806098]
	28	D. E. Knuth, "Semantics of context-free languages," Math. Systems Theory2(2), pp. 127-145 (June 1968). Correction in 5(1) pp. 95-96 (1971).
	29	M. E. Lesk, "Lex - a lexical analyzer generator," CSTR 39, Bell Laboratories, Murray Hill NJ (October 1975). See the version by M. E. Lesk and E. Schmidt in the UNIX Programmer's Manual2 Section 20 (January 1979)
	30	Philip M. Lewis, 2nd , Daniel J. Rosenkrantz , Richard E. Stearns, Compiler Design Theory, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1976
	31	J. McCarthy, "Towards a mathematical science of computation," pp. 21-28 in Information Processing 1962, ed. C. M. Popplewell, North-Holland, Amsterdam (1963).
	32	F. Lockwood Morris, Advice on structuring compilers and proving them correct, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.144-152, October 01-03, 1973, Boston, Massachusetts [doi>10.1145/512927.512941]
	33	P. D. Mosses, "SIS - semantics implementation system: Reference manual and user guide," DAIMI MD-30, Department of Computer Science, University of Aarhus, Denmark (August 1979).
	34	Peter D. Mosses, A Constructive Approach to Compiler Correctness, Proceedings of the 7th Colloquium on Automata, Languages and Programming, p.449-469, July 14-18, 1980
	35	Peter D. Mosses, A Semantic Algebra for Binding Constructs, Proceedings of the International Colloquium on Formalization of Programming Concepts, p.408-418, April 19-25, 1981
	36	L. Paulson, "A semantics-directed compiler generator," manuscript (to appear).
	37	K.-J. Raiha, "Bibliography on attribute grammars," SIGPLAN Notices15(3), pp. 35-44 (March 1980).
	38	Jean-Claude Raoult , Ravi Sethi, Properties of a Notation for Combining Functions, Proceedings of the 9th Colloquium on Automata, Languages and Programming, p.429-441, July 12-16, 1982
	39	Martin R. Raskovsky , Philip A. Collier, From standard to implementation denotational semantics, Semantics-Directed Compiler Generation, Proceedings of a Workshop, p.94-139, January 14-18, 1980
	40	D. M. Ritchie, "A tour through, the UNIX C compiler," UNIX Programmer's Manual2(Section 33) January 1979).
	41	D. S. Scott and C. Strachey, Towards a mathematical semantics for computer languages, Polytechnic Press, Brooklyn, New York (April 1971).
	42	R. Sethi, "Control flow aspects of semantics directed compiling," TR 98, Bell Laboratories, Murray Hill NJ (September 1981).
	43	R. Sethi, "Circular expressions: elimination of static environments," Science of Computer Programming1(3), For an earlier version, see Lecture Notes in Computer Science 115, (1982).
	44	J. E. Stoy, Denotational Semantics, MIT Press, Cambridge MA (1977).
	45	C. Strachey and C. Wadsworth, "Continuations: a mathematical semantics which can deal with full jumps," Technical Monograph PRG-11, Programming Research Group, Oxford University (1974).
	46	R. D. Tennent, The denotational semantics of programming languages, Communications of the ACM, v.19 n.8, p.437-453, Aug. 1976 [doi>10.1145/360303.360308]
	47	D. A. Turner, "A new implementation technique for applicative languages," Software - Practice and Experience9(1), pp. 31-49 January 1979).
	48	M. Wand, "Deriving target code as a representation of continuation semantics," TR 94, Computer Science Department, Indiana University, Bloomington IN (July 1980).
	49	M. Wand, "Different advice on structuring compilers and proving them correct," TR 95, Computer Science Department, Indiana University, Bloomington IN (September 1980).