zbMATH — the first resource for mathematics

Sublinear-space evaluation algorithms for attribute grammars. (English) Zbl 0633.68005
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(\(\sqrt{n})\) attribute values, is also presented, both as an introduction to the O(log n) method and because it works in linear time.

68Q60 Specification and verification (program logics, model checking, etc.)
68N20 Theory of compilers and interpreters
68N01 General topics in the theory of software
Full Text: DOI Link