The formal power of one-visit attribute grammars

DOI10.1007/BF00289307zbMath0471.68044OpenAlexW1968022708MaRDI QIDQ1157968

Joost Engelfriet, Gilberto File

Publication date: 1981

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf00289307

zbMATH Keywords

derivation treedeterministic top-down tree transductionmacro tree languagesone synthesized attributeone-pass left-to-right attribute grammarsoutput languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (17)

Pushdown machines for the macro tree transducer ⋮ High level tree transducers and iterated pushdown tree transducers ⋮ Composition and evaluation of attribute coupled grammars ⋮ Proofs of partial correctness for attribute grammars with applications to recursive procedures and logic programming ⋮ Attribute grammars and recursive program schemes. I. II ⋮ Multiple context-free tree grammars: lexicalization and characterization ⋮ Context-free hypergraph grammars have the same term-generating power as attribute grammars ⋮ Tree transducers with external functions ⋮ Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity ⋮ Simple multi-visit attribute grammars ⋮ The equivalence of bottom-up and top-down tree-to-graph transducers ⋮ k-visit attribute grammars ⋮ A comparison of tree transductions defined by monadic second order logic and by attribute grammars ⋮ Macro tree transducers, attribute grammars, and MSO definable tree translations. ⋮ A note on one-pass evaluation of attribute grammars ⋮ Modular tree transducers ⋮ Macro tree transducers

Uses Software

• ALGOL 68

Cites Work

• Un théorème de duplication pour les forets algébriques
• A generalized approach to formal languages
• IO and OI. I
• Generalized sequential machine maps
• Bounded nesting in macro grammars
• Attribute Grammars and Mathematical Semantics
• k-visit attribute grammars
• Semantic evaluation from left to right
• The intrinsically exponential complexity of the circularity problem for attribute grammars
• Bottom-up and top-down tree transformations— a comparison
• IO-macrolanguages and attributed translations
• Semantics of context-free languages
• Mappings and grammars on trees

This page was built for publication: The formal power of one-visit attribute grammars