Interpretation and reduction of attribute grammars

Gilberto Filè

    Research output: Contribution to journalArticleAcademic

    6 Citations (Scopus)
    36 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

    Filè, Gilberto. / Interpretation and reduction of attribute grammars. In: Acta informatica. 1983 ; Vol. 19, No. 2. pp. 115-150.
    @article{718ac2c762474118b4f86b7540c50178,
    title = "Interpretation and reduction of attribute grammars",
    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.",
    keywords = "IR-85760",
    author = "Gilberto Fil{\`e}",
    year = "1983",
    doi = "10.1007/BF00264472",
    language = "Undefined",
    volume = "19",
    pages = "115--150",
    journal = "Acta informatica",
    issn = "0001-5903",
    publisher = "Springer",
    number = "2",

    }

    Interpretation and reduction of attribute grammars. / Filè, Gilberto.

    In: Acta informatica, Vol. 19, No. 2, 1983, p. 115-150.

    Research output: Contribution to journalArticleAcademic

    TY - JOUR

    T1 - Interpretation and reduction of attribute grammars

    AU - Filè, Gilberto

    PY - 1983

    Y1 - 1983

    N2 - 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.

    AB - 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.

    KW - IR-85760

    U2 - 10.1007/BF00264472

    DO - 10.1007/BF00264472

    M3 - Article

    VL - 19

    SP - 115

    EP - 150

    JO - Acta informatica

    JF - Acta informatica

    SN - 0001-5903

    IS - 2

    ER -