Alternating semantic evaluator

ABSTRACT

In order to make the use of attribute grammars practical in (automatic) compiler generation, restricted attribute grammars are introduced. A membership test is given which determines whether a given attribute grammar satisfies the required restrictions. The major advantage of the restricted attribute grammars is that they are non-circular. The given membership test can be embedded in a compiler writing system which accepts an attribute grammar as input and outputs a compiler for the associated language provided the grammar meets the restrictions. The technique is also applicable to translation grammars of [15]. It is assumed that the reader is familiar with context free grammars but not necessarily with attribute grammars.

REFERENCES

• 1: D. E. Knuth, Semantics of Context Free Languages, Mathematical Systems Theory, vol. 2, no. 2, June 1968, 127-145; also see correction, vol. 5, no. 1, March 1971, 95-96.
• 2: W. T. Wilner, Formal Semantic Definition Using Synthesized and Inherited Attributes, in R. Rustin, ed., Formal Semantics of Programming Languages, Prentice Hall, New Jersey, 1972, 25-40.
• 3: T. W. Dreisbach, A Declarative Semantic Definition of PL360, Computer Science Department Report UCLA-ENG-7289, UCLA, 1972.
• 4: S. R. Petrick, Semantic Interpretation in the REQUEST System, Research Report RC 4457, IBM, July 1973.
• 5: D. Neel , M. Amirchahy, Semantic attributes and improvement of generated code, Proceedings of the 1974 annual conference, p.1-10, January 1974 [doi>10.1145/800182.810373]
• 6: D. Neel , M. Amirchahy, Removal of invariant statements from nested-loops in a single effective compiler pass, ACM SIGPLAN Notices, v.10 n.3, p.87-96, March 1975
• 7: Mehdi Jazayeri, On attribute grammars and the semantic specification of programming languages., 1975
• 8: M. Jazayeri , W. F. Ogden , W. C. Rounds, On the complexity of the circularity test for attribute grammars, Proceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.119-129, January 20-22, 1975, Palo Alto, California [doi>10.1145/512976.512989]
• 9: I. Fang, Folds, a Declarative Formal Language Definition System, Computer Science Department Reprot, STAN-CS-72-329, Stanford University, December 1972.
• 10: G. V. Bochmann, Semantics Evaluated From Left to Right, Département d'Informatique, Publication no. 135, Université de Montréal, June 1973.
• 11: G. V. Bochmann, Semantic Equivalence of Syntactically Related Attribute Grammars, Département d'Informatique publication no. 148, University sité de Montréal. November 1973.
• 12: D. E. Knuth, Examples of Formal Semantics, in Lecture Notes in Mathematics no. 188, Springer Verlag, Berlin, 1971, 212-235.
• 13: A. V. Aho and J. D. Ullman, Translations on a Context Free Grammar, Information and Control, vol. 19, no. 5, December 1971, 439-475.
• 14: P. M. Lewis, II , R. E. Stearns, Syntax-Directed Transduction, Journal of the ACM (JACM), v.15 n.3, p.465-488, July 1968 [doi>10.1145/321466.321477]
• 15: P. M. Lewis II, D. J. Rosenkrantz and R. E. Stearns, Attributed Translations, Journal of Computer and System Science, vol. 9, no. 3, December 1974, 279-307.
• 16: J. Kelleher, F. McGriff and D. Pozefsky, COMP 145 Project Report, Computer Science Department, University of North Carolina, Spring 1975.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Grammar types (e.g., context-free, context-sensitive)

General Terms:
Theory