×

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
PDF BibTeX XML Cite
Full Text: DOI Link