A characterization of attribute evaluation in passes

H. Alblas

    Research output: Contribution to journalArticleAcademic

    14 Citations (Scopus)
    167 Downloads (Pure)


    This paper describes the evaluation of semantic attributes in a bounded number of passes from left-to-right and/or from right-to-left over the derivation tree of a program. Evaluation strategies where different instances of the same attribute in any derivation tree are restricted to be evaluated in one pass, with for every derivation tree the same pass number, are referred to as simple multi-pass whereas the unrestricted pass-oriented strategies are referred to as pure multi-pass. A graph theoretic characterization is given, showing in which cases an attribute grammar meets the simple multi-pass requirements and what are the minimal pass numbers of its attributes for a given sequence of pass directions. For the special cases where only left-to-right passes are made or where left-to-right and right-to-left passes strictly alternate, new algorithms are developed that associate minimal pass numbers with attributes and indicate in case of failure the attributes that cause the rejection of the grammar. Mixing of a simple multi-pass strategy with other evaluation strategies, in case the grammar is not simple multi-pass, is discussed.
    Original languageEnglish
    Pages (from-to)427-464
    JournalActa informatica
    Issue number4
    Publication statusPublished - 1981


    • IR-85713


    Dive into the research topics of 'A characterization of attribute evaluation in passes'. Together they form a unique fingerprint.

    Cite this