Open AccessK-Visit Attribute Grammars
Author(s) -
Hanne Riis,
Sven Skyum
Publication year - 1980
Publication title -
daimi pb
Language(s) - English
Resource type - Journals
eISSN - 2245-9316
pISSN - 0105-8517
DOI - 10.7146/dpb.v9i121.6539
Subject(s) - grammar , decidability , rule based machine translation , combinatorics , tree adjoining grammar , mathematics , argument (complex analysis) , hierarchy , tree (set theory) , context free grammar , indexed grammar , l attributed grammar , integer (computer science) , discrete mathematics , computer science , node (physics) , natural language processing , linguistics , programming language , physics , medicine , philosophy , quantum mechanics , economics , market economy
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.