Dynamic allocation of space for attribute instances in multi-pass evaluators of attribute grammars

ABSTRACT

Attribute grammars [14] have proved useful as the basis of input languages for compiler-compilers. Many algorithms have evolved which can be used to automatically produce an evaluator for a given attribute grammar. The task of an evaluator is to compute the values of the attribute instances attached to a parse tree. From the compiler point of view, the evaluator takes care of the semantic analysis and in some cases also the code generation of the compiler. An overview of various evaluation algorithms is given in [6]. A bibliography can be found in [21].

REFERENCES

• 1: Gregor V. Bochmann, Semantic evaluation from left to right, Communications of the ACM, v.19 n.2, p.55-62, Feb. 1976 [doi>10.1145/359997.359999]
• 2: Rina Cohen , Eli Harry, Automatic generation of near-optimal linear-time translators for non-circular attribute grammars, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.121-134, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567764]
• 3: Fang, I.: FOLDS, a declarative formal language definition system. STAN-CS-72-329, Computer Science Department, Stanford University, Stanford, California, December 1972.
• 4: Ganzinger, H.: Optimierende Erzeugung von Übersetzerteilen aus Implementierungsorientierten Sprachbeschreibungen. TUM-INFO-7809, Institut für Informatik, Technische Universität München, München, Mai 1978.
• 5: Harald Ganzinger, On Storage Optimization for Automatically Generated Compilers, Proceedings of the 4th GI-Conference on Theoretical Computer Science, p.132-141, March 26-28, 1979
• 6: Giegerich,R. and Wilhelm,R.: Attribute evaluation. State of the Art and Future Trends in Compilation, Preliminary Document 2, Seminaires IRIA, Rocquencourt, January 1978, 299-336.
• 7: Jazayeri,M.: Storage-efficient storage management in an attribute grammar evaluator. Manuscript, Department of Computer Science, University of North Carolina, Chapel Hill, N.C., 1978.
• 8: Jazayeri,M. and Pozefsky,D.: Algorithms for efficient evaluation of multi-pass attribute grammars without a parse tree. Report TR 77-001, Department of Computer Science, University of North Carolina, Chapel Hill, N.C., February 1977.
• 9: Mehdi Jazayeri , Kenneth G. Walter, Alternating semantic evaluator, Proceedings of the 1975 annual conference, p.230-234, January 1975 [doi>10.1145/800181.810328]
• 10: Jochum,G.: Generierung optimierter semantischer Analyse für Ein- und Mehrpassübersetzer. Diplomarbeit, Institut für Informatik, Technische Universität München, München, November 1977.
• 11: Kastens,U.: Ordered attribute grammars. Bericht 7/78, Institut für Informatik II, Universität Karlsruhe, Karlsruhe, 1978.
• 12: Kennedy,K. and Ramanathan,J.: A deterministic attribute grammar evaluator based on dynamic sequencing. Technical Report 476-093-12, Department of Mathematical Sciences, Rice University, Houston, Texas, October 1975.
• 13: Ken Kennedy , Scott K. Warren, Automatic generation of efficient evaluators for attribute grammars, Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.32-49, January 19-21, 1976, Atlanta, Georgia [doi>10.1145/800168.811538]
• 14: Knuth,D.E.: Semantics of context-free languages. Mathematical Systems Theory 2, 2 (1968), 127-145.
• 15: Koskimies,K.: LALR(1) syntax analysis for the programming language Euclid (in Finnish). Internal Report C-1978-41, Department of Computer Science, University of Helsinki, Helsinki, 1978.
• 16: Koskimies,K.: The definition of compile-time checking in C-Euclid as an attribute grammar (in Finnish). Internal Report C-1979-17, Department of Computer Science, University of Helsinki, Helsinki, February 1979.
• 17: B. W. Lampson , J. J. Horning , R. L. London , J. G. Mitchell , G. J. Popek, Report on the programming language Euclid, ACM SIGPLAN Notices, v.12 n.2, p.1-79, February 1977 [doi>10.1145/954666.971189]
• 18: Bernard Lorho, Semantic attributes processing in the system DELTA, Symposium on Methods of Algorithmic Language Implementation, p.21-40, September 10-13, 1975
• 19: Milton,D.R.: Syntactic specification and analysis with attributed grammars. Technical Report 304, Computer Sciences Department, University of Wisconsin-Madison, Madison, Wisconsin, August 1977.
• 20: Diane Pozefsky , Mehdi Jazayeri, A Family Of Pass-Oriented Attribute Grammar Evaluators, Proceedings of the 1978 annual conference, p.261-270, December 04-06, 1978, Washington, D.C., United States [doi>10.1145/800127.804108]
• 21: Räihä,K-J.: On attribute grammars and their use in a compiler writing system. Report A-1977-4, Department of Computer Science, University of Helsinki, Helsinki, August 1977.
• 22: Räihä,K-J. and Saarinen,M.: An optimization of the alternating semantic evaluator. Information Processing Letters 6, 3 (June 1977), 97-100.
• 23: Räihä,K-J., Saarinen,M., Soisalon-Soininen,E. and Tienari,M.: The compiler writing system HLP (Helsinki Language Processor). Report A-1978-2, Department of Computer Science, University of Helsinki, Helsinki, March 1978.
• 24: Mikko Saarinen, On Constructing Efficient Evaluators for Attribute Grammars, Proceedings of the Fifth Colloquium on Automata, Languages and Programming, p.382-397, July 17-21, 1978
• 25: Waldean Allen Schulz, Semantic analysis and target language synthesis in a translator., 1976
• 26: Scott Kipling Warren, The coroutine model of attribute grammar evaluation., 1976

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Allocation/deallocation strategies

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

General Terms:
Management