Automatic generation of efficient evaluators for attribute grammars

ABSTRACT

The translation process may be divided into a syntactic phase and a semantic phase. Context-free grammars can be used to describe the set of syntactically correct source texts in a formal yet intuitively appealing way, and many techniques are now known for automatically constructing parsers from given CF grammars. Knuth's attribute grammars offer the prospect of similarly automating the implementation of the semantic phase. An attribute grammar is an ordinary CF grammar extended to specify the “meaning” of each string in the language. Each grammar symbol has an associated set of “attributes:”, and each production rule is provided with corresponding semantic rules expressing the relationships between the attributes of symbols in the production. To find the meaning of a string, first we find its parse tree and then we determine the values of all the attributes of symbols in the tree.

REFERENCES

• 1: Aho, A.V. Indexed grammars—an extension of context-free grammars. IEEE Conf. Record of 8th Annual Symp. on Switching and Automata Theory. Austin, Texas, October, 1967.
• 2: Aho, A.V. and Ullman, J.D. Properties of syntax-directed translations. J. Computer Systems Sci. v.3, pp. 319-334 (1965).
• 3: Alfred V. Aho , Jeffrey D. Ullman, Theory of Parsing, Translation and Compiling, Prentice Hall Professional Technical Reference, 1973
• 4: Bochmann, G.V. Semantics evaluated from left to right. Publ. No. 135, Departemente d'Informatique, Universite de Montreal (June 1973).
• 5: Bochmann, G.V. Semantic equivalence of syntactically related attribute grammars. Publ. No. 148, Departemente d'Informatique, Universite de Montreal (November 1973).
• 6: Culik, K. Attributed grammars and languages. Publ. No. 3, Departemente d'Informatique, University de Montreal (May 1969).
• 7: Dreisbach, T.A. A declarative semantic definition of PL360. UCLA-ENG-7289, Computer Science Department, UCLA (October 1972).
• 8: Fang, I. FOLDS, a declarative formal language definition system. STAN-72-329, Comp. Sci. Dept., Stanford Univ. (December 1972).
• 9: Greibach, S. and Hopcroft, J. Scattered context grammars. Scientific Report, System Development Corp., Santa Monica, California (1967).
• 10: Irons, E.T. Towards more versatile mechanical translators. Proc. Symp. on Applied Math., v.15, pp. 41-50 (1963).
• 11: Mehdi Jazayeri, On attribute grammars and the semantic specification of programming languages., 1975
• 12: Jazayeri, M. Live variable analysis, attribute grammars, and program optimization, draft. Dept. of Comp. Sci., Univ. of N. Carolina, Chapel Hill, N.C. (March 1975).
• 13: Knuth, D.E. Semantics of context-free languages. Math. Systems Theory J., v.2, pp. 127-145 (1968).
• 14: Knuth, D.E. Semantics of context-free languages: Correction. Math. Systems Theory J., v.5, p.95 (1971).
• 15: Donald E. Knuth, The Art of Computer Programming Volumes 1-3 Boxed Set, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 16: 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]
• 17: 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
• 18: Daniel J. Rosenkrantz, Programmed Grammars and Classes of Formal Languages, Journal of the ACM (JACM), v.16 n.1, p.107-131, Jan. 1969 [doi>10.1145/321495.321504]
• 19: Stearns, R.E. and Lewis, P.M. Property grammars and table machines. Information and Control v.14, pp. 524-549 (1969)
• 20: van Wijngaarden, A. et. al. Report on the Algorithmic Language ALGOL 68. Numerische Mathematik v.14, pp. 79-218 (1969).
• 21: Warren, S.K. The efficient evaluation of attribute grammars. M.A. Thesis, Dept. of Math. Sci., Rice University, Houston, Texas (April 1975).
• 22: Wayne Theodore Wilner, Declarative semantic definition as illustrated by a definition of simula 67, 1971
• 23: Wilner, W.T. Formal semantic definition using synthesized and inherited attributes.Formal Semantics of Programming Languages (Rustin, ed.), Prentice-Hall (1972).

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Code generation

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Translator writing systems and compiler generators

  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:
Algorithms, Languages, Performance, Theory