Skip to main content
SpringerLink
Log in

An order-algebraic definition of knuthian semantics

  • Published:
Mathematical systems theory Aims and scope Submit manuscript

Abstract

This paper presents a formulation, within the framework of initial algebra semantics, of Knuthian semantic systems (K-systems) which contain both synthesized and inherited attributes. The approach is based on viewing the semantics of a derivation tree of a context-free grammar as a set of values, called an attribute valuation, assigned to the attributes of all its nodes. Any tree's attribute valuation which is consistent with the semantic rules of the K-system may be chosen as the semantics of that derivation tree.

The set of attribute valuations of a given tree is organized as a complete partially ordered set such that the semantic rules define a continuous transformation on this set. The least fixpoint of this transformation is chosen as the semantics of a given derivation tree. The mapping from derivation trees to their least fixpoint semantics is a homomorphism between certain algebras. Thus, the semantics of a K-system is an application of the Initial Algebra Semantics Principle of Goguen and Thatcher. This formulation permits a precise definition of K-systems, and generalizes Knuth's original formulation by defining the meaning of recursive (circular) semantic specifications.

The algebraic formulation of K-systems is applied to proving the equivalence of K-systems having the same underlying grammar. Such proofs may require verifying that a K-system possesses certain properties and to this end, a principle of structural induction on many-sorted algebras is formulated, justified, and applied.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. D. M. Berry, On the Design and Specification of the Programming Language OREGANO, Computer Science Department, University of California, Los Angeles, UCLA-ENG-7388, January 1974.

  2. G. Birkhoff and J. D. Lipson, Heterogeneous Algebras,J. Combinatorial Theory, 8, 115–113, 1970.

    Google Scholar 

  3. G. V. Bochmann, Semantic Evaluation from Left to Right,Communications of the ACM, 19(2), 55–62, February 1976.

    Google Scholar 

  4. L. M. Chirica, Contributions to Compiler Correctness, Computer Science Department, University of California, Los Angeles, UCLA-ENG-7697, October 1976.

  5. L. M. Chirica and D. F. Martin, An Algebraic Formulation of Knuthian Semantics,Proceedings of the 17th IEEE Symposium on Foundations of Computer Science, Houston, Texas, October 1976, IEEE, New York, 127–136, 1976.

    Google Scholar 

  6. K. Culic, Attributed Grammars and Languages, Department d' Informatique, Universite de Montreal, Montreal, 1969.

    Google Scholar 

  7. J. W. DeBakker, Recursive Procedures, Mathematical Center, Amsterdam, Report No. MC-24, 1971.

  8. T. A. Dreisbach, A Declarative Semantic Definition of PL360, Computer Science Department, University of California, Los Angeles, UCLA-ENG-7289, 1972.

  9. I. Fang, FOLDS—A Declarative Formal Language Definition System, Computer Science Department, Stanford University, Palo Alto, California, STAN-CS-329, December 1972.

    Google Scholar 

  10. S. Gerhart, Correctness Preserving Program Transformations,Proceedings of the Second ACM Symposium on Principles of Programming Languages, Palo Alto, California, January 1975, ACM, New York, 54–66, 1975.

    Google Scholar 

  11. J. A. Goguen and J. W. Thatcher, Initial Algebra Semantics,Proceedings of the 15th IEEE Symposium on Switching and Automata Theory, New Orleans, Louisiana, October 1974, IEEE, New York, 63–77, 1974.

    Google Scholar 

  12. J. A. Goguen, J. W. Thatcher, E. G. Wagner and J. B. Wright, Initial Algebra Semantics and Continuous Algebras,Journal of the ACM, 24(1), 68–95, January 1977.

    Google Scholar 

  13. M. Jazayeri, W. F. Ogden and W. C. Rounds, The Intrinsically Exponential Complexity of the Circularity Problem for Attribute Grammars,Communications of the ACM, 18(12), 697–706, December 1975.

    Google Scholar 

  14. D. E. Knuth, Semantics of Context-Free Languages,Math. Syst. Th., 2, 127–145, 1968.

    Google Scholar 

  15. D. E. Knuth, Semantics of Context-Free Languages: Correction,Math. Syst. Th., 5, 95–96, 1971.

    Google Scholar 

  16. D. E. Knuth, Examples of Formal Semantics,Lecture Notes in Math. No. 188, Springer-Verlag, Berlin, 212–235, 1971.

    Google Scholar 

  17. C. H. A. Koster, Affix Grammars,ALGOL 68 Implementation, North-Holland, Amsterdam, 1971.

    Google Scholar 

  18. K. Kennedy and S. K. Warren, Automatic Generation of Efficient Evaluators for Attribute Grammars,Conference Record of the Third ACM Symposium on Principles of Programming Languages, Atlanta, Georgia, January 1976, ACM, New York, 32–49, 1976.

    Google Scholar 

  19. P. M. Lewis and B. K. Rosen, Recursively Defined Data Types,Proceedings of ACM Symposium on Principles of Programming Languages, Boston, Massachusetts, October 1973, ACM, New York, 125–138, 1973.

    Google Scholar 

  20. P. M. Lewis, D. J. Rosenkrantz and R. E. Stearns, Attributed Translations,Journal of Computer and System Science, 9, 279–307, 1974.

    Google Scholar 

  21. P. M. Lewis, D. J. Rosenkrantz and R. E. Stearns,Compiler Design Theory, Addison-Wesley, Reading, Massachusetts, 1976.

    Google Scholar 

  22. G. Markowsky, Chain-Complete Posets and Directed Sets with Applications,Algebra Universalis, 6(1), 53–68, 1976.

    Google Scholar 

  23. D. F. Martin and S. A. Vere, On Syntax-Directed Transduction and Tree Transducers,Proceedings of the Second Annual ACM Symposium on Theory of Computing, Northhampton, Massachusetts, May 1970, ACM, New York, 129–135, 1970.

    Google Scholar 

  24. D. Neel and M. Amirchahy, Semantic Attributes and Improvement of Generated Code,Proceedings of ACM National Conference, San Diego, California, November 1974, ACM, New York, 1–10, 1974.

    Google Scholar 

  25. S. R. Petrick, Semantic Interpretation in the REQUEST System, IBM Thomas J. Watson Research Center, Yorktown Heights, New York, Research Report RC4457, July 1973.

    Google Scholar 

  26. D. Scott, Outline of a Mathematical Theory of Computation,Proceedings of the Fourth Annual Princeton Conference on Information Science and Systems, Princeton, New Jersey, 1970, Department of Electrical Engineering, Princeton University, Princeton, New Jersey, 169–176, 1970.

    Google Scholar 

  27. D. Scott, Data Types as Lattices, Unpublished Lecture Notes, Amsterdam, 1972.

  28. D. Scott, Mathematical Concepts in Programming Language Semantics,Proceedings of the AFIPS Spring Joint Computer Conference, Atlantic City, New Jersey, May 1972, AFIPS Press, Montvale, New Jersey, 225–234, 1972.

    Google Scholar 

  29. D. Scott and C. Strachey, Toward a Mathematical Semantics for Computer Languages,Proc. Symp. on Computers and Automata (J. Fox, Ed.), Microwave Research Institute Symposia Series Vol. 21, Polytechnic Institute of Brooklyn, 19–46, 1971.

  30. R. E. Stearns and P. M. Lewis, Property Grammars and Table Machines,Information and Control, 14, 524–549, 1969.

    Google Scholar 

  31. J. E. Stoy,Denotational Semantics: The Scott-Strachey Approach to Programming Language Theory, MIT Press, Cambridge, 1977.

    Google Scholar 

  32. W. T. Wilner, Declarative Semantic Definition, Computer Science Department, Stanford University, Palo Alto, California, STAN-CS-233-71, 1971.

    Google Scholar 

  33. W. T. Wilner, Formal Semantic Definition Using Synthesized and Inherited Attributes,Proceedings of Courant Institute Computer Science Symposium, New York, September 1970, Prentice-Hall, Englewood Cliffs, New Jersey, Vol. 2, 25–39, 1972.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computer Science Department, University of California, 93106, Santa Barbara, CA, USA

    Laurian M. Chirica

  2. Computer Science Department, University of California, Los Angeles, CA, 90024

    David F. Martin

Authors
  1. Laurian M. Chirica
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. David F. Martin
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Editor's Note: This paper is one of several presented in the Session on Semantics at the 17th Annual IEEE Symposium on Foundations of Computer Science, 1976, and subsequently invited for submission to this journal to present different approaches to the subject.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Chirica, L.M., Martin, D.F. An order-algebraic definition of knuthian semantics. Math. Systems Theory 13, 1–27 (1979). https://doi.org/10.1007/BF01744285

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01744285

Keywords

Search

Navigation