Syntax-directed semantics. Formal models based on tree transducers
The book investigates the concept of tree transducers, an abstraction of some formal models which give semantics to context-free languages in a syntax-directed way. Such formal models include attribute grammars with synthesized attribute only, denotational semantics and attribute grammars with both synthesized and inherited attributes. Chapter 1 and 2 present an overview on syntax directed semantics and establish basic notions and notations. Chapter 3 introduces the concept of a top-down tree transducer, created by abstraction from the attribute grammars with synthesized attributes only. Different subclasses of top-down tree translators and the inclusion diagram of these subclasses are also considered. Chapter 4 deals with another formal model of syntax directed semantics: the macro tree transducer, which is an abstraction from denotational semantics. It is more powerful than a top-down tree transducer and can be considered as a straightforward extension of top-down tree transducers. Chapter 5 presents the attributed tree transducer, created by abstraction from attribute grammars with both synthesized attributes and inherited attributes. It is more powerful that a macro tree transducer. The derivation relation of an attribute tree transducer can be circular and hence is not terminating. There is a decision algorithm with an exponential time complexity to detect the circularity. For a noncircular attributed tree transducer the derivation relation is terminating. The problems raised by practice are very often modeled by noncircular attributed tree transducers with polynomial time for the membership problem. Chapter 6 contains a detailed comparison of macro tree transducers and attributed tree transducers, including a discussion about various extensions. Chapter 7 investigates another formal model, called macro attributed tree transducer, which integrates the approaches presented in Chapters 4 and 5. Chapter 8 gives two more complicate examples which are motivated by practical problems. The first example deals with the contextual analysis in block-structured programming languages and the second shows how insertion in 2-3 trees can be specified by means of macro attributed tree transducers. The book is intended for those who work in an academic environment, e.g. in universities or research institutes, and who deal with theoretical computer science. The subject can also be taught to graduate students in computer science. However, as prerequisites, some basic knowledge of universal algebra and of formal languages theory and compiling is necessary to use the book effectively. The book is also a valuable source of inspiration for the active researchers in the field.
- The time complexity of typechecking tree-walking tree transducers
- Deciding equivalence of top-down XML transformations in polynomial time
- Macro forest transducers
- Functional description of the contextual analysis in block-structured programming languages: A case study of tree transducers
- Synthesized and inherited functions. A new computational model for syntax-directed semantics
- A comparison of tree transductions defined by monadic second order logic and by attribute grammars
- Output string languages of compositions of deterministic macro tree transducers
- Decision problems of tree transducers with origin
- Multiple context-free tree grammars: lexicalization and characterization
- Hierarchies of tree series transformations
- Macro tree transducers, attribute grammars, and MSO definable tree translations.
- The complexity of the exponential output size problem for top-down and bottom-up tree transducers
- Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity
- Characterization of tree automata based on quantum logic
- XML navigation and transformation by tree-walking automata and transducers with visible and invisible pebbles
- Deciding origin equivalence of weakly self-nesting macro tree transducers
- Domains of partial attributed tree transducers
- Unidirectional Derivation Semantics for Synchronous Tree-Adjoining Grammars
- scientific article; zbMATH DE number 3858450 (Why is no real title available?)
- Decision problems of tree transducers with origin
- Syntax-Directed Translations and Quasi-alphabetic Tree Bimorphisms
- From Tree-Based Generators to Delegation Networks
- An Algebra for Tree-Based Music Generation
- Monadic Datalog Tree Transducers
- A Kleene Theorem for Forest Languages
- Syntax-Directed Translations and Quasi-alphabetic Tree Bimorphisms — Revisited
- scientific article; zbMATH DE number 41955 (Why is no real title available?)
- Forward and backward application of symbolic tree transducers
- A two-dimensional hierarchy for attributed tree transducers
- Composition closure of linear extended top-down tree transducers
- Tree-based generation of languages of fractals
- Branching synchronization grammars with nested tables
- Compositions with Constant Weighted Extended Tree Transducers
- Characterizing attributed tree translations in terms of macro tree transducers
- Compositions of Weighted Extended Tree Transducers — The Unambiguous Case
- Attributed tree transducers for partial functions
- Deciding whether an attributed translation can be realized by a top-down transducer
- Deciding linear height and linear size-to-height increase of macro tree transducers
- Extended symbolic finite automata and transducers
- The equivalence problem for deterministic MSO tree transducers is decidable
- Automata for XML -- a survey
- Deaccumulation techniques for improving provability
- The generative power of delegation networks
- Compositions of extended top-down tree transducers
This page was built for publication: Syntax-directed semantics. Formal models based on tree transducers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4210160)
