Syntax-Directed Semantics
Formal Models Based on Tree Transducers
Published on 17. September 1998
Book
Hardback
X, 269 pages
978-3-540-64607-5 (ISBN)
Description
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.
More details
Series
Language
English
Place of publication
Heidelberg
Germany
Publishing group
Springer Berlin
Target group
Professional and scholarly
Illustrations
biography
Dimensions
Height: 23.5 cm
Width: 15.5 cm
Weight
535 gr
ISBN-13
978-3-540-64607-5 (9783540646075)
DOI
10.1007/978-3-642-72248-6
Schweitzer Classification
Other editions
Additional editions
E-Book
12/2012
Springer
€96.29
Available for download
Book
12/2011
Springer
€106.99
Shipment within 7-9 days
Content
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.