The formal power of one-visit attribute grammars

Joost Engelfriet, Gilberto Filè

    Research output: Contribution to journalArticleAcademic

    39 Citations (Scopus)
    138 Downloads (Pure)

    Abstract

    An attribute grammar is one-visit if the attributes can be evaluated by walking through the derivation tree in such a way that each subtree is visited at most once. One-visit (1V) attribute grammars are compared with one-pass left-to-right (L) attribute grammars and with attribute grammars having only one synthesized attribute (1S). Every 1S attribute grammar can be made one-visit. One-visit attribute grammars are simply permutations of L attribute grammars; thus the classes of output sets of 1V and L attribute grammars coincide, and similarly for 1S and L-1S attribute grammars. In case all attribute values are trees, the translation realized by a 1V attribute grammar is the composition of the translation realized by a 1S attribute grammar with a deterministic top-down tree transduction, and vice versa; thus, using a result of Duske e.a., the class of output languages of 1V (or L) attribute grammars is the image of the class of IO macro tree languages under all deterministic top-down tree transductions.
    Original languageUndefined
    Pages (from-to)275-302
    JournalActa informatica
    Volume16
    Issue number3
    DOIs
    Publication statusPublished - 1981

    Keywords

    • IR-85447

    Cite this