A characterization of attribute evaluation in passes

H. Alblas

    Research output: Contribution to journalArticleAcademic

    13 Citations (Scopus)
    66 Downloads (Pure)

    Abstract

    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 languageUndefined
    Pages (from-to)427-464
    JournalActa informatica
    Volume16
    Issue number4
    DOIs
    Publication statusPublished - 1981

    Keywords

    • IR-85713

    Cite this