Simple multi-visit attribute grammars

Joost Engelfriet, Gilberto Filè

    Research output: Contribution to journalArticleAcademic

    33 Citations (Scopus)
    75 Downloads (Pure)


    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.
    Original languageEnglish
    Pages (from-to)283-314
    JournalJournal of computer and system sciences
    Issue number3
    Publication statusPublished - 1982


    Dive into the research topics of 'Simple multi-visit attribute grammars'. Together they form a unique fingerprint.

    Cite this