K-Visit Attribute Grammars
DOI:
https://doi.org/10.7146/dpb.v9i121.6539Resumé
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.
Downloads
Publiceret
Citation/Eksport
Nummer
Sektion
Licens
Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.