The purpose of this paper is to study the formal power of certain classes of attribute-grammars (AG). We first consider the class of 1S-AG and extend a result of [DPSS]. Then we compare the formal power of "one-visit" AG with that of related types of AG. Finally, using a partial characterization of the formal power of arbitrary AG we prove some results on deciding whether an AG is (left-to-right) multi-pass. In Section 1 we give some necessary definitions about AG and related concepts. Section 2 consists of the study of 1S-AG. In Section 3 we extend some of the results of Section 2 to "one-visit" AG and we finally summarize the relations existing among all the classes of AG we considered. In Section 4 we show that the multi-pass problem for AG is complete in exponential time. No complete proofs are given, they can be found in [EF1] and [EF2].
Formal Properties of One-Visit and Multi-Pass Attribute Grammars
FILE', GILBERTO
1980
Abstract
The purpose of this paper is to study the formal power of certain classes of attribute-grammars (AG). We first consider the class of 1S-AG and extend a result of [DPSS]. Then we compare the formal power of "one-visit" AG with that of related types of AG. Finally, using a partial characterization of the formal power of arbitrary AG we prove some results on deciding whether an AG is (left-to-right) multi-pass. In Section 1 we give some necessary definitions about AG and related concepts. Section 2 consists of the study of 1S-AG. In Section 3 we extend some of the results of Section 2 to "one-visit" AG and we finally summarize the relations existing among all the classes of AG we considered. In Section 4 we show that the multi-pass problem for AG is complete in exponential time. No complete proofs are given, they can be found in [EF1] and [EF2].
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
