A major drawback of attribute-grammar-based systems is that they are profligate consumers of storage. This paper concerns new storage-management techniques that reduce the number of attribute values retained at any stage of attribute evaluation; it presents an algorithm for evaluating an n-attribute tree that never retains more than O(log n) attribute values. This method is optimal, although it may require nonlinear time. A second algorithm, which never retains more than order n**1/2 attribute values, is also presented, both as an introduction to the O(log n)-method and because it works in linear time.

CR Categories and Subject Descriptors: D.3.1 [Programming Languages]: Formal Definitions and Theory -- semantics; D.3.4 [Programming Languages]: Processors -- translator writing systems and compiler generators; F.3.2 [Logics and Meanings of Programs]: Semantics of Programming Languages -- denotational semantics

General Terms: Algorithms, Theory

Additional Key Words and Phrases: attribute grammar, attribute evaluation, language-based editor, spill file

[ACM Author-Izer Link.]