[Prev][Next][Index][Thread]
Thesis: Syntax Definition for Language Prototyping
-
To: types@cs.indiana.edu
-
Subject: Thesis: Syntax Definition for Language Prototyping
-
From: Eelco Visser <visser@wins.uva.nl>
-
Date: Thu, 04 Sep 1997 15:39:59 +0200
-
Delivery-Date: Thu, 04 Sep 1997 08:40:40 -0500
Last week my PhD thesis was delivered from the printer:
Syntax Definition for Language Prototyping
Eelco Visser
ISBN 90-74795-75-7
University of Amsterdam
1997
383 pages + viii
I have a few copies left. So if you are interested drop me an email
with your address.
Regards,
Eelco Visser
P.S. The complete thesis is not available on-line, but
http://adam.wins.uva.nl/~visser/thesis/
contains some excerpts from the thesis including the complete
introduction.
-----
mail:visser@acm.org
http://adam.wins.uva.nl/~visser/
------------------------------------------------------------------------
>From the introduction
------------------------------------------------------------------------
Language prototyping is the activity of designing and testing
definitions of new or existing computer languages. An
important aspect of a language definition is the definition of
its syntax. The subject of this thesis are new formalisms and
techniques that support the development and prototyping of
syntax definitions. There are four main subjects: (1)
Techniques for parsing and disambiguation of context-free
languages. (2) Design and implementation of a new syntax
definition formalism. (3) Design of a multi-level algebraic
specification formalism. (4) Study of polymorphic syntax
definition.
------------------------------------------------------------------------
This thesis is concerned with the design and implementation of
methods to enhance the expressive power and usability of the
syntactic aspects of language definition formalisms. The main
theme is the development of techniques for providing an
expressive syntax definition formalism. The point of departure
is the syntax definition formalism SDF of Heering et
al. (1989) that is used in combination with the algebraic
specification formalism ASF of Bergstra et al. (1989). This
setting provides the direct background and motivation for this
work, but the techniques developed are applicable in other
syntax definition settings as well. There are four main
results:
--- Scannerless generalized-LR parsing is a new approach to
parsing without scanners that solves a number of problems of
conventional parsing techniques, by combining the following
techniques: parsing without scanner, generalized-LR parsing,
static disambiguation with priority and associativity
declarations, lexical disambiguation with follow restrictions
and reject productions.
--- SDF2 is an expressive syntax definition formalism for
context-free syntax defintion. It is a redesign of SDF as a
family of orthogonally defined features for syntax definition.
--- The multi-level algebraic specification formalism MLS
extends first-order many-sorted algebraic specification by
making the sorts used in a signature a user-definable
algebraic data type. This provides a simple and uniform
framework for the specification of advanced type constructs
including polymorphism and higher-order functions.
--- Polymorphic syntax definition is the combination of the
flexible notation facilities of SDF with the flexible typing
facilities of MLS.
--------------------------------------------------------------------------
CONTENTS
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
--------------------------------------------------------------------------