Table of Contents
Table of contents of Syntax Definition for Language Prototyping
1 Introduction 1
1.1 General 1
1.2 Part I: Context-free Parsing Techniques 4
1.3 Part II: A Family of Syntax Definition Formalisms 6
1.4 Part III: Multi-Level Algebraic Specification 7
1.5 Part IV: Polymorphic Syntax Definition 9
1.6 Short Trips 9
1.7 Origins of the Chapters 11
2 Specification in ASF+SDF 13
2.1 Introduction 13
2.2 Many-Sorted Algebra 14
2.3 Grammars as Signatures 15
2.4 Conditional Equations 18
2.5 Term Rewriting 18
2.6 Modularization 18
2.7 The ASF+SDF Meta-Environment 18
2.8 Literate Specification 19
2.9 Specification of Programming Languages 19
2.10 Literature 21
I Context-Free Parsing Techniques 23
3 Scannerless Generalized-LR Parsing 25
3.1 Introduction 25
3.2 Scannerless Parsing 30
3.3 Grammar Normalization 36
3.4 Disambiguation 40
3.5 Parser Generation 45
3.6 Automatic Lexical Disambiguation 50
3.7 Reject Productions 52
3.8 Generalized-LR Parsing 56
3.9 Implementation 66
3.10 Related Work 68
3.11 Conclusions 69
4 Disambiguation Filters 71
4.1 Introduction 71
4.2 Disambiguation 72
4.3 Preliminaries 74
4.4 Filters 76
4.5 Priorities 80
4.6 Prolog Operators 84
4.7 Offside Rule 86
4.8 Pattern Matching Filters 86
4.9 Discussion 90
4.10 Conclusions 92
5 A Case Study in Optimizing Parsing Schemata by Disambiguation Filters 93
5.1 Introduction 93
5.2 Preliminaries 95
5.3 Disambiguation Filters 96
5.4 Parsing Schemata 97
5.5 Priority Conflicts 99
5.6 From Earley to LR 102
5.7 Multi-set Filter 107
5.8 Conclusions 111
II Context-Free Syntax Definition 113
6 A Family of Syntax Definition Formalisms 115
6.1 Introduction 115
6.2 An Overview of SDF2 118
6.3 Design 123
6.4 Organization 126
7 Context-Free Grammars 129
7.1 Symbols 129
7.2 Grammars 131
7.3 Context-Free Grammars (Kernel) 133
7.4 Basic Symbols 138
7.5 Parse Trees 144
8 Disambiguation and Abbreviation 157
8.1 Priorities 157
8.2 Regular Expressions 166
8.3 Lexical and Context-Free Syntax 174
8.4 Restrictions 181
9 Renaming and Modularization 185
9.1 Renamings 185
9.2 Aliases 192
9.3 Modules 195
10 The Syntax Definition Formalism SDF2 203
10.1 SDF2 203
10.2 Comparison to SDF 208
10.3 Discussion and Concluding Remarks 209
III Multi-Level Algebraic Specification 215
11 Extensions of First-Order Specification 217
11.1 Introduction 218
11.2 Multi-Level Specifications 220
11.3 Related Formalisms 223
11.4 Outline 226
12 Untyped and Simply Typed Specifications 227
12.1 Untyped Equational Specifications 227
12.2 One-Level Specifications 232
12.3 Typechecking One-Level Specifications 241
13 Examples of Multi-Level Specifications 253
13.1 Introduction 253
13.2 One Level 254
13.3 Two Levels 255
13.4 Polymorphic Data Types 257
13.5 Three Levels 262
13.6 Type Equations 264
14 Definition of Multi-Level Specifications 273
14.1 Syntax and Equational Logic 273
14.2 Modular Specifications 277
14.3 Well-Formedness 279
14.4 Type Assignment 285
14.5 Typechecking 295
14.6 Discussion and Concluding Remarks 296
IV Polymorphic Syntax Definition 303
15 Polymorphic Syntax Definition 305
15.1 Introduction 305
15.2 Signatures and Grammars 307
15.3 Two-Level Grammars 317
15.4 Examples 319
15.5 Properties 324
15.6 Parsing 327
15.7 Related Formalisms 330
15.8 Conclusions 332
V Epilogue 333
16 Concluding Remarks 335
16.1 Syntax 335
16.2 Type Systems 337
16.3 Program and Specification Schemata 337
VI Appendices 339
A Auxiliary Modules for the Specification of SDF2 341
A.1 Literals 341
A.2 ATerms 341
A.3 Renamings 346
A.4 SDF2 349
B Auxiliary Modules for Multi-Level Specifications 351
B.1 Library Modules 351
B.2 Term Utilities 354
C Samenvatting 365
C.1 Algemeen 365
C.2 Resultaten 367
D Bibliography 371