K-Visit Attribute Grammars

Abstract

An attribute grammar G is k-visit if for any derivation tree t of G it is possible to evaluate all the attributes associated with t by walking through t in such a way that no node in t is visited more than k times.

We show in this paper that any well-defined attribute grammar G is k-visit for some k. Furthermore it is shown using a pumping argument, that given a well-defined grammar G and an integer k it is decidable whether G is k-visit. Thus we can effectively for any well-defined attribute grammar G find the minimal k such that G is k-visit. Finally we show that the k-visit attribute grammars specify a proper hierarchy with respect to translations.