Back to University of Twente portal
Simple multi-visit attribute grammars
Engelfriet, Joost and Filè, Gilberto (1982) Simple multi-visit attribute grammars. Journal of computer and system sciences, 24 (3). pp. 283-314. ISSN 0022-0000
![[img]](http://doc.utwente.nl/style/images/fileicons/application_pdf.png)
| PDF 1881Kb |
| Abstract: | An attribute grammar is simple multi-visit if each attribute of a nonterminal has a fixed visit-number associated with it such that, during attribute evaluation, the attributes of a node which have visit-number j are computed at the jth visit to the node. An attribute grammar is l-ordered if for each nonterminal a linear order of its attributes exists such that the attributes of a node can always be evaluated in that order (cf. the work of Kastens).
An attribute grammar is simple multi-visit if and only if it is l-ordered. Every noncircular attribute grammar can be transformed into an equivalent simple multi-visit attribute grammar which uses the same semantic operations. For a given distribution of visit-numbers over the attributes, it can be decided in polynomial time whether the attributes can be evaluated according to these visit-numbers. The problem whether an attribute grammar is simple multi-visit is NP-complete. |
| Item Type: | Article |
| Copyright: | © 1982 Elsevier Science |
| Faculty: | Electrical Engineering, Mathematics and Computer Science (EEMCS) |
| Link to this item: | http://purl.utwente.nl/publications/69001 |
| Official URL: | http://dx.doi.org/10.1016/0022-0000(82)90030-7 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page