Attribute grammars and recursive program schemes. I. II

DOI10.1016/0304-3975(82)90003-2zbMath0481.68068OpenAlexW4210277633MaRDI QIDQ1162363

Paul Franchi-Zannettacci, Bruno Courcelle

Publication date: 1982

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(82)90003-2

zbMATH Keywords

semantic rulesmany-sorted algebrasheterogeneous algebrasattribute grammar specificationattribute systemderivation trees of context-free grammarsequivalence problem for purely synthesized attribute systemsprimitive recursive schemes with parametersstrong noncircularitysystems of recursive definitions

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Specification and verification (program logics, model checking, etc.) (68Q60)

Related Items (41)

Systematic debugging method for attribute grammar description ⋮ The translation power of top-down tree-to-graph transducers ⋮ Synthesized and inherited functions. A new computational model for syntax-directed semantics ⋮ Pushdown machines for the macro tree transducer ⋮ Tree Transformations and Dependencies ⋮ High level tree transducers and iterated pushdown tree transducers ⋮ Classical and incremental attribute evaluation by means of recursive procedures ⋮ Equivalences and transformations of regular systems - applications to recursive program schemes and grammars ⋮ Composition and evaluation of attribute coupled grammars ⋮ Proofs of partial correctness for attribute grammars with applications to recursive procedures and logic programming ⋮ Can we transform logic programs into attribute grammars ? ⋮ A bottom-up characterization of deterministic top-down tree transducers with regular look-ahead ⋮ Equivalence of finite-valued tree transducers is decidable ⋮ Attribute grammars as tree transducers over cyclic representations of infinite trees and their descriptional composition ⋮ Characterizing attributed tree translations in terms of macro tree transducers ⋮ Iterated linear control and iterated one-turn pushdowns ⋮ Computational and attribute models of formal languages ⋮ The IO- and OI-hierarchies ⋮ A complete rewriting system for a monoid of tree transformation classes ⋮ Unnamed Item ⋮ An implementation of syntax directed functional programming on nested- stack machines ⋮ Multiple context-free tree grammars: lexicalization and characterization ⋮ Single-valuedness of tree transducers is decidable in polynomial time ⋮ Context-free hypergraph grammars have the same term-generating power as attribute grammars ⋮ Attribute Grammars as Recursion Schemes over Cyclic Representations of Zippers ⋮ Tree transducers with external functions ⋮ Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity ⋮ Basic tree transducers ⋮ A Survey on Decidable Equivalence Problems for Tree Transducers ⋮ Decidability of the finiteness of ranges of tree transductions ⋮ The equivalence of bottom-up and top-down tree-to-graph transducers ⋮ The generating power of total deterministic tree transducers ⋮ Extended multi bottom-up tree transducers ⋮ A comparison of tree transductions defined by monadic second order logic and by attribute grammars ⋮ An extension to trees of the Sardinas and Patterson algorithm ⋮ Macro tree transducers, attribute grammars, and MSO definable tree translations. ⋮ Attributed tree grammars ⋮ Modular tree transducers ⋮ Output string languages of compositions of deterministic macro tree transducers ⋮ Macro tree transducers ⋮ A pumping lemma for output languages of macro tree transducers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Simple multi-visit attribute grammars
• The formal power of one-visit attribute grammars
• Ordered attributed grammars
• On equivalence of grammars through transformation trees
• On the equivalence problem for attribute systems
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• Attribute Grammars and Mathematical Semantics
• The intrinsically exponential complexity of the circularity problem for attribute grammars
• Bottom-up and top-down tree transformations— a comparison
• Initial Algebra Semantics and Continuous Algebras
• IO-macrolanguages and attributed translations
• An order-algebraic definition of knuthian semantics
• Semantics of context-free languages
• Heterogeneous algebras
• Semantics of context-free languages: Correction

This page was built for publication: Attribute grammars and recursive program schemes. I. II