Summary
This paper describes the evaluation of semantic attributes in a bounded number of passes from left-to-right and/or from right-to-left over the derivation tree of a program. Evaluation strategies where different instances of the same attribute in any derivation tree are restricted to be evaluated in one pass, with for every derivation tree the same pass number, are referred to as simple multi-pass whereas the unrestricted pass-oriented strategies are referred to as pure multi-pass.
A graph theoretic characterization is given, showing in which cases an attribute grammar meets the simple multi-pass requirements and what are the minimal pass numbers of its attributes for a given sequence of pass directions. For the special cases where only left-to-right passes are made or where left-to-right and right-to-left passes strictly alternate, new algorithms are developed that associate minimal pass numbers with attributes and indicate in case of failure the attributes that cause the rejection of the grammar. Mixing of a simple multi-pass strategy with other evaluation strategies, in case the grammar is not simple multi-pass, is discussed.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The design and analysis of computer algorithms. Reading, Mass.: Addison-Wesley 1974
Alblas, H.: A characterization of attribute evaluation in passes, Memorandum 315, Dept. of Appl. Math., Twente University of Technology (1980)
Bochmann, G.V.: Semantic evaluation from left to right. Comm. ACM 19, 55–62 (1976)
Engelfriet, J., Filè, G.: Passes and paths of attribute grammars, Memorandum 323, Dept. of Appl. Math., Twente University of Technology (1980). Also to appear in Information and Control
Fang, I.: FOLDS, a declarative formal language definition system. Rep. STAN-CS-72-329, Computer Science Dept., Stanford University (1972)
Giegerich, R., Wilhelm, R.: Attribute evaluation, in: Le point sur la compilation, Proc. IRIA Symposium on state of the art and future trends in compilation, 337–365 (1978)
Jazayeri, M.: On attribute grammars and the semantic specification of programming languages, Rep. 1159, Case Western Reserve University (1974)
Jazayeri, M., Walter, K.G.: Alternating semantic evaluator. Proc. ACM 1975 Annual Conference, 230–234 (1975)
Kennedy, K., Warren, S.K.: Automatic generation of efficient evaluators for attribute grammars. Proc. Third ACM Symposium on Principles of Programming Languages, 32–49 (1976)
Knuth, D.E.: Semantics of context-free languages. Math. Systems Theory 2, 127–145 (1968) Correction in: Math. Systems Theory 5, 95–96 (1971)
Räihä, K.-J., Saarinen, M.: An optimization of the alternating semantic evaluator. Information Processing Letters 6, 97–100 (1977)
Räihä, K.-J., Ukkonen, E.: Minimizing the number of evaluation passes for attribute grammars. Proc. 7th Int. Colloq. on Automata, Languages and Programming 1980, Lecture Notes in Computer Science 85, pp. 500–511. Berlin-Heidelberg-New York: Springer 1980
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Alblas, H. A characterization of attribute evaluation in passes. Acta Informatica 16, 427–464 (1981). https://doi.org/10.1007/BF00264495
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF00264495