# 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.

##### MSC:
 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: