K-Visit Attribute Grammars | Zendy

Hanne Riis | Zendy; Sven Skyum | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

K-Visit Attribute Grammars

Author(s) -

Hanne Riis,

Sven Skyum

Publication year - 1980

Publication title -

daimi report series

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research