Machines for attribute grammars

From MaRDI portal





In designing a compiler for a given programming language one can use a context free grammar describing the syntax of the language and an attribute grammar (AG) for describing the semantics. The evaluation of the attribute of the nodes of the constructed parse tree is the subject of many recent works. In the present paper the author introduces two automata models that play, with respect to attribute grammars and attribute evaluation for them, the same role as pushdown automata play for context free grammars. The paper begins with a survey on AG, giving the basic definitions, properties, and results on AG, attribute evaluation, and existing automata for AG's (pushdown assembler, pushdown processor, attributed pushdown machines). The temporary (permanent) register pushdown transducers (TRT, PRT) are defined. In the second section the relations among the classes of string- and tree-translations defined by AG, TRT, PRT are found and a new class of AG, called flags-AG is introduced. Next section is dedicated to the study of the transformation of PRT computations. Based on this in the 4th section there are proved the tree- equivalence between one PRT and flags-AG, and string-equivalence of one- PRT, flags-AG and AG, respectively. The formal power of the models introduced in the paper is studied in the next section and, finally, some concluding remarks and further works are presented.











This page was built for publication: Machines for attribute grammars

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3753513)