More Web Proxy on the site http://driver.im/

article

Free access

Control flow aspects of semantics directed compiling (Summary)

Author:

Ravi SethiAuthors Info & Claims

ACM SIGPLAN Notices, Volume 17, Issue 6

Pages 245 - 260

https://doi.org/10.1145/872726.806999

Published: 01 June 1982 Publication History

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

[1]

J. A. Goguen, J. W. Thatcher, E. G. Wagner, and J. B. Wright, "Initial algebra semantics and continuous algebras," J. ACM24(1), pp. 68-95 (January 1977).

Digital Library

[2]

J. W. Thatcher, E. G. Wagner, and J. B. Wright, "More on advice on structuring compilers and proving them correct," pp. 165-188 in Semantics Directed Compiler Generation, ed. N. D. Jones, Lecture Notes in Computer Science 94, Springer-Verlag, Berlin (1980).

Digital Library

[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]

A. V. Aho and J. D. Ullman, Principles of Compiler Design, Addison-Wesley, Reading MA (1977).

Digital Library

[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]

F. L. Bauer, "Historical remarks on compiler construction," pp. 603-621 in Compiler Construction: An Advanced Course, 2nd edition, ed. F. L. Bauer and J. Eickel, Lecture Notes in Computer Science 21, Springer-Verlag, Berlin (1976).

Digital Library

[9]

F. L. Bauer and J. Eickel (eds), Compiler Construction: An Advanced Course, 2nd edition, Lecture Notes in Computer Science 21, Springer-Verlag, Berlin (1976).

Digital Library

[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]

D. Bjorner and C. B. Jones, The Vienna Development Method: The Meta-Language, Lecture Notes in Computer Science 61, Springer Verlag, Berlin (1978).

Digital Library

[12]

R. G. G. Cattell, "Automatic derivation of code generators from machine descriptions," TOPLAS2(2), pp. 173-190 (April 1980).

Digital Library

[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]

J. W. Davidson and C. W. Fraser, "The design and application of a retargetable peephole optimizer," TOPLAS2(2), pp. 191-202 (April 1980).

Digital Library

[15]

J. Feldman and D. Gries, "Translator writing systems," Comm. ACM11(2), pp. 77-113 (February 1968).

Digital Library

[16]

H. Ganzinger, "Transforming denotational semantics into practical attribute grammars," pp. 1-69 in Semantics Directed Compiler Generation, ed. N. D. Jones, Lecture Notes in Computer Science 94, Springer-Verlag, Berlin (1980).

Digital Library

[17]

M. C. Gaudel, "Specification of compilers as abstract data type representations," pp. 140-164 in Semantics Directed Compiler Generation, ed. N. D. Jones, Lecture Notes in Computer Science 94, Springer-Verlag, Berlin (1980).

Digital Library

[18]

M. C. Gaudel, "Compiler generation from formal definition of programming languages: a survey," pp. 96-114 in Formalization of Programming Concepts, Intl. Colloquium, Peniscola, Spain, Lecture Notes in Computer Science 107, Springer-Verlag, Berlin (April 1981).

Digital Library

[19]

R. S. Glanville and S. L. Graham, "A new method for compiler code generation (extended abstract)," Fifth Annual ACM Symposium on Principles of Programming Languages, pp. 231-240 (January 1978).

Digital Library

[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]

D. Gries, Compiler Construction for Digital Computers, John Wiley, New York (1971).

Digital Library

[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]

W. L. Johnson, J. H. Porter, S. I. Ackley, and D. T. Ross, "Automatic generation of efficient lexical processors using finite state techniques," Comm. ACM11(12), pp. 805-813 (December 1968).

Digital Library

[25]

N. D. Jones (ed), Semantics-Directed Compiler Generation, Lecture Notes in Computer Science 94, Springer-Verlag, Berlin (1980).

Digital Library

[26]

B. W. Kernighan and D. M. Ritchie, The C Programming Language, Prentice-Hall, Englewood Cliffs NJ (1978).

Digital Library

[27]

D. E. Knuth, "History of writing compilers," 1962 ACM National Conference, p. 43,126 (September 1962).

Digital Library

[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]

P. M. Lewis II, D. J. Rosenkrantz, and R. E. Stearns, Compiler Design Theory, Addison-Wesley, Reading MA (1976).

Digital Library

[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. L. Morris, "Advice on structuring compilers and proving them correct," ACM Symposium on Principles of Programming Languages, Boston MA, pp. 144-152 (October 1973).

Digital Library

[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]

P. D. Mosses, "A constructive approach to compiler correctness," pp. 449-469 in Automata, Languages and Programming, 7th Colloquium, Noordwijkerhout, Lecture Notes in Computer Science 85, Springer-Verlag, Berlin (July 1980).

Digital Library

[35]

P. D. Mosses, "A semantic algebra for binding constructs," pp. 408-418 in Formalization of Programming Concepts, Intl. Colloquium, Peniscola, Spain, Lecture Notes in Computer Science 107,| Springer-Verlag, Berlin (April 1981).

Digital Library

[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]

J.-C. Raoult and R. Sethi, "Properties of a notation for combining functions," in Automata, Languages and Programming, 9th Colloquium, Aarhus, Lecture Notes in Computer Science, Springer-Verlag, Berlin (July 1982).

Digital Library

[39]

M. Raskovsky and P. Collier, "From standard to implementation denotational semantics," pp. 94-139 in Semantics Directed Compiler Generation, ed. N. D. Jones, Lecture Notes in Computer Science 94, Springer-Verlag, Berlin (1980).

Digital Library

[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," Comm. ACM19(8), pp. 437-453 (August 1976).

Digital Library

[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).

Cited By

Hanson D(2006)Simple code optimizationsSoftware: Practice and Experience10.1002/spe.438013080813:8(745-763)Online publication date: 30-Oct-2006
https://doi.org/10.1002/spe.4380130808
Ringström JFritzson PPettersson M(2005)Generating an efficient compiler for a data parallel language from a denotational specificationCompiler Construction10.1007/3-540-57877-3_17(248-262)Online publication date: 30-May-2005
https://doi.org/10.1007/3-540-57877-3_17
Pettersson M(2005)Generating efficient code from continuation semanticsCompiler Compilers10.1007/3-540-53669-8_81(165-178)Online publication date: 4-Jun-2005
https://doi.org/10.1007/3-540-53669-8_81
Show More Cited By

Index Terms

Control flow aspects of semantics directed compiling (Summary)
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
      1. Source code generation
    2. Formal language definitions
      1. Semantics
2. Theory of computation
  1. Semantics and reasoning
    1. Program semantics
      1. Denotational semantics

Recommendations

Control flow aspects of semantics directed compiling (Summary)
SIGPLAN '82: Proceedings of the 1982 SIGPLAN symposium on Compiler construction

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 ...
A truly generative semantics-directed compiler generator
Proceedings of the 1982 SIGPLAN symposium on Compiler construction

This paper describes semantic processing in the compiler generating system MUG2. MUG2 accepts high-level descriptions of the semantics of a programming language including full runtime semantics, data flow analysis, and optimizing transformations. This ...
Denotational semantics-directed compiler generation for data flow machines

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 17, Issue 6

Proceedings of the 1982 SIGPLAN symposium on Compiler construction

June 1982

347 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/872726

Issue’s Table of Contents

SIGPLAN '82: Proceedings of the 1982 SIGPLAN symposium on Compiler construction
June 1982
357 pages
ISBN:0897910745
DOI:10.1145/800230
Chairmen:
John R. White,
Frances E. Allen

Copyright © 1982 Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1982

Published in SIGPLAN Volume 17, Issue 6

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
416
Total Downloads

Downloads (Last 12 months)98
Downloads (Last 6 weeks)7

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hanson D(2006)Simple code optimizationsSoftware: Practice and Experience10.1002/spe.438013080813:8(745-763)Online publication date: 30-Oct-2006
https://doi.org/10.1002/spe.4380130808
Ringström JFritzson PPettersson M(2005)Generating an efficient compiler for a data parallel language from a denotational specificationCompiler Construction10.1007/3-540-57877-3_17(248-262)Online publication date: 30-May-2005
https://doi.org/10.1007/3-540-57877-3_17
Pettersson M(2005)Generating efficient code from continuation semanticsCompiler Compilers10.1007/3-540-53669-8_81(165-178)Online publication date: 4-Jun-2005
https://doi.org/10.1007/3-540-53669-8_81
Pleban ULee P(1988)An automatically generated, realistic compiler for imperative programming languageACM SIGPLAN Notices10.1145/960116.5401223:7(222-232)Online publication date: 1-Jun-1988
https://dl.acm.org/doi/10.1145/960116.54012
Pleban ULee P(1988)An automatically generated, realistic compiler for imperative programming languageProceedings of the ACM SIGPLAN 1988 conference on Programming language design and implementation10.1145/53990.54012(222-232)Online publication date: 1-Jun-1988
https://dl.acm.org/doi/10.1145/53990.54012
Lee PPleban U(1987)A realistic compiler generator based on high-level semantics: another progress reportProceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages10.1145/41625.41651(284-295)Online publication date: 1-Oct-1987
https://dl.acm.org/doi/10.1145/41625.41651
Lee PPleban UScherlis WWilliams JGabriel R(1986)On the use of LISP in implementing denotational semanticsProceedings of the 1986 ACM conference on LISP and functional programming10.1145/319838.319866(233-248)Online publication date: 8-Aug-1986
https://dl.acm.org/doi/10.1145/319838.319866
Pleban U(1984)Compiler prototyping using formal semanticsACM SIGPLAN Notices10.1145/502949.50288319:6(94-105)Online publication date: 1-Jun-1984
https://dl.acm.org/doi/10.1145/502949.502883
Pleban UVan Deusen MGraham S(1984)Compiler prototyping using formal semanticsProceedings of the 1984 SIGPLAN symposium on Compiler construction10.1145/502874.502883(94-105)Online publication date: 17-Jun-1984
https://dl.acm.org/doi/10.1145/502874.502883
Allison L(1983)An Executable Prolog SemanticsALGOL Bulletin10.5555/1061790.1061794(10-18)Online publication date: 1-Dec-1983
https://dl.acm.org/doi/10.5555/1061790.1061794
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents