Syntax-directed semantics. Formal models based on tree transducers (Q4210160)

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.