Interpretation and reduction of attribute grammars

Gilberto Filè

    Research output: Contribution to journalArticleAcademic

    6 Citations (Scopus)
    52 Downloads (Pure)

    Abstract

    An attribute grammar (AG) is in reduced form if in all its derivation trees every attribute contributes to the translation. We prove that, eventhough AG are generally not in reduced form, they can be reduced, i.e., put into reduced form, without modifying their translations. This is shown first for noncircular AG and then for arbitrary AG. In both cases the reduction consists of easy (almost syntactic) transformations which do not change the semantic domain of the AG. These easy transformations are formalized by introducing the notion of AG interpretation as an extension to AG of the concept of context-free grammar form. Finally we prove that any general algorithm for reducing even the simple class of L-AG needs exponential time (in the size of the input AG) infinitely often.
    Original languageUndefined
    Pages (from-to)115-150
    JournalActa informatica
    Volume19
    Issue number2
    DOIs
    Publication statusPublished - 1983

    Keywords

    • IR-85760

    Cite this