Syntax-Directed Semantics: Formal Models Based on Tree Transducers - Brossura

Fülöp, Zoltan; Vogler, Heiko

Brossura

ISBN 10: 3642722504 ISBN 13: 9783642722509

Casa editrice: Springer, 2011

Riassunto

This is a motivated presentation of recent results on tree transducers, applied to studying the general properties of formal models and for providing semantics to context-free languages. The authors consider top-down tree transducers, macro tree transducers, attributed tree transducers, and macro attributed tree transducers. A unified terminology is used to define them, and their transformational capacities are compared. This handbook on tree transducers will serve as a base for further research.

Su questo libro

Contenuti

1. Introduction.- 1.1 Syntax-Directed Semantics.- 1.2 Tree Transducers.- 1.3 Theory of Compositions of Classes of Tree Transformations.- 1.4 Other Formal Models.- 1.5 Outline of the Book.- 1.6 Bibliographic Notes.- 2. Basic Notions and Notations.- 2.1 Sets and Relations.- 2.2 Partial Orders.- 2.3 Directed Graphs.- 2.4 Derivation Systems.- 2.5 Semigroups, Strings and Languages.- 2.6 String Rewrite Systems.- 2.7 Grammars.- 2.8 Notions on Trees.- 3. Top-Down Tree Transducers.- 3.1 Basic Definitions.- 3.2 Induced Tree Transformation.- 3.3 Characterization of Top-Down Tree Transformations.- 3.4 Height Property.- 3.5 Subclasses of TOP.- 3.6 Composition and Decomposition Results.- 3.7 Composition Semigroup Generated by TOP, l-TOP, and HOM.- 3.8 Bibliographic Notes.- 4. Macro Tree Transducers.- 4.1 Basic Definitions.- 4.2 Induced Tree Transformation.- 4.3 Characterization of Macro Tree Transformations.- 4.4 Height Property.- 4.5 Composition and Decomposition Results.- 4.6 Bibliographic Notes.- 5. Attributed Tree Transducers.- 5.1 Basic Definitions.- 5.2 Induced Tree Transformation.- 5.3 Characterization of Attributed Tree Transformations.- 5.4 Height and Subtree Properties.- 5.5 Composition and Decomposition Results.- 5.6 Bibliographic Notes.- 6. Comparison of Induced Tree Transformation Classes.- 6.1 Comparison of M AC and ATT.- 6.2 Inclusion Diagram Based on TOP, YIELD, ATT, and M AC.- 6.2.1 The inequality bas-MAC ― ATT ? ?.- 6.2.2 The inequality ROM ― sl-MAC ? ?.- 6.2.3 The inequality l-TOP ― sl-MAC ? ?.- 6.2.4 The inequality sl-TOP ― HOM ? ?.- 6.2.5 The inequality sl-TOP ― YIELD ? ?.- 6.2.6 The inequality YIELD ― bas-MAC ? ?.- 6.2.7 The inequality ATT ― 1v-ATT ? ?.- 6.2.8 The inequality nn-ATT ― TOP ? ?.- 6.2.9 The inequality HOM ― l-TOP ? ?.- 6.3 Composition Semigroup Generated by TOP, ATT, and MAC.- 6.4 Bibliographic Notes.- 7. Macro Attributed Tree Transducers.- 7.1 Basic Definitions.- 7.2 Induced Tree Transformation.- 7.3 Characterization of Macro Attributed Tree Transformations.- 7.4 Composition and Decomposition Results.- 7.5 Height Property.- 7.6 Bibliographic Notes.- 8. Two Examples.- 8.1 The Specification Language.- 8.2 Contextual Analysis.- 8.3 Insertion into 2–3 Trees.- 8.4 Bibliographic Notes.

Product Description

Book by Flp Zoltan Vogler Heiko

Dettagli dell'edizione

• Editore: Springer
• Data di pubblicazione: 2011
• Lingua: Inglese
• ISBN 10: 3642722504
• ISBN 13: 9783642722509
• Rilegatura: Copertina flessibile
• Numero di pagine: 288
• Contatto del produttore: Springer Nature Customer Service Center GmbH; ProductSafety@springernature.com; ; Europaplatz 3; Heidelberg; 69115; Germania