Sublinear-Space Evaluation Algorithms for Attribute Grammars

Abstract

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 O (√ n ) attribute values, is also presented, both as an introduction to the O (log n ) method and because it works in linear time.